Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

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


Comment on Re: Sorting by dependencies
Select or Download Code
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)

Log In?
Username:
Password:

What's my password?
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 imbibing at the Monastery: (14)
As of 2014-07-29 17:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (224 votes), past polls