perl - 创建由节点列表诱导的图的子图

Question

我目前正在使用Graph，但是它缺少一种方法来创建由给定顶点列表引起的原始图的子图。

我写了一个存根，它使用 Graph 的访问器，但是

这是我的代码：

# subgraph ($graph, @node_list); 
# return subgraph (with the same setup) 
# induced by node list
sub subgraph {
    my $self = shift;
    my $new = $self->new;
    my @edges;
    foreach my $v(@_) {
        $self->has_vertex($v) or next;
        $new->add_vertex($v);
        foreach my $u(@_) {
            $self->has_edge($u, $v) and push @edges, $u, $v;
        };
    };
    $new->add_edges(@edges);
    return $new;
};

笔记：

• 该$Graph->new行为未记录在案，但是由于 Graph 的源显示它会复制属性，但不会复制顶点/边。

• CPAN 上已有功能请求：https ://rt.cpan.org/Ticket/Display.html?id=65497

那么，是否有其他模块（可能是 XS），或者我应该 patch Graph，还是每个人自己编写一个图形类，我也应该这样做？

Answer 1

所以我已经将问题中的代码发布到了 github（大约有 10 个单元测试）。

https://github.com/dallaylaen/perl-Graph-Subgraph

我将不胜感激批评、错误报告和更多测试用例。希望有一天它会进入主模块。

更新：现在可通过 CPAN 获得：Graph::Subgraph。然而，上述段落仍然成立。

Answer 2

如果您有所有顶点的列表和所需的顶点列表，则计算两者之间的集差并使用

$graph->delete_vertices(@unwanted_vertices);

我以前用过这样的东西来修剪一个大图。