查找节点随着一个图形通过Perl的

只有入边和只出边我有以下图表查找节点随着一个图形通过Perl的

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

alt text

图表使用创建graph.gafol.net

更新：根据RF建议修正了%connection条目错误。

来源

2010-10-31 neversaint

两次与你的图的问题：（1）节点36/31/22之间的边缘是不正确的; （2）它没有显示你的图是直接的。 – 2010-10-31 12:33:53

@RF：我已经修复了图形声明。感谢您指出。 – neversaint 2010-10-31 12:36:50

这仍然是错误的。 31只链接到30，而不是22。 – 2010-10-31 12:43:58

理查德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

来源

2010-10-31 14:54:15 FMc

只有传出边的节点将在connections字典（表示存在从该节点到一个或多个其他节点的边）中有条目，但该节点不会出现在任何字典条目的值中这将表明来自其他节点的该节点存在边缘）。

只有入边的节点将不具有在connections词典中的条目（意味着不存在边缘从该节点到任何其他节点）。然而，它会出现在用于一个或多个字典的条目的（意味着有一个边缘到从某些其他节点在该节点）的值。

来源

2010-10-31 12:39:07

虽然我觉得我喜欢FM的好，对我自己的娱乐，我实现理查德：

#!/usr/bin/perl 

use strict; 
use warnings; 

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

my @left = keys %connections; 
my @only_incoming; 
my @arrives; 
my @only_outgoing; 
my @all_nodes = @left; 

foreach my $left (@left) { 
    foreach my $arrives (@{ $connections{$left} }) { 
    unless ($arrives ~~ @arrives) { 
     push(@arrives, $arrives); 
     push(@all_nodes, $arrives) unless $arrives ~~ @all_nodes; 
    } 
    } 
} 

foreach my $node (@all_nodes) { 
    if ($node ~~ @left and !($node ~~ @arrives)) { 
    push(@only_incoming, $node); 
    } elsif (!($node ~~ @left) and $node ~~ @arrives) { 
    push(@only_outgoing, $node); 
    } 
} 
print "Only incoming: " . join(" ", @only_incoming) . "\n"; 
print "Only outgoing: " . join(" ", @only_outgoing) . "\n";

来源

2010-10-31 15:51:37

查找节点随着一个图形通过Perl的

回答

相关问题