父子 Perl 数据结构

发布于 2024-12-08 13:41:15 字数 299 浏览 0 评论 0原文

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

该文件具有以下结构

Node       Downstream Node
A          B
B          C
C          D
E          C

etc

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

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

我在 Linux 机器上使用 Perl，而我为其编写此内容的人也是如此。谢谢。

原文

I have a datafile that has a list of paired values representing river flow relationships.

The file has this structure

Node       Downstream Node
A          B
B          C
C          D
E          C

etc

What I need to do is read this file and then for any given node, I need all the UPSTREAM nodes printed.

In the example above if I entered C, I would get E, B, A.

I am using perl on a linux box and the person I am writing this for is too. Thanks.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

紫﹏色ふ单纯 2024-12-15 13:41:15

您的问题的正确数据结构是图表：

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

The correct data structure for your problem is a 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

回复收藏 0 原文

北城孤痞 2024-12-15 13:41:15

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

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

What have you tried? This seems to work, assuming we can load the entire thing into memory. I also assumed each line only had one upstream value and one downstream value. Allowing more is left as an excersise for the reader.

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

回复收藏 0 原文

~没有更多了~