Graph.pm - как получить все пути определенной длины?

Question

У меня есть следующий примерный график с 9 ребрами:

Предполагается, что график не является ненаправленным, а вес каждого ребра равен 1.

Мы можем описать это программно, используя Graph.pm как

use Graph::Undirected;
my $g = Graph::Undirected->new; # An undirected graph.
$g->add_edge(1, 3);
$g->add_edge(3, 4);
$g->add_edge(4, 2);
$g->add_edge(1, 2);
$g->add_edge(1, 5);
$g->add_edge(1, 2);
$g->add_edge(1, 6);
$g->add_edge(6, 2);
$g->add_edge(2, 7);

Как получить все пути от вершины 1 до вершины 2, которые имеют длину = 2?

Я не нашел никакого метода для этого в Graph.pm : (

В моем примере он должен возвращать 2 пути, [ 1, 5, 2 ] и [ 1, 6, 2 ]

Answer 1

У вас была ошибка в настройке ребра, сравните с моим правильным определением.

use Graph::Undirected;
my $g = Graph::Undirected->new;
$g->add_edge(1, 2);
$g->add_edge(1, 3);
$g->add_edge(1, 5);
$g->add_edge(1, 6);
$g->add_edge(2, 7);
$g->add_edge(3, 4);
$g->add_edge(4, 2);
$g->add_edge(5, 2);
$g->add_edge(6, 2);

for my $neighbour_of_v1 ($g->neighbours(1)) {
    next if 2 == $neighbour_of_v1; # direct neighbour, path is too short
    for my $neighbour_of_neighbour_of_v1 ($g->neighbours($neighbour_of_v1)) {
        next if 1 == $neighbour_of_neighbour_of_v1; # ignore backlink to start
        say "1-$neighbour_of_v1-$neighbour_of_neighbour_of_v1"
            if 2 == $neighbour_of_neighbour_of_v1;
    }
}
__END__
1-5-2
1-6-2