Rosetta Code

Topological sort: Difference between revisions

Page Discussion

Topological sort (view source)

Revision as of 11:14, 20 May 2021

13,941 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 4,385:
=={{header|Phix}}==
Implemented as a trivial normal sort.
<!--<lang Phix>sequence names(phixonline)-->
<span style="color: #004080;">sequence</span> <span style="color: #000000;">names</span>
enum RANK, NAME, DEP -- content of names
<span style="color: #008080;">enum</span> <span style="color: #000000;">RANK</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NAME</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">DEP</span> <span style="color: #000080;font-style:italic;">-- content of names
-- rank is 1 for items to compile first, then 2, etc,
-- rank is 1 for items to compile first, then 2, etc,
-- or 0 if cyclic dependencies prevent compilation.
-- or 0 if cyclic dependencies prevent compilation.
-- name is handy, and makes the result order alphabetic!
-- name is handy, and makes the result order alphabetic!
-- dep is a list of dependencies (indexes to other names)
-- dep is a list of dependencies (indexes to other names)</span>
 
function add_dependency(string name)
<span style="color: #008080;">function</span> <span style="color: #000000;">add_dependency</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">)</span>
integer k = find(name,vslice(names,NAME))
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">vslice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">,</span><span style="color: #000000;">NAME</span><span style="color: #0000FF;">))</span>
if k=0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
names = append(names,{0,name,{}})
<span style="color: #000000;">names</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,{}})</span>
k = length(names)
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return k
<span style="color: #008080;">return</span> <span style="color: #000000;">k</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
procedure topsort(string input)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">)</span>
names = {}
<span style="color: #000000;">names</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
sequence lines = split(input,'\n')
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
for i=1 to length(lines) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
sequence line = split(lines[i]),
<span style="color: #004080;">sequence</span> <span style="color: #000000;">line</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),</span>
dependencies = {}
<span style="color: #000000;">dependencies</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
integer k = add_dependency(line[1])
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_dependency</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
for j=2 to length(line) do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer l = add_dependency(line[j])
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_dependency</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
if l!=k then -- ignore self-references
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">k</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- ignore self-references</span>
dependencies &= l
<span style="color: #000000;">dependencies</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">l</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
names[k][DEP] = dependencies
<span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DEP</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dependencies</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
 
-- Now populate names[RANK] iteratively:
<span style="color: #000080;font-style:italic;">-- Now populate names[RANK] iteratively:</span>
bool more = true
<span style="color: #004080;">bool</span> <span style="color: #000000;">more</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
integer rank = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">rank</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
while more do
<span style="color: #008080;">while</span> <span style="color: #000000;">more</span> <span style="color: #008080;">do</span>
more = false
<span style="color: #000000;">more</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
rank += 1
<span style="color: #000000;">rank</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
for i=1 to length(names) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if names[i][RANK]=0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
bool ok = true
<span style="color: #004080;">bool</span> <span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
for j=1 to length(names[i][DEP]) do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DEP</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
integer ji = names[i][DEP][j],
<span style="color: #004080;">integer</span> <span style="color: #000000;">ji</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DEP</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span>
nr = names[ji][RANK]
<span style="color: #000000;">nr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ji</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span>
if nr=0 or nr=rank then
<span style="color: #008080;">if</span> <span style="color: #000000;">nr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">nr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rank</span> <span style="color: #008080;">then</span>
-- not yet compiled, or same pass
ok <span style="color: #000080;font-style:italic;">-- not yet compiled, or same falsepass</span>
<span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
exit
end if <span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if ok then
<span style="color: #008080;">if</span> <span style="color: #000000;">ok</span> <span style="color: #008080;">then</span>
names[i][RANK] = rank
<span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rank</span>
more = true
<span style="color: #000000;">more</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 
names = sort(names) -- (ie by [RANK=1] then [NAME=2])
<span style="color: #000000;">names</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (ie by [RANK=1] then [NAME=2])</span>
integer prank = names[1][RANK]
<span style="color: #004080;">integer</span> <span style="color: #000000;">prank</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span>
if prank=0 then puts(1,"** CYCLIC **:") end if
<span style="color: #008080;">if</span> <span style="color: #000000;">prank</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"** CYCLIC **:"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for i=1 to length(names) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">names</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
rank = names[i][RANK]
<span style="color: #000000;">rank</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span>
if i>1 then
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
puts(1,iff(rank=prank?" ":"\n"))
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rank</span><span style="color: #0000FF;">=</span><span style="color: #000000;">prank</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
puts(1,names[i][NAME])
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">names</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NAME</span><span style="color: #0000FF;">])</span>
prank = rank
<span style="color: #000000;">prank</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rank</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
puts(1,"\n")
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
 
constant input = """
<span style="color: #008080;">constant</span> <span style="color: #000000;">input</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee
dw01 ieee dw01 dware gtech
dw02 dw01 ieee dw02dw01 dware gtech
dw03 dw02 stdieee synopsysdw02 dware dw03 dw02 dw01 ieee gtech
dw04 dw03 dw04std ieeesynopsys dware dw03 dw02 dw01 dwareieee gtech
dw05 dw04 dw05dw04 ieee dw01 dware gtech
dw06 dw05 dw06dw05 ieee dware
dw07 dw06 dw06 ieee dware
dware dw07 ieee dware
gtech dware ieee gtechdware
ramlib gtech std ieee gtech
ramlib std ieee
std_cell_lib ieee std_cell_lib
std_cell_lib ieee std_cell_lib
synopsys"""
synopsys"""</span>
 
topsort(input)
<span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">)</span>
puts(1,"\nbad input:\n")
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nbad input:\n"</span><span style="color: #0000FF;">)</span>
topsort(input&"\ndw01 dw04")</lang>
<span style="color: #000000;">topsort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">input</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"\ndw01 dw04"</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
Items on the same line can be compiled at the same time, and each line is alphabetic.
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/118361"