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

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

Replies are listed 'Best First'.
Re: Sort Algorithm (recursive?)
by merlyn (Sage) on Oct 14, 2005 at 15:19 UTC
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 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 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?
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.