Hatena::ブログ(Diary)

はて日記

2009-11-12

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