Finding all paths in a directed acyclic graph structure with CPAN Graph module
非循環有向グラフで、ある頂点から頂点までの全経路を探します。
This script finds all paths from a vertex to another.
(注意点: 循環構造があると無限ループします)
NOTE: cannot be used with cycles.
use strict; use warnings; use Graph::Directed; use Data::Dumper; sub find_all_paths { my ($from, $dest) = @_; return [[$dest]] if $from eq $dest; return undef unless $g->is_reachable($from, $dest); my @paths; foreach my $edge ( $g->edges_from($from) ) { my $child_paths = find_all_paths($edge->[1], $dest); if (defined($child_paths)) { foreach my $child_path (@$child_paths) { push(@paths, [$from, @$child_path]); } } } return \@paths; } # usage my $g = Graph::Directed->new; $g->add_edges(qw( b a c a d a e a f a g a h b i c j h k h l i m l n i o d o t p j q j q r q s r l r n s o )); my $paths = find_all_paths('q', 'a'); print Dumper($paths);
outputs:
$VAR1 = [ [ 'q', 's', 'o', 'd', 'a' ], [ 'q', 'r', 'n', 'i', 'c', 'a' ], [ 'q', 'r', 'l', 'i', 'c', 'a' ], [ 'q', 'j', 'h', 'b', 'a' ] ];