Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Finding All Paths From a Graph From a Given Source and End Node

by neversaint (Deacon)
on Oct 28, 2010 at 14:13 UTC ( #868031=perlquestion: print w/replies, xml ) Need Help??

neversaint has asked for the wisdom of the Perl Monks concerning the following question:

Dear Masters,
I have a graph, for example this one. What I want to do is to fin all possible path from a given starting vertice and ending vertice.
my %graph =( 'F' => ['B','C','E'], 'A' => ['B','C'], 'D' => ['B'], 'C' => ['A','E','F'], 'E' => ['C','F'], 'B' => ['A',''E','F'] );
So for example if I chose B as my starting and E as my ending I would get, These paths:
B->E B->F->E B->F->C->E B->A->C->E B->A->C->F->E
What's the fastest way to implement that in Perl?

---
neversaint and everlastingly indebted.......

Replies are listed 'Best First'.
Re: Finding All Paths From a Graph From a Given Source and End Node
by Limbic~Region (Chancellor) on Oct 28, 2010 at 14:54 UTC
    neversaint,
    I noticed you asked a graph question the other day too. If they are related, then perhaps it might be useful for you to explain the bigger picture. There are a few monks I lean on heavily whenever I have a graph question. Using Graph or some other high level abstraction model is usually faster for the programmer to write - but can end up being terribly slow runtime.

    If you only wanted the shortest path between the two end points (assuming cyclical path avoidance), I would go with modified Bidirectional search which I discovered in A Better Word Morph Builder. To find all paths I might go with a self-pruning Depth-first search. This is still a brute force search but you pay attention to which paths are invalid and do not descend into them when reaching the node from a different path.

    If you need example code beyond the explanation above, let me know but it won't happen until tonight.

    Cheers - L~R

Re: Finding All Paths From a Graph From a Given Source and End Node
by Limbic~Region (Chancellor) on Oct 28, 2010 at 18:38 UTC
    neversaint,
    Per our conversation, here is an example of finding all paths using a depth-first search. It is unoptimized and with all the copying of arrays and hashes - I wouldn't expect it to be a top performer as is. I am thinking about the self-pruning approach I alluded to earlier as I have to convince myself it will still work with a directed graph (which I now realize this is). If it works, I will post it as well.

    Update: Assuming you can create a function to convert your node name to an integer (preferrably 0 based) then the following should be a lot faster assuming copying strings is faster than arrays and hashes.

    Update 2: Here is a version using short-circuiting. I am not happy with it since you need to enumerate over an array of bitstrings to determine if the path can be pruned rather than doing a lookup. I may post my own SoPW to see if anyone can come up with a better way. I have tried this on a very limited test set so it could very well be flawed. I would be interested to know how it fairs performance wise on real data as well as if it can be found to be flawed.

    Cheers - L~R

      I tried to benchmark your subs (together with my ones - Update: that turned out to be slower). The short circuiting approach is slower than the previous one.
        choroba,
        The short circuiting approach is slower than the previous one

        I suspect this will heavily depend on the test data which neversaint hasn't supplied. In a nutshell, I am recording path information on the basis that it will pay off down the road. If there is no short circuit possibilities then the overhead of tracking will not be paid for and it becomes slower.

        This is why I said I was unhappy with it. I am going to let this sit in my feeble brain for a while and if I can't come up with a better approach I will post a new thread for other monks to weigh in on.

        Update: The following is the basically the same algorithm with some optimizations. I would be interested in your test data and/or your benchmark.

        Cheers - L~R

Re: Finding All Paths From a Graph From a Given Source and End Node
by jethro (Monsignor) on Oct 28, 2010 at 14:34 UTC
    Exhaustive search. Just try out every vertice recursively and disregard any vertices that you already have in your path. If you want all paths and not only the shortest or anything I don't see much possibility for a shortcut

    You can speed this up a bit if you change the recursive function to an interative, but basically you just simulate the recursion then.

    UPDATE: See Limpic-Regions post for the truth about shortcuts

Re: Finding All Paths From a Graph From a Given Source and End Node
by Tux (Abbot) on Oct 28, 2010 at 14:48 UTC

    Did you already look at the Graph module? It has a chapter in the man page that awfully sounds like your quest:

    All-Pairs Shortest Paths (APSP) For either a directed or an undirected graph, return the APSP o +bject describing all the possible paths between any two vertices of t +he graph. If no weight is defined for an edge, 1 (one) is assumed +.

    Enjoy, Have FUN! H.Merijn
Re: Finding All Paths From a Graph From a Given Source and End Node
by BrowserUk (Pope) on Oct 29, 2010 at 00:44 UTC

    I finally got my recursive version to work. How it compares with the iterative versions I haven't tested:

    #! perl -slw use strict; use Data::Dump qw[ pp ]; my %graph =( F => ['B','C','E'], A => ['B','C'], D => ['B'], C => ['A','E','F'], E => ['C','F'], B => ['A','E','F'] ); sub findPaths { my( $seen, $start, $end ) = @_; return [[$end]] if $start eq $end; $seen->{ $start } = 1; my @paths; for my $node ( @{ $graph{ $start } } ) { my %seen = %{$seen}; next if exists $seen{ $node }; push @paths, [ $start, @$_ ] for @{ findPaths( \%seen, $node, +$end ) }; } return \@paths; } my( $start, $end ) = @ARGV; print "@$_" for @{ findPaths( {}, $start, $end ) }; __END__ c:\test>868031 B E B A C E B A C F E B E B F C E B F E c:\test>868031 A F A B E C F A B E F A B F A C E F A C F c:\test>868031 A C A B E C A B E F C A B F C A B F E C A C

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      Dear BrowserUK, I have successfully generalize your code above so that it just take %graph, $start,$end as input and return final array. Thanks so much. BTW, what's the time complexity of your subroutine?
      sub findPathsAll { my ($graph,$start,$end) = @_; my $findPaths_sub; $findPaths_sub = sub { my( $seen, $start, $end ) = @_; return [[$end]] if $start eq $end; $seen->{ $start } = 1; my @paths; for my $node ( @{ $graph->{ $start } } ) { my %seen = %{$seen}; next if exists $seen{ $node }; push @paths, [ $start, @$_ ] for @{ $findPaths_sub->( \%seen, $node, $end ) }; } return \@paths; }; my @all; push @all,[@$_] for @{ $findPaths_sub->( {}, $start, $end ) + }; return @all; }


      ---
      neversaint and everlastingly indebted.......

        The usual thing to do when you have a recursive routine that needs an IUO parameter, is to use a 'helper' wrapper that supplies it.

        Here's a cleaned up and simplified version that does that:

        #! perl -slw #! perl -slw use strict; use List::Util qw[ shuffle ]; use Data::Dump qw[ pp ]; my %graph = map { ( chr( 64 + $_ ) => [ (shuffle 'A'...'Z')[ 0 .. 1+ int( rand 10 )] ] + ) } 1, (shuffle 2 .. 25)[ 0.. int( rand 20 )], 26; pp \%graph; sub _findPaths { my( $graph, $start, $end, $seen ) = @_; return [$end] if $start eq $end; $seen->{ $start } = 1; map { map [ $start, @$_ ], _findPaths( $graph, $_, $end, {%$seen} ); } grep !$seen->{ $_ }, @{ $graph->{ $start } }; } sub findPaths { _findPaths( @_, {} ); } my( $start, $end ) = @ARGV; print "@$_" for findPaths( \%graph, $start, $end ); __END__ c:\test>868031 A Z { A => ["M", "L", "V", "Y", "C", "T", "X", "B", "U", "G", "J"], B => ["U", "W", "E", "Q", "M", "G", "N"], H => ["K", "L", "I", "S", "B", "H", "M", "P", "Q", "N", "T"], L => ["Q", "X", "E", "D", "L", "S", "N", "K"], P => ["D", "O", "Y", "R", "I", "W", "Q", "V", "N"], Q => ["P", "A", "N", "X", "R", "M", "T", "H", "O", "V"], R => ["O", "A", "S", "V", "M"], T => ["J", "Z", "F", "T", "Q", "X", "S"], V => ["L", "E", "Z", "V"], Y => ["M", "X", "Y", "I", "K", "U", "G", "S"], Z => ["M", "F", "A", "P", "I"], } A L Q P R V Z A L Q P V Z A L Q R V Z A L Q T Z A L Q H P R V Z A L Q H P V Z A L Q H T Z A L Q V Z A V L Q T Z A V L Q H T Z A V Z A T Z A T Q P R V Z A T Q P V Z A T Q R V Z A T Q H P R V Z A T Q H P V Z A T Q V Z A B Q P R V Z A B Q P V Z A B Q R V Z A B Q T Z A B Q H P R V Z A B Q H P V Z A B Q H T Z A B Q V Z

        Be warned. The random tree generator can generate some pretty big results sets.


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Finding All Paths From a Graph From a Given Source and End Node
by LanX (Cardinal) on Oct 28, 2010 at 23:04 UTC
    your problem is not well defined, but the demonstrated results can be achieved with a recursive function:

    use strict; use warnings; use Data::Dumper; $|=1; my $start="B"; my $stop="E"; my %graph =( 'F' => ['B','C','E'], 'A' => ['B','C'], 'D' => ['B'], 'C' => ['A','E','F'], 'E' => ['C','F'], 'B' => ['A','E','F'] ); track($start); sub track { my @path=@_; my $last=$path[-1]; for my $next (@{$graph{$last}}) { next if $next ~~ @path; # next if grep {$_ eq $next } @path; if ($next eq $stop){ print join ("->",@path,$stop),"\n"; } else { track(@path,$next); } } }

    prints

    B->A->C->E B->A->C->F->E B->E B->F->C->E B->F->E

    for large graphs you should consider using a hash instead of passing an array to speed up the test.

    Cheers Rolf

      > for large graphs you should consider using a hash instead of passing an array to speed up the test.

      e.g. like this

      { my %seen; sub track { my @path=@_; my $last=$path[-1]; $seen{$last}=1; for my $next ( @{$graph{$last}} ) { next if $seen{$next}; if ($next eq $stop) { print join ("->",@path,$stop),"\n"; } else { track(@path,$next); } } delete $seen{$last}; } }

      Cheers Rolf

      Thank you!! Very helpful!!
Re: Finding All Paths From a Graph From a Given Source and End Node
by JavaFan (Canon) on Oct 30, 2010 at 12:25 UTC
    What's the fastest way to implement that in Perl?
    Considering your graph has a loop (A -> B, B -> A), and your start point lies on this loop, there's no fastest way. In fact, any program that terminates will not be correct, as there are an infinite numbers of paths from B to E.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (4)
As of 2020-10-30 02:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favourite web site is:












    Results (277 votes). Check out past polls.

    Notices?