How can I find which jobs in a dependency tree can be run in parallel?

Question

Currently, I am using a graph to store the dependencies and then running all of the vertices the don't have any dependencies. This works, but it feels kludgy. Is there a better algorithm or data structure I should be using?

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

You can run in parallel any tasks with no unfinished dependencies. For example, on your dataset shown you can run d, e, f, and g in parallel at the start. When f and g are finished, you can run c in parallel, even if d and e are still running, etc. Your algorithm just needs every time a task finishes to mark it as done and reevaluate if any tasks are now available to run.

Answer 2

Another idea is to use a Petri net. The nodes in your graph are its places, the actions are its transitions. Every place should have exactly one enabling transition, even when it has no dependencies. That way you don't even need to place any initial tokens.

This also incorporates Karl Bielefeldt's suggestion.