Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re^2: find all paths of length n in a graph

by Roy Johnson (Monsignor)
on Jan 10, 2006 at 20:47 UTC ( #522312=note: print w/ replies, xml ) Need Help??


in reply to Re: find all paths of length n in a graph
in thread find all paths of length n in a graph

Algorithm::Loops' NestedLoops allows a non-recursive implementation:

use Algorithm::Loops 'NestedLoops'; sub find_path { my ($adj_list, $length) = @_; my %been_there; NestedLoops([ [sort {$a <=> $b} keys %$adj_list], (sub { # The last value on @_ has just changed, so remove it from %be +en_there # and set the new one my ($last_position, $last_value) = ($#_, $_[-1]); delete $been_there{$_} for grep $been_there{$_} >= $last_posit +ion, keys %been_there; $been_there{$last_value} = $last_position; # Here I grep out the already-visited nodes, but you could als +o exclude # any letters that don't result in prefixes of real words. [ grep !defined($been_there{$_}), @{$adj_list->{$last_value}} +] }) x ($length-1)] ); } my $i = find_path(\%adjacency_list, 3); my @path; print "@path\n" while @path = $i->();

Caution: Contents may have been coded under pressure.


Comment on Re^2: find all paths of length n in a graph
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (7)
As of 2015-07-29 08:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (261 votes), past polls