Topological sort/Extracted top item: Difference between revisions
Added 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 42:
* [[Topological sort]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<lang 11l>F _topx(data, tops, &_sofar) -> [[String]]
‘Recursive topological extractor’
_sofar [+]= copy(tops)
V depends = Set[String]()
L(top) tops
I top C data
depends.update(data[top])
I !depends.empty
_topx(data, depends, &_sofar)
[[String]] ordered
V accum = Set[String]()
L(i) (_sofar.len-1 .. 0).step(-1)
ordered [+]= sorted(Array(_sofar[i] - accum))
accum.update(_sofar[i])
R ordered
F toplevels(&data)
‘
Extract all top levels from dependency data
Top levels are never dependents
’
L(k, v) data
v.discard(k)
Set[String] dependents
L(k, v) data
dependents.update(v)
R Set(data.keys()) - dependents
F topx(&data, tops)
‘Extract the set of top-level(s) in topological order’
L(k, v) data
v.discard(k)
[Set[String]] _sofar
R _topx(data, tops, &_sofar)
F printorder(order)
‘Prettyprint topological ordering’
I !order.empty
print(‘First: ’order[0].map(s -> String(s)).join(‘, ’))
L(o) order[1..]
print(‘ Then: ’o.map(s -> String(s)).join(‘, ’))
V data = [
‘top1’ = Set([‘ip1’, ‘des1’, ‘ip2’]),
‘top2’ = Set([‘ip2’, ‘des1’, ‘ip3’]),
‘des1’ = Set([‘des1a’, ‘des1b’, ‘des1c’]),
‘des1a’ = Set([‘des1a1’, ‘des1a2’]),
‘des1c’ = Set([‘des1c1’, ‘extra1’]),
‘ip2’ = Set([‘ip2a’, ‘ip2b’, ‘ip2c’, ‘ipcommon’]),
‘ip1’ = Set([‘ip1a’, ‘ipcommon’, ‘extra1’])
]
V tops = toplevels(&data)
print(‘The top levels of the dependency graph are: ’Array(tops).join(‘ ’))
L(t) sorted(Array(tops))
print("\nThe compile order for top level: #. is...".format(t))
printorder(topx(&data, Set([t])))
I tops.len > 1
print("\nThe compile order for top levels: #. is...".format(sorted(Array(tops)).map(s -> String(s)).join(‘ and ’)))
printorder(topx(&data, tops))</lang>
{{out}}
<pre>
The top levels of the dependency graph are: top1 top2
The compile order for top level: top1 is...
First: des1a1, des1a2, des1c1, extra1
Then: des1a, des1b, des1c, ip1a, ip2a, ip2b, ip2c, ipcommon
Then: des1, ip1, ip2
Then: top1
The compile order for top level: top2 is...
First: des1a1, des1a2, des1c1, extra1
Then: des1a, des1b, des1c, ip2a, ip2b, ip2c, ipcommon
Then: des1, ip2, ip3
Then: top2
The compile order for top levels: top1 and top2 is...
First: des1a1, des1a2, des1c1, extra1
Then: des1a, des1b, des1c, ip1a, ip2a, ip2b, ip2c, ipcommon
Then: des1, ip1, ip2, ip3
Then: top1, top2
</pre>
=={{header|C}}==
| |||