### Re: Sorting by dependencies

by LanX (Canon)
 on Apr 27, 2013 at 19:07 UTC ( #1031003=note: print w/ replies, xml ) Need Help??

in reply to Sorting by dependencies

> 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

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

Comment on Re: Sorting by dependencies
Replies are listed 'Best First'.
Re^2: Sorting by dependencies
by Anonymous Monk on Apr 27, 2013 at 21:11 UTC
Thanks everybody for the detailed help.

Especially LanX' version is great, basically 6 lines of codes are doing the job and validating the input at the same time.

Thanks a lot!!!

Just one more question:

Is it possible to combine different types of rules in this algorithm?

```A not after B"
B after C
Thanks
Axel
> Is it possible to combine different types of rules in this algorithm?

Well not A > B is equivalent to B >= A.

But the B == A part - i.e. B and A belong to the same phase - must be ignored, otherwise one risks that A comes after B in the unsorted output of a phase.

So translating to B > A should be safe, w/o loss of solutions.

Just modify the parser to translate different rules accordingly.

HTH! =)

Cheers Rolf

( addicted to the Perl Programming Language)

Create A New User
Node Status?
node history
Node Type: note [id://1031003]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (14)
As of 2015-08-04 12:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?