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.

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

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
+.
[download]

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.

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.

Read more... (2 kB)

Cheers - L~R

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
[download]

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;
        }
[download]




---
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
[download]

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.

RIP an inspiration; A true Folk's Guy

> BTW, what's the time complexity of your subroutine?

please have a look at this post: Re: Short Circuiting DFS Graph Traversal

Cheers Rolf

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);
    }  
  }
}
[download]

prints

B->A->C->E
B->A->C->F->E
B->E
B->F->C->E
B->F->E
[download]

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

> 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};
  }
}
[download]

Cheers Rolf

Thank you!! Very helpful!!

What's the fastest way to implement that in Perl?

Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated.

:)

I'm not sure if the OP is aware about this distinction, the examples given suggest he talks about non repeated walks.

Cheers Rolf