http://www.perlmonks.org?node_id=1031000

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

[download]
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

Replies are listed 'Best First'.
Re: Sorting by dependencies
by LanX (Saint) 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
    Read more... (1461 Bytes)

    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"]

    [download]

    Cheers Rolf

    ( addicted to the Perl Programming Language)

    UPDATE
    minor cleanups in code
[reply]
[d/l]
[select]
      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

      [download]
      Thanks
      Axel
[reply]
[d/l]
        > 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)

[reply]
[d/l]
[select]
Re: Sorting by dependencies
by moritz (Cardinal) on Apr 27, 2013 at 18:51 UTC
[reply]

      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;

      [download]
      package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name
[reply]
[d/l]
Re: Sorting by dependencies
by tobyink (Canon) 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
[reply]
[d/l]

      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.

[reply]
        In English and graph theory, they usually say "acyclic".
        لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
[reply]
Re: Sorting by dependencies
by exilepanda (Friar) 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

    [download]
    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

    [download]
    There's no logical problem, however your presentation maybe going clumsy. You might want some mechanism for "normalization".
[reply]
[d/l]
[select]

Back to Seekers of Perl Wisdom