Topological sort: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 3,646: | Line 3,646: | ||
</lang> |
</lang> |
||
=={{header|Nim}}== |
|||
<lang Nim>import sequtils, strutils, sets, tables, sugar |
|||
type StringSet = HashSet[string] |
|||
proc topSort(data: var OrderedTable[string, StringSet]) = |
|||
## Topologically sort the data in place. |
|||
var ranks: Table[string, Natural] # Maps the keys to a rank. |
|||
# Remove self dependencies. |
|||
for key, values in data.mpairs: |
|||
values.excl key |
|||
# Add extra items (i.e items present in values but not in keys). |
|||
for values in toSeq(data.values): |
|||
for value in values: |
|||
if value notin data: |
|||
data[value] = initHashSet[string]() |
|||
# Find ranks. |
|||
var deps = data # Working copy of the table. |
|||
var rank = 0 |
|||
while deps.len > 0: |
|||
# Find a key with an empty dependency set. |
|||
var keyToRemove: string |
|||
for key, values in deps.pairs: |
|||
if values.card == 0: |
|||
keyToRemove = key |
|||
break |
|||
if keyToRemove.len == 0: |
|||
# Not found: there is a cycle. |
|||
raise newException(ValueError, "Unorderable items found: " & toSeq(deps.keys).join(", ")) |
|||
# Assign a rank to the key and remove it from keys and values. |
|||
ranks[keyToRemove] = rank |
|||
inc rank |
|||
deps.del keyToRemove |
|||
for k, v in deps.mpairs: |
|||
v.excl keyToRemove |
|||
# Sort the original data according to the ranks. |
|||
data.sort((x, y) => cmp(ranks[x[0]], ranks[y[0]])) |
|||
when isMainModule: |
|||
const Data = {"des_system_lib": ["std", "synopsys", "std_cell_lib", |
|||
"des_system_lib", "dw02", "dw01", |
|||
"ramlib", "ieee"].toHashSet, |
|||
"dw01": ["ieee", "dw01", "dware", "gtech"].toHashSet, |
|||
"dw02": ["ieee", "dw02", "dware"].toHashSet, |
|||
"dw03": ["std", "synopsys", "dware", "dw03", |
|||
"dw02", "dw01", "ieee", "gtech"].toHashSet, |
|||
"dw04": ["dw04", "ieee", "dw01", "dware", "gtech"].toHashSet, |
|||
"dw05": ["dw05", "ieee", "dware"].toHashSet, |
|||
"dw06": ["dw06", "ieee", "dware"].toHashSet, |
|||
"dw07": ["ieee", "dware"].toHashSet, |
|||
"dware": ["ieee", "dware"].toHashSet, |
|||
"gtech": ["ieee", "gtech"].toHashSet, |
|||
"ramlib": ["std", "ieee"].toHashSet, |
|||
"std_cell_lib": ["ieee", "std_cell_lib"].toHashSet, |
|||
"synopsys": initHashSet[string]()}.toOrderedTable |
|||
# Process the original data (without cycle). |
|||
echo "Data without cycle. Order after sorting:" |
|||
var data = Data |
|||
try: |
|||
data.topSort() |
|||
for key in data.keys: echo key |
|||
except ValueError: |
|||
echo getCurrentExceptionMsg() |
|||
# Process the modified data (with a cycle). |
|||
echo "\nData with a cycle:" |
|||
data = Data |
|||
data["dw01"].incl "dw04" |
|||
try: |
|||
data.topSort() |
|||
for key in data.keys: echo key |
|||
except ValueError: |
|||
echo getCurrentExceptionMsg()</lang> |
|||
=={{header|Object Pascal}}== |
=={{header|Object Pascal}}== |