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.
-
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 How to display code and escape characters
are good places to start.