1

河川の流れの関係を表す一対の値のリストを含むデータファイルがあります。

ファイルはこの構造を持っています

Node       Downstream Node
A          B
B          C
C          D
E          C

etc

私がする必要があるのは、このファイルを読み取ることです。次に、特定のノードについて、すべての UPSTREAM ノードを出力する必要があります。

上記の例で C を入力すると、E、B、A となります。

私は Linux ボックスで perl を使用しており、これを書いている相手もそうです。ありがとう。

4

2 に答える 2

5

問題の正しいデータ構造は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
于 2011-10-06T21:42:52.847 に答える
1

何を試しましたか？すべてをメモリにロードできると仮定すると、これは機能しているようです。また、各ラインには1つのアップストリーム値と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
于 2011-10-06T20:34:04.447 に答える