Anonymous user
Topological sort/Extracted top item: Difference between revisions
Topological sort/Extracted top item (view source)
Revision as of 17:12, 17 January 2019
, 5 years ago→{{header|Perl 6}}
Line 525:
Compile order for ip1: [extra1, ipcommon, ip1a, ip1]
</pre>
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw( uniq );
my $deps = <<END;
top1 des1 ip1 ip2
top2 des1 ip2 ip3
ip1 extra1 ip1a ipcommon
ip2 ip2a ip2b ip2c ipcommon
des1 des1a des1b des1c
des1a des1a1 des1a2
des1c des1c1 extra1
END
sub before
{
map { $deps =~ /^$_\b(.+)/m ? before( split ' ', $1 ) : (), $_ } @_
}
1 while $deps =~ s/^(\w+)\b.*?\K\h+\1\b//gm; # remove self dependencies
print "TOP LEVELS: @{[grep $deps !~ /\h$_\b/, $deps =~ /^\w+/gm]}\n";
print "\nTARGET $_ ORDER: @{[ uniq before split ]}\n"
for $deps =~ /^\w+/gm, 'top1 top2';</lang>
{{out}}
<pre>
TOP LEVELS: top1 top2
TARGET top1 ORDER: des1a1 des1a2 des1a des1b des1c1 extra1 des1c des1 ip1a ipcommon ip1 ip2a ip2b ip2c ip2 top1
TARGET top2 ORDER: des1a1 des1a2 des1a des1b des1c1 extra1 des1c des1 ip2a ip2b ip2c ipcommon ip2 ip3 top2
TARGET ip1 ORDER: extra1 ip1a ipcommon ip1
TARGET ip2 ORDER: ip2a ip2b ip2c ipcommon ip2
TARGET des1 ORDER: des1a1 des1a2 des1a des1b des1c1 extra1 des1c des1
TARGET des1a ORDER: des1a1 des1a2 des1a
TARGET des1c ORDER: des1c1 extra1 des1c
TARGET top1 top2 ORDER: des1a1 des1a2 des1a des1b des1c1 extra1 des1c des1 ip1a ipcommon ip1 ip2a ip2b ip2c ip2 top1 ip3 top2
</pre>
Line 619 ⟶ 666:
top1 top2
</pre>
=={{header|Phix}}==
Minor tweaks to the Topological_sort code: top_levels, propagate() and -1 now means "not required".
| |||