Welcome to the Monastery PerlMonks

### Re: Finding All Paths From a Graph From a Given Source and End Node

by LanX (Archbishop)
 on Oct 28, 2010 at 23:04 UTC ( #868177=note: print w/replies, xml ) Need Help??

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

Replies are listed 'Best First'.
Re^2: Finding All Paths From a Graph From a Given Source and End Node
by LanX (Archbishop) on Oct 28, 2010 at 23:25 UTC
> 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

Re^2: Finding All Paths From a Graph From a Given Source and End Node
by Anonymous Monk on Feb 21, 2014 at 10:48 UTC

Create A New User
Node Status?
node history
Node Type: note [id://868177]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (9)
As of 2020-04-09 11:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The most amusing oxymoron is:

Results (47 votes). Check out past polls.

Notices?