Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

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 ( #868179=note: print w/replies, xml ) Need Help??


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

> 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

  • Comment on Re^2: Finding All Paths From a Graph From a Given Source and End Node
  • Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://868179]
help
Chatterbox?
and the web crawler heard nothing...

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
















    Results (47 votes). Check out past polls.

    Notices?