perl - 通过 Perl 在图中查找只有传入边和传出边的节点

Question

我有下图

my %connections=(36=>[31,22],31=>[30],30=>[20],22=>[20,8],20=>[1],8=>[5],5=>[2],2=>[1,20]);

是否有任何现有算法可以让我们找到只有出边和入边的节点。因此，鉴于上图，它将产生:

$node_only_incoming_edge = [36];
$node_only_outgoing_edge = [1];

使用 graph.gafol.net 创建的图表

更新:根据 RF 建议修复了 %connection 输入错误。

Answer 1

Richard Fearn 的回答描述了自己计算结果的算法。另一种方法是使用 Graph模块。例如:

use strict;
use warnings;
use Graph;

my $g = Graph->new;

my %connections = (
    36 => [31,22],
    31 => [22,30],  # Your data omitted 22.
    30 => [20],
    22 => [20,8],
    20 => [1,99],   # Added 99 for testing.
     8 => [5],
     5 => [2],
     2 => [1,20],
    88 => [31],     # Added 88 for testing.
);

for my $n (keys %connections){
    $g->add_edge($n, $_) for @{$connections{$n}};
}

my @outgoing_only = $g->source_vertices;        # 36 and 88
my @incoming_only = $g->successorless_vertices; #  1 and 99