How to resolve the algorithm Topological sort step by step in the REXX programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Topological sort step by step in the REXX 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 REXX programming language
Source code in the rexx programming language
/*REXX pgm does a topological sort (orders such that no item precedes a dependent item).*/
iDep.= 0; iPos.= 0; iOrd.= 0 /*initialize some stemmed arrays to 0.*/
nL= 15; nd= 44; nc= 69 /* " " "parms" and indices.*/
label= 'DES_SYSTEM_LIB DW01 DW02 DW03 DW04 DW05 DW06 DW07' ,
'DWARE GTECH RAMLIB STD_CELL_LIB SYNOPSYS STD IEEE'
iCode= 1 14 13 12 1 3 2 11 15 0 2 15 2 9 10 0 3 15 3 9 0 4 14 213 9 4 3 2 15 10 0 5 5 15 ,
2 9 10 0 6 6 15 9 0 7 7 15 9 0 8 15 9 0 39 15 9 0 10 15 10 0 11 14 15 0 12 15 12 0 0
j= 0
do i=1
iL= word(iCode, i); if iL==0 then leave
do forever; i= i+1
iR= word(iCode, i); if iR==0 then leave
j= j+1; iDep.j.1= iL
iDep.j.2= iR
end /*forever*/
end /*i*/
call tSort
say '═══compile order═══'
@= 'libraries found.)'
#=0; do o=nO by -1 for nO; #= #+1; say word(label, iOrd.o)
end /*o*/; if #==0 then #= 'no'
say ' ('# @; say
say '═══unordered libraries═══'
#=0; do u=nO+1 to nL; #= #+1; say word(label, iOrd.u)
end /*u*/; if #==0 then #= 'no'
say ' ('# "unordered" @
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
tSort: procedure expose iDep. iOrd. iPos. nd nL nO
do i=1 for nL; iOrd.i= i; iPos.i= i
end /*i*/
k= 1
do until k<=j; j = k; k= nL+1
do i=1 for nd; iL = iDep.i.1; iR= iPos.iL
ipL= iPos.iL; ipR= iPos.iR
if iL==iR | ipL>.k | ipL
k= k-1
_= iOrd.k; iPos._ = ipL
iPos.iL= k
iOrd.ipL= iOrd.k; iOrd.k = iL
end /*i*/
end /*until*/
nO= j-1; return
You may also check:How to resolve the algorithm Factorial step by step in the Emacs Lisp programming language
You may also check:How to resolve the algorithm Summarize and say sequence step by step in the Julia programming language
You may also check:How to resolve the algorithm OpenWebNet password step by step in the C++ programming language
You may also check:How to resolve the algorithm File extension is in extensions list step by step in the Sidef programming language
You may also check:How to resolve the algorithm Primorial numbers step by step in the Ruby programming language