Perl 依赖树求解器

Question

我正在尝试想出一种创造性的方法来确定依赖关系，以便我可以按正确的顺序启动测试回归。

例如:

a: d, e, f

b: c, d

c: f

d: e

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

我有以下代码，它将打印“叶”节点“e”和“f”，但是我一直不知道如何向上遍历并打印父节点。任何提示将不胜感激。

谢谢!

my @input = ("a:d,e,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, $builtRef, $dep);
 }
}

Answer 1

您最好使用图形模块，例如 Graph::Directed。例如，以下给出了满足您的依赖关系的顺序:

use Graph::Directed;

my $graph = Graph::Directed->new();

my @edges = qw(d a e a f a c b d b f c e d);
while (my ($from, $to) = splice @edges, 0, 2) {
    $graph->add_edge($from, $to);
}
my @order = $graph->toposort();
print "@order\n";

它产生输出

f e c d a b