Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Sorting by dependencies

by Anonymous Monk
on Apr 27, 2013 at 18:39 UTC ( #1031000=perlquestion: print w/ replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi

I have a list of jobs which need to be executed according to some dependencies.

for instance  @jobs =qw(A B C D E) and

A after D E after B B after C
should lead to a possible result:

qw(C B E D A)

How can I solve this in Perl? Unfortunately I cant assign a ranking value for sorting since the job list is very volatile.

And using sort {} didn't help with incomplete dependencies.

Thanks
Axel

Comment on Sorting by dependencies
Select or Download Code
Re: Sorting by dependencies
by moritz (Cardinal) on Apr 27, 2013 at 18:51 UTC

      Personally I'd go with Graph over Sort::Topological...

      use v5.12; use Graph; my @jobs = "A" .. "J"; my @rules = ( [qw/ A C /], # A before C [qw/ D B /], # D before B [qw/ J F /], # J before F [qw/ E J /], # E before J [qw/ I B /], # I before B ); my $g = "Graph"->new; $g->add_vertex($_) for @jobs; $g->add_edge(@$_) for @rules; say for $g->topological_sort;
      package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name
Re: Sorting by dependencies
by LanX (Canon) on Apr 27, 2013 at 19:07 UTC
    > 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

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

Re: Sorting by dependencies
by tobyink (Abbot) on Apr 27, 2013 at 19:07 UTC

    It's not a problem that is always solvable. Consider: @jobs = qw(A B) with rules "A after B" and "B after A".

    package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name

      I think that's what Rolf was talking about when he spoke about circular dependencies.

      You need to end up with (what we called in my IT studies, my translation into English might be faulty) a cycle-less oriented graph.

        In English and graph theory, they usually say "acyclic".
        لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
Re: Sorting by dependencies
by exilepanda (Monk) on Apr 28, 2013 at 05:40 UTC
    In project management, there's kind of model like this called "Critical Path" which intend to resolve dependency. Whatever approach you are trying to adopt, you want to consider these 2 situation

    A after B B after C C after A
    This is loop back. You might want to stop the user by saving this record. The dependency will never able to resolve.

    Lunch after Breakfast Dinner after Lunch Dinner after Breakfast
    There's no logical problem, however your presentation maybe going clumsy. You might want some mechanism for "normalization".

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1031000]
Approved by moritz
Front-paged by toolic
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (5)
As of 2014-08-22 06:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (148 votes), past polls