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

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
> 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

In reply to Re: Sorting by dependencies by LanX
in thread Sorting by dependencies by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others contemplating the Monastery: (7)
    As of 2014-09-18 23:13 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (126 votes), past polls