Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Anonymous Monk,
I saw this node just as I was leaving so I thought about it on the way home. This is actually a pretty easy problem if you turn it into a tree and I am not sure it requires Graph
#!/usr/bin/perl use strict; use warnings; my %net = ( '1.2.3.4' => ['1.2.3.5', '1.2.3.7'], '1.2.3.5' => ['1.2.3.4', '1.2.3.6', '1.2.3.7'], '1.2.3.6' => ['1.2.3.5', '1.2.3.7'], '1.2.3.7' => ['1.2.3.6', '1.2.3.4', '1.2.3.5'], ); print find_path('1.2.3.4', '1.2.3.6', %net); sub find_path { my ($beg, $end, %net) = @_; my (%seen, %stop, @work); for (@{$net{$end}}) { return "$beg=>$end" if $_ eq $beg; $stop{$_} = 1; } push @work, {key => $_, path => "$beg=>$_"} for @{$net{$beg}}; while (@work) { my $node = pop @work; next if $seen{$node->{key}}++; return "$node->{path}=>$end" if $stop{$node->{key}}; push @work, {key => $_, path => "$node->{path}=>$_"} for @{$ne +t{$node->{key}}}; } return 'path not found'; }

First thing you do is create a %stop hash that tells you when you have built enough of the tree. It will contain all of the nodes connected to $end. If one of those nodes happens to be your $beg value you return immediately.

Next you create a work queue/stack of all the nodes connected to $beg. You build the path as you go so once you have found the node you are looking for you don't have to walk the tree again.

Finally you take an item from the work queue and check to see if you have seen it before. If not you check to see if we are 1-hop away from $beg (%stop hash). If not, we go through all the nodes connected to this node and add it to our work queue. If we get to the end we know that there is no connection.

Cheers - L~R


In reply to Re: traversing a hash looking for path? by Limbic~Region
in thread traversing a hash looking for path? by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (4)
As of 2022-05-25 14:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you prefer to work remotely?



    Results (90 votes). Check out past polls.

    Notices?