The fundamental problem (as noted in other threads) is that we only have a partial ordering on the set, i.e. some pairs of nodes don't satisfy (a <= b or a => b). My sort comparator returns equal for such pairs (e.g. two root nodes) which breaks the sorting algo, as you noted.
perldoc -f sort says: "The comparison function is required to behave. If it returns inconsistent results (sometimes saying $x1 is less than $x2 and sometimes saying the opposite, for example) the results are not well-defined." My comparator was badly-behaved for different reason. It doesn't satisfy transitivity: i.e. a == b && b == c does not imply a == c.
As well as CPAN's Graph module, there is slightly more direct Sort::Topological which appears to do the job (in essentially the same way the other code posted appears to do it - associate a depth and sort on that).
(Side note: if testing other approaches, note that your example list is already sorted - the first three elts are all root nodes). In the code below, I've reversed the dependency, so that the fourth depends on the second.)
#!/usr/bin/perl use strict; use warnings; use Sort::Topological qw/toposort/; use Class::Struct Item => { id => '$', deps => '@', }; my @items; push @items, Item->new(id => $_) for 1..4; # Make $items[1] a rank 'deeper', so it should sort last $items[3]->deps([$items[1]]); map { print "id: ", $_->id, "\n" } @items; # 1, 2, 3, 4 @items = toposort(sub { my $i = shift; @{$i->deps}; }, \@items); map { print "id: ", $_->id, "\n" } @items; # 1, 3, 4, 2
In reply to Re^3: Partial sort for dependency graph
by jbert
in thread Partial sort for dependency graph
by throop
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |