[] 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;
    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);


$VAR1 = [
Connection: close