Beefy Boxes and Bandwidth Generously Provided by pair Networks
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??


in reply to Finding All Paths From a Graph From a Given Source and End Node

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
    Thank you!! Very helpful!!

Log In?
Username:
Password:

What's my password?
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?