Re: Sorting by dependencies

[LanX]

> 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,

1. everything w/o dependencies can be excluded from the data
2. after exclusion loop again to 1
3. 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"]

UPDATE

minor cleanups in code