> I have a list of jobs which need to be executed according to some dependencies.
Your dependencies define a Poset and your looking for a so called Linear Extension
The most popular algorithm is called Topological Sorting.
If you are on *nix you can use tsort
Otherwise you can search CPAN for the above keywords.
There is a little personal implementation I did some weeks ago, I'll post it as soon as I find it.
update
Here we go, this is work in progress, no guaranties whatsoever.
Please note: It will die, if the input has circular dependencies and dump the data for check.
The basic idea is simple,
- everything w/o dependencies can be excluded from the data
- after exclusion loop again to 1
- if the loops terminate w/o deleting all nodes, the data must have been corrupt
use strict;
use warnings;
use feature qw/say/;
use Data::Dumper;
use constant DEBUG=>1; # only for show()
use Data::Dump qw/pp/;
my %depends; # HoH key1 depends on keys2
# --- read data
while (my $line = <DATA>) {
next if $line =~ m/^\s*$/; # ignore empty lines
next if $line =~ m/^\s*#/; # ignore comments
my ($pre,@posts) = split /\s+/, $line;
for my $post (@posts){
$depends{$post} //= {};
$depends{$pre}{$post}=1;
}
}
show("Input", \%depends);
#--- delete free elements (i.e. w/o dependencies)
my $loop_count;
my (@free,@result);
while ( @free = grep { ! %{ $depends{$_} } } keys %depends ) {
push @result, @free;
delete @depends{@free};
delete @$_{@free} for values %depends;
show("Phase: " . $loop_count++, \@free, \%depends);
}
# --- catch errors
die "Input corrupt! Check for circular dependencies in " . Dumper(\%de
+pends)
if (%depends);
show("Result",\@result);
sub show {
return unless DEBUG;
say "-"x10," ", shift;
pp $_ for @_;
}
__DATA__
# a depends on b
Cat Dog
Rooster Cat
Dog Donkey
DEBUG output:
/usr/bin/perl -w /home/lanx/perl/IPL/poset.pl
---------- Input
{
Cat => { Dog => 1 },
Dog => { Donkey => 1 },
Donkey => {},
Rooster => { Cat => 1 },
}
---------- Phase: 0
["Donkey"]
{ Cat => { Dog => 1 }, Dog => {}, Rooster => { Cat => 1 } }
---------- Phase: 1
["Dog"]
{ Cat => {}, Rooster => { Cat => 1 } }
---------- Phase: 2
["Cat"]
{ Rooster => {} }
---------- Phase: 3
["Rooster"]
{}
---------- Result
["Donkey", "Dog", "Cat", "Rooster"]
Cheers Rolf
( addicted to the Perl Programming Language)
UPDATE
minor cleanups in code