perl - 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 ]

标签： perlgraph

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