Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

traversing a hash looking for path?

by Anonymous Monk
on Apr 11, 2006 at 19:10 UTC ( #542640=perlquestion: print w/ replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

I'm wondering if anyone has some suggestions on how to accomplish this. I have a data structure mocked up below that represents connections between two nodes. I'm trying to create an algorithm that given a starting and ending IP will find one path. This is a lot like the traveling salesman problem. The data structure is simply a representaion of the data so I can alter it in any way that might make this problem easier.
#!C:/perl/bin/perl.exe use strict; use warnings; my $start = '1.2.3.4'; my $end = '1.2.3.6'; my %network = ( '1.2.3.4 links with 1.2.3.5', '1.2.3.5 links with 1.2.3.4', '1.2.3.5 links with 1.2.3.6', '1.2.3.6 links with 1.2.3.5', '1.2.3.6 links with 1.2.3.7', '1.2.3.7 links with 1.2.3.6', '1.2.3.7 links with 1.2.3.4', '1.2.3.4 links with 1.2.3.7', '1.2.3.5 links with 1.2.3.7', '1.2.3.7 links with 1.2.3.5' ); one path is: '1.2.3.4 links with 1.2.3.5' '1.2.3.5 links with 1.2.3.6'

I could always just use brute force, but there has to be a more elegant solution.
Any thoughts?

Comment on traversing a hash looking for path?
Download Code
Re: traversing a hash looking for path?
by Fletch (Chancellor) on Apr 11, 2006 at 19:38 UTC

    The strange storing of what's really an array of links into a hash aside, I'd parse your edge information out and use Graph.

Re: traversing a hash looking for path?
by Albannach (Prior) on Apr 11, 2006 at 19:41 UTC
    Just FYI, this isn't much like the Travelling Salesman Problem (or TSP) as that requires a path that visits every node in the network, usually for a minimum cost (there are many variations, such as using each link only once, etc.) which is probably not what you are after. In any case you should find some valuable tools on the CPAN in Graph as Fletch advises.

    Update: Graph is not so complicated, though you could argue it is overkill for this simple example:

    use strict; use warnings; use Graph; my $net = Graph::Undirected->new; # links go both ways my $start = '1.2.3.4'; my $end = '1.2.3.6'; while(<DATA>) { chomp(my($from,$to) = (split /\s+[^\d.]+\s+/)[0,1]); if($net->has_edge($from,$to) ) { print "duplication of $from to $to\n"; # shows Graph understands u +ndirected links }else{ $net->add_edge($from, $to); print "link from $from to $to added\n"; } } print "the nodes are: ", join(', ', sort $net->vertices), "\n"; print "the links are: ",$net, "\n"; print "a shortest path from $start to $end is: ", join ' => ', $net->S +P_Dijkstra($start,$end); __DATA__ 1.2.3.4 links with 1.2.3.5 1.2.3.5 links with 1.2.3.4 1.2.3.5 links with 1.2.3.6 1.2.3.6 links with 1.2.3.5 1.2.3.6 links with 1.2.3.7 1.2.3.7 links with 1.2.3.6 1.2.3.7 links with 1.2.3.4 1.2.3.4 links with 1.2.3.7 1.2.3.5 links with 1.2.3.7 1.2.3.7 links with 1.2.3.5
    produces:
    link from 1.2.3.4 to 1.2.3.5 added duplication of 1.2.3.5 to 1.2.3.4 link from 1.2.3.5 to 1.2.3.6 added duplication of 1.2.3.6 to 1.2.3.5 link from 1.2.3.6 to 1.2.3.7 added duplication of 1.2.3.7 to 1.2.3.6 link from 1.2.3.7 to 1.2.3.4 added duplication of 1.2.3.4 to 1.2.3.7 link from 1.2.3.5 to 1.2.3.7 added duplication of 1.2.3.7 to 1.2.3.5 the nodes are: 1.2.3.4, 1.2.3.5, 1.2.3.6, 1.2.3.7 the links are: 1.2.3.4=1.2.3.5,1.2.3.4=1.2.3.7,1.2.3.5=1.2.3.6,1.2.3.5 +=1.2.3.7,1.2.3.6=1.2.3.7 a shortest path from 1.2.3.4 to 1.2.3.6 is: 1.2.3.4 => 1.2.3.7 => 1.2. +3.6

    --
    I'd like to be able to assign to an luser

Re: traversing a hash looking for path?
by Herkum (Parson) on Apr 11, 2006 at 20:28 UTC

    I was somewhat excited to see a module that did something neat when the two previous posters mentioned Graph but after looking at it and the extensive documentation and no tutorials I thought this was too much...

    The method I was thinking of is a hash of a hash; the key of the hash is all the IP's and the values are a hash with with your linked IP's.

    my %network = ( '1.2.3.4' => {'1.2.3.5' => undef, '1.2.3.6' => undef, '1.2.3.7' => undef }, '1.2.3.5' => {'1.2.3.4' => undef, '1.2.3.6' => undef, '1.2.3.7' => undef }, '1.2.3.6' => {'1.2.3.4' => undef, '1.2.3.5' => undef, '1.2.3.7' => undef }, '1.2.3.7' => {'1.2.3.4' => undef, '1.2.3.5' => undef, '1.2.3.6' => undef }, );
      I've been looking at the documentation and I agree. I can easily create a hash of hashes with my info, and then I suppose I hand it off to graph and look for has_edge providing my start and end node?
Re: traversing a hash looking for path?
by Limbic~Region (Chancellor) on Apr 11, 2006 at 22:44 UTC
    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

      L~R:

      Since you asked in the ChatterBox for a recursive version, I thought I'd take up the challenge. Here's my take on a recursive solution:

      #!/usr/bin/perl use strict; use warnings; my %net = ( '1.2.3.3' => ['1.2.3.4'], '1.2.3.4' => ['1.2.3.3', '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'], ); my %visited=(); my @stack=(); print find_path('1.2.3.4', '1.2.3.6') || "no solution!"; sub find_path { my ($beg, $end) = @_; return $end if $beg eq $end; $visited{$beg}=1; for my $try (@{$net{$beg}}) { if (!defined($visited{$try})) { push @stack, $beg; my $t = find_path($try, $end); return $beg.'=>'.$t if $t; pop @stack; } } undef; }
      --roboticus
        Both of these are great examples and have opened a few doors for me.
        Thanks for all the help :)
        roboticus,
        Thank you. I have a real hard time thinking recursively for some reason. There are some things that I would want to change. For instance, letting the call stack be handled automatically by the recursion and not relying on lexicals visible at the package level. Here is my take on satisfying those two changes:
        my %net = (...); # shortened for brevity sake print find_path('1.2.3.4', '1.2.3.6', \%net); sub find_path { my ($beg, $end, $net, $seen, $stop, $node, $path) = @_; if (! defined $stop) { ($node, $path) = ($beg, $beg); $stop->{$_} = 1 for @{$net->{$end}}; } return $path if $node eq $end; return "$path=>$end" if $stop->{$node}; return undef if $seen->{$node}++; for (@{$net->{$node}}) { my $found = find_path($beg, $end, $net, $seen, $stop, $_, "$pa +th=>$_"); return $found if $found; } return 'path not found'; }
        I liked the iterative solution better because I could alter the search process by adjusting the shift/unshift and push/pop. I thought recursive solutions were supposed to be more elegant. Perhaps it is just because I don't know what I am doing.

        Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://542640]
Approved by tinita
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (4)
As of 2014-08-01 04:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (256 votes), past polls