Perl依赖树求解器

发布时间：2020-12-16 06:17:59 所属栏目：大数据来源：网络整理

导读：我正在尝试用一种创造性的方法来确定依赖关系,这样我就可以按正确的顺序启动测试回归. 例如： a: d,e,fb: c,dc: fd: e 这意味着测试“a”取决于测试“d,e和f”等的完成. 我有以下代码将打

我正在尝试用一种创造性的方法来确定依赖关系,这样我就可以按正确的顺序启动测试回归.

例如：

a: d,e,f

b: c,d

c: f

d: e

这意味着测试“a”取决于测试“d,e和f”等的完成.

我有以下代码将打印“叶子”节点“e”和“f”,但我仍然坚持如何遍历和打印父节点.任何提示将非常感谢.

谢谢！

my @input = ("a:d,f","b:c,d","c:f","d:e");
my %Tests = ();
my %Built = ();

## Build Structure
foreach my $elem (@input) {
     my $depends = [];
     my $target;
     ($target,$depends) = parseData($elem);
     $Tests{$target} = $depends; ## Setting array ref to hashkey $target     
}


sub parseData {
  my $data = shift;
  my ($target,$deps) = split(/:/,$data);
  my @deps;
  @deps = split(/,/,$deps);
  return ($target,@deps);
}

foreach my $key (keys %Tests) {
  doIT(%Tests,%Built,$key);
}

sub doIT {
 my ($testRef,$builtRef,$target) = @_;
 my $depends = $testRef->{$target};
 if(exists $builtRef->{$target}) {
   return;
 }
 if(!$depends) {
   ## No dependency,build it
   print "RunTest($target)n";
   $builtRef->{$target}++;
   return;
 }

 foreach my $dep (@$depends) {
    doIT($testRef,$dep);
 }
}

解决方法

总有蛮力的方法.我会让别人想出一些聪明的东西：

use strict;
use warnings;

my @input = ("a:d,"d:e");

my %children;
my %parents;

for (@input) {
    my ($parent,@kids) = split /[:,]/;
    for (@kids) {
        $children{$parent}{$_}++;
        $children{$_} ||= {};
        push @{$parents{$_}},$parent;
    }
}

my @order;
while (my $count = scalar keys %children) {
    while (my ($p,$k) = each %children) {
        if (! keys %$k) {
            push @order,$p;
            delete $children{$p};
            delete $children{$_}{$p} for @{$parents{$p}};
        }
    }

    die "circular dependency exists" if $count == scalar keys %children;
}

print "@order";

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!