Структура данных родительского дочернего Perl

Question

У меня есть файл данных, в котором есть список парных значений, представляющих отношения речного стока.

Файл имеет такую ​​структуру

Node       Downstream Node
A          B
B          C
C          D
E          C

etc

Что мне нужно сделать, это прочитать этот файл, а затем для любого данного узла мне нужно распечатать все узлы UPSTREAM.

В приведенном выше примере, если я введу C, я получу E, B, A.

Я использую Perl для Linux, и тот, для кого я пишу это, тоже. Благодаря.

Answer 1

Правильная структура данных для вашей проблемы: График :

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

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