查找節點隨着一個圖形通過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的

回答

相關問題