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