父子Perl数据结构

Question

我有一个数据文件，它有一个表示河流流动关系的配对值列表。

该文件具有这种结构

Node  Downstream Node 
A   B 
B   C 
C   D 
E   C 

etc 

我需要做的就是读取这个文件，然后对于任何给定的节点，我需要打印的所有上游节点是什么。

在上面，如果我进入C中的例子，我会得到E，B，A

我使用在Linux中，我写这个的人Perl是太。谢谢。

Answer 1

你有什么试过的？这似乎工作，假设我们可以将整个内容加载到内存中。我还假设每条线只有一个上游值和一个下游值。允许更多的东西留给读者看。

#!/usr/bin/perl 

use strict; 
use warnings; 
use 5.12.0; 

my %links; 
while(<DATA>) 
{ 
    my ($key, $val) = split ' ', $_; 
    $links{$key}{down}{$val} = 1; # dupes not allowed/ignored 
    $links{$val}{up}{$key} = 1; 
} 

sub gather_up 
{ 
    my $start = shift; 
    my $seen = shift || {}; 

    my @up; 
    if ($links{$start}{up}) 
    { 
     for my $u (sort keys %{$links{$start}{up}}) 
     { 
      unless ($seen->{$u}++) 
      { 
       push @up, $u; 
      } 
     } 

     push @up, map { gather_up($_, $seen) } @up; 
    } 

    @up 
} 

say join ', ', gather_up('C'); 

__END__ 
A   B 
B   C 
C   D 
E   C 

Answer 2

有关问题的正确数据结构是Graph：

#!/usr/bin/env perl 

use warnings; use strict; 
use Graph::Directed; 

my $g = Graph::Directed->new; 

while (my $line = <DATA>) { 
    last unless $line =~ /\S/; 
    my ($v1, $v2) = split ' ', $line; 
    $g->add_edge($v1, $v2); 
} 

print $g->all_predecessors('D'), "\n"; 

__DATA__ 
A   B 
B   C 
C   D 
E   C 

C:\Temp> h 
ACEB