Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: traversing a hash looking for path?

by Albannach (Prior)
on Apr 11, 2006 at 19:41 UTC ( #542647=note: print w/replies, xml ) Need Help??


in reply to traversing a hash looking for path?

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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://542647]
help
Chatterbox?
[ambrus]: choroba: heh heh... I have such a doc bug report somewhere. fixed by now.
[Corion]: Once upon a time I had automatic tests for checking the synopsis, but I stopped doing that because the setup was too fragile on CPAN testers for extracting code from the SYNOPSIS.
[Corion]: Maybe I should move the extraction of the code from the SYNOPSIS section into the author tests, or something like that...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (8)
As of 2017-02-27 12:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?






    Results (383 votes). Check out past polls.