How to resolve the algorithm Topological sort step by step in the Tcl programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Topological sort step by step in the Tcl programming language
Table of Contents
Problem Statement
Given a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon. The compiling of a library in the VHDL language has the constraint that a library must be compiled after any library it depends on. A tool exists that extracts library dependencies.
Write a function that will return a valid compile order of VHDL libraries from their dependencies.
Use the following data as an example:
Note: the above data would be un-orderable if, for example, dw04 is added to the list of dependencies of dw01.
There are two popular algorithms for topological sorting:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Topological sort step by step in the Tcl programming language
Source code in the tcl programming language
package require Tcl 8.5
proc topsort {data} {
# Clean the data
dict for {node depends} $data {
if {[set i [lsearch -exact $depends $node]] >= 0} {
set depends [lreplace $depends $i $i]
dict set data $node $depends
}
foreach node $depends {dict lappend data $node}
}
# Do the sort
set sorted {}
while 1 {
# Find available nodes
set avail [dict keys [dict filter $data value {}]]
if {![llength $avail]} {
if {[dict size $data]} {
error "graph is cyclic, possibly involving nodes \"[dict keys $data]\""
}
return $sorted
}
# Note that the lsort is only necessary for making the results more like other langs
lappend sorted {*}[lsort $avail]
# Remove from working copy of graph
dict for {node depends} $data {
foreach n $avail {
if {[set i [lsearch -exact $depends $n]] >= 0} {
set depends [lreplace $depends $i $i]
dict set data $node $depends
}
}
}
foreach node $avail {
dict unset data $node
}
}
}
set inputData {
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
}
foreach line [split $inputData \n] {
if {[string trim $line] eq ""} continue
dict set parsedData [lindex $line 0] [lrange $line 1 end]
}
puts [topsort $parsedData]
You may also check:How to resolve the algorithm Longest common subsequence step by step in the Wren programming language
You may also check:How to resolve the algorithm Empty string step by step in the Prolog programming language
You may also check:How to resolve the algorithm Sudoku step by step in the Wren programming language
You may also check:How to resolve the algorithm Selectively replace multiple instances of a character within a string step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Musical scale step by step in the Lilypond programming language