perl - 父子 Perl 数据结构

Question

我有一个数据文件，其中包含代表河流流量关系的配对值列表。

该文件具有这种结构

Node       Downstream Node
A          B
B          C
C          D
E          C

etc

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

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

我在 linux 机器上使用 perl，我写这篇文章的人也是。谢谢。

Answer 1

您的问题的正确数据结构是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:\温度> h
ACEB

Answer 2

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

#!/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