Topological sort: Difference between revisions
Content added Content deleted
(Add Tailspin solution) |
|||
Line 5,754: | Line 5,754: | ||
<pre>["ieee", "std_cell_lib", "gtech", "dware", "dw07", "dw06", "dw05", "dw02", "dw01", "dw04", "std", "ramlib", "synopsys", "dw03", "des_system_lib"]</pre> |
<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}}== |
=={{header|Tcl}}== |