Topological sort: Difference between revisions
→{{header|Perl}}: Added Perl 5 solution
(→{{header|Perl}}: Added Perl 5 solution) |
|||
Line 850:
des_system_lib dw03 dw04
</pre>
=={{header|Perl}}==
In July 2002, [http://perlgolf.sourceforge.net/TPR/0/4b/ Topological Sort] was the monthly [http://perlgolf.sourceforge.net/ Perl Golf] course. The [http://perlgolf.sourceforge.net/cgi-bin/PGAS/post_mortem.cgi?id=6 post-mortem] contains many solutions. This code was adapted from the solution that scored 144.39.
The algorithm used allows the output to be clustered; libraries on the same line are all independent (given the building of any previous lines of libraries), and so could be built in parallel.
<lang perl>sub print_topo_sort {
my %deps = @_;
my %ba;
while ( my ( $before, $afters_aref ) = each %deps ) {
for my $after ( @{ $afters_aref } ) {
$ba{$before}{$after} = 1 if $before ne $after;
$ba{$after} ||= {};
}
}
while ( my @afters = sort grep { ! %{ $ba{$_} } } keys %ba ) {
print "@afters\n";
delete @ba{@afters};
delete @{$_}{@afters} for values %ba;
}
print !!%ba ? "Cycle found! ". join( ' ', sort keys %ba ). "\n" : "---\n";
}
my %deps = (
des_system_lib => [qw( std synopsys std_cell_lib des_system_lib dw02
dw01 ramlib ieee )],
dw01 => [qw( ieee dw01 dware gtech )],
dw02 => [qw( ieee dw02 dware )],
dw03 => [qw( std synopsys dware dw03 dw02 dw01 ieee gtech )],
dw04 => [qw( dw04 ieee dw01 dware gtech )],
dw05 => [qw( dw05 ieee dware )],
dw06 => [qw( dw06 ieee dware )],
dw07 => [qw( ieee dware )],
dware => [qw( ieee dware )],
gtech => [qw( ieee gtech )],
ramlib => [qw( std ieee )],
std_cell_lib => [qw( ieee std_cell_lib )],
synopsys => [qw( )],
);
print_topo_sort(%deps);
push @{ $deps{'dw01'} }, 'dw04'; # Add unresolvable dependency
print_topo_sort(%deps);</lang>
Output:<pre>ieee std synopsys
dware gtech ramlib std_cell_lib
dw01 dw02 dw05 dw06 dw07
des_system_lib dw03 dw04
---
ieee std synopsys
dware gtech ramlib std_cell_lib
dw02 dw05 dw06 dw07
Cycle found! des_system_lib dw01 dw03 dw04</pre>
=={{header|PicoLisp}}==
Line 884 ⟶ 939:
(synopsys) ) )
-> (std synopsys ieee std-cell-lib ramlib dware dw02 gtech dw01 des-system-lib dw03 dw04 dw05 dw06 dw07)</pre>
=={{header|PowerShell}}==
<lang PowerShell>#Input Data
| |||