#!/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
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |