Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Sort Algorithm (recursive?)

by bertigo (Novice)
on Oct 14, 2005 at 14:44 UTC ( #500240=perlquestion: print w/ replies, xml ) Need Help??
bertigo has asked for the wisdom of the Perl Monks concerning the following question:

Following a previous post Best way to sort these strings ? recursive way ? use Parse::RecDescent?, i want to obtain this output with the right order :

TEX1J desc 'Job Start' MEX1J desc 'Job 2' Pred TEX1J MEX2J desc 'Job end' Pred MEX1J, MEX2J # MEX1J must appear after TEX1J because it depend on TEX1J # MEX2J must appear after TEX1J and MEX1J from a hash defined like this: %hash={ 'MEX1J' => { 'desc' => 'Job 2' 'pred' => [TEX1J], }, 'MEX2J' => { 'desc' => 'Job end' 'pred' => [TEX1J,MEX1J], }, 'TEX1J' => { 'desc' => 'Job start' 'pred' => [], } }

I think I must use a recursive algorithm but I don't really see how to do it...

Thanks for the answer

Edited by planetscape - removed <pre> tags; replaced with <code>

Comment on Sort Algorithm (recursive?)
Download Code
Re: Sort Algorithm (recursive?)
by Perl Mouse (Chaplain) on Oct 14, 2005 at 15:17 UTC
    Ah, a topological sort. Which you can be reduced to sorting if there are no conflicting requirements. (Sometimes you can do a topological sort faster than an ordinary sort, but you never need more time than a regular sort).

    I'd preprocess the 'pred' arrays so I can faster search in them, after that, I'd do a regular sort:

    #!/usr/bin/perl use strict; use warnings; my %hash = ( MEX1J => { desc => 'Job 2', pred => [qw /TEX1J/], }, MEX2J => { desc => 'Job End', pred => [qw /TEX1J MEX1J/], }, TEX1J => { desc => 'Job start', pred => [], }, ); # # Preprocess, transform the 'pred' arrays into hashes. # while (my ($key, $value) = each %hash) { $value->{pred_h} = {map {($_, 1)} @{$value->{pred}}}; } # # Sort keys. # my @keys = sort {$hash{$b}{pred_h}{$a} ? -1 : $hash{$a}{pred_h}{$b} ? 1 : 0} keys %hash; # # Print keys. # print "$_\n" for @keys; __END__ TEX1J MEX1J MEX2J
    Note that you can write the sort block as:
    {$hash{$a}{pred_h}{$b} - $hash{$b}{pred_h}{$a}}
    but that's rather obscure, and you'd need to turn off warnings.
    Perl --((8:>*
      Doesn't work on
      my %hash=( 'MEX1J' => { desc => 'Job 2' , pred => ['TEX1J'], }, 'MEX2J' => { desc => 'Job end', pred => ['TROUBLE'], }, 'TEX1J' => { desc => 'Job start', pred => [], }, 'TROUBLE' => { desc => 'who cares', pred => ['MEX1J'] } );

      Caution: Contents may have been coded under pressure.
Re: Sort Algorithm (recursive?)
by merlyn (Sage) on Oct 14, 2005 at 15:19 UTC
Re: Sort Algorithm (recursive?)
by BrowserUk (Pope) on Oct 14, 2005 at 15:22 UTC

    This does the job for your simple case with the only recursion necessary is that embedded inside Perl's builtin sort.

    UpdateHowever, if your structure could have circular dependancies that are indirect--ie. A depends on B depends on C depends on A.--then this will not detect that.

    Making it more efficient is the next challenge, but maybe that doesn't matter if your hash is smallish.

    Updated to use @{} instead of $#{}. With thanks to Roy Johnson

    A somewhat more efficient version curtesy of the Orcish Manouver(?) and List::Util::first that avoids modifying your datastructure.

Re: Sort Algorithm (recursive?)
by Roy Johnson (Monsignor) on Oct 14, 2005 at 15:23 UTC
    For the general case, you'd need a recursive solution to traverse the pred lists. For this particular case, you don't have to worry about something being a pred-of-a-pred. I believe I have fixed the recursive section, as well.
    my %hash=( 'MEX1J' => { desc => 'Job 2' , pred => ['TEX1J'], }, 'MEX2J' => { desc => 'Job end', pred => ['TROUBLE'], }, 'TEX1J' => { desc => 'Job start', pred => [], }, 'TROUBLE' => { desc => 'who cares', pred => ['MEX1J'] } ); sub pred_cmp { my ($i1, $i2) = @_; # Anybody with no preds is first if (@{$hash{$i1}{pred}} == 0) { return -1; } elsif (@{$hash{$i2}{pred}} == 0) { return 1; } # If one is a pred of the other, it's first elsif (grep {$_ eq $i2} @{$hash{$i1}{pred}}) { return 1; } elsif (grep {$_ eq $i1} @{$hash{$i2}{pred}}) { return -1; } else { # Check recursively my ($rec) = grep $_, map {pred_cmp($_, $i2)} @{$hash{$i1}{pred +}}; if ($rec) { print "Returning $rec\n"; return $rec } ($rec) = grep $_, map {pred_cmp($i1, $_)} @{$hash{$i2}{pred}}; if ($rec) { print "Returning $rec\n"; return $rec } return 0; } } for (sort {pred_cmp($a,$b)} keys %hash) { print "$_\n"; }

    Caution: Contents may have been coded under pressure.
Re: Sort Algorithm (recursive?)
by dragonchild (Archbishop) on Oct 14, 2005 at 15:36 UTC
    Convert your HoH into an AoH. To do that, you need to create a second entry in your HoH that contains successors. So, your datastructure needs to look like:
    $hash={ 'MEX1J' => { 'desc' => 'Job 2' 'pred' => [TEX1J], 'succ' => [MEX2J], }, 'MEX2J' => { 'desc' => 'Job end' 'pred' => [TEX1J,MEX1J], 'succ' => [], }, 'TEX1J' => { 'desc' => 'Job start' 'pred' => [], 'succ' => [MEX2J], } }
    That way, you can start to build your job execution tree.

    Of course, I would build this using some sort of directed graph instead of a HoH. That way, predecessors and successors would be handled for you.


    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (5)
As of 2014-10-01 10:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (7 votes), past polls