如何找到并行树中的哪些作业可以并行运行？

Question

目前,我使用图形来存储依赖项,然后运行没有任何依赖项的所有顶点.这有效,但感觉很糟糕.我应该使用更好的算法或数据结构吗？

#!/usr/bin/perl

use strict;
use warnings;

use Graph;

#FIXME: naive implementation, there may be a much better way to do this
sub run_in_parallel {
       my $g = shift->copy;

       while (my @v = $g->vertices) {
               my @run = grep { $g->is_successorless_vertex($_) } @v;
               print "running ", join(", ", @run), " in parallel\n";
               for my $compenent (@run) {
                       $g->delete_vertex($compenent);
               };
       }
}

my $g = Graph->new;
while (<DATA>) {
       my ($component, @dependencies) = split;
       unless ($g->has_vertex($component)) {
               $g->add_vertex($component);
       }
       for my $dependency (@dependencies) {
               unless ($g->has_vertex($dependency)) {
                       $g->add_vertex($dependency);
               }
               $g->add_edge($component, $dependency);
       }
}

run_in_parallel($g);

#component  dependency list
__DATA__
a           b c d
b           e
c           f g
d
e
f
g

Answer 1

您可以并行运行任何没有未完成的依赖项的任务。例如，在显示的数据集上，您可以在开始时并行运行 d、e、f 和 g。当 f 和 g 完成时，您可以并行运行 c，即使 d 和 e 仍在运行，等等。您的算法只需要每次任务完成时将其标记为已完成，并重新评估现在是否有任何任务可以运行。