В настоящее время я использую график для хранения зависимостей, а затем запускаю все вершины, у которых нет никаких зависимостей. Это работает, но это кажется грязным. Есть ли лучший алгоритм или структура данных, которые я должен использовать?
#!/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