Anonymous user
Topological sort: Difference between revisions
Add Tailspin solution
(Add Tailspin solution) |
|||
Line 5,754:
<pre>["ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", "dw02", "dw01", "dw04", "std", "ramlib", "synopsys", "dw03", "des_system_lib"]</pre>
=={{header|Tailspin}}==
<lang tailspin>
data node <'.+'>, from <node>, to <node>
templates topologicalSort
@: [];
{V: {|$.v..., $.e({node: §.to})...|} , E: {|$.e... -> \(<{from: <~=$.to>}> $! \)|}} -> #
when <{V: <?($::count <=0>)>}> $@!
otherwise
def independent: ($.V notMatching $.E({node: §.from}));
[$independent... -> $.node] -> ..|@: $;
{V: ($.V notMatching $independent), E: ($.E notMatching $independent({to: §.node}))}
-> \(<?($independent::count <1..>)> $! \) -> #
end topologicalSort
composer lines
[<line>+]
rule line: <'[^\n]*'> (<'\n'>)
end lines
templates collectDeps
@: { v: [], e: []};
composer depRecord
(<WS>? def node: <~WS>; <WS>? <dep>* <WS>? $node -> ..|@collectDeps.v: {node: $};)
rule dep: (<~WS> -> ..|@collectDeps.e: {from: $node, to: $}; <WS>?)
end depRecord
$(3..last)... -> !depRecord
$@!
end collectDeps
'LIBRARY LIBRARY DEPENDENCIES
======= ====================
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01 ieee dw01 dware gtech
dw02 ieee dw02 dware
dw03 std synopsys dware dw03 dw02 dw01 ieee gtech
dw04 dw04 ieee dw01 dware gtech
dw05 dw05 ieee dware
dw06 dw06 ieee dware
dw07 ieee dware
dware ieee dware
gtech ieee gtech
ramlib std ieee
std_cell_lib ieee std_cell_lib
synopsys
' -> lines -> collectDeps -> topologicalSort -> !OUT::write
</lang>
{{out}}
<pre>
[[std, synopsys, ieee], [ramlib, dware, std_cell_lib, gtech], [dw01, dw02, dw05, dw06, dw07], [dw03, dw04, des_system_lib]]
</pre>
=={{header|Tcl}}==
| |||