Topological sort: Difference between revisions

Content added Content deleted

Inline

@@ Line 52: / Line 52: @@
 [http://www.embeddedrelated.com/showarticle/799.php "Ten little algorithms, part 4: topological sort"] </ref>
 <br><br>
+=={{header|11l}}==
+{{trans|Python}}
+<lang 11l>V data = [
+   ‘des_system_lib’ = Set(‘std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee’.split(‘ ’)),
+   ‘dw01’           = Set(‘ieee dw01 dware gtech’.split(‘ ’)),
+   ‘dw02’           = Set(‘ieee dw02 dware’.split(‘ ’)),
+   ‘dw03’           = Set(‘std synopsys dware dw03 dw02 dw01 ieee gtech’.split(‘ ’)),
+   ‘dw04’           = Set(‘dw04 ieee dw01 dware gtech’.split(‘ ’)),
+   ‘dw05’           = Set(‘dw05 ieee dware’.split(‘ ’)),
+   ‘dw06’           = Set(‘dw06 ieee dware’.split(‘ ’)),
+   ‘dw07’           = Set(‘ieee dware’.split(‘ ’)),
+   ‘dware’          = Set(‘ieee dware’.split(‘ ’)),
+   ‘gtech’          = Set(‘ieee gtech’.split(‘ ’)),
+   ‘ramlib’         = Set(‘std ieee’.split(‘ ’)),
+   ‘std_cell_lib’   = Set(‘ieee std_cell_lib’.split(‘ ’)),
+   ‘synopsys’       = Set[String]()
+]
+F toposort2(&data)
+   L(k, v) data
+      v.discard(k)
+   Set[String] extra_items_in_deps
+   L(v) data.values()
+      extra_items_in_deps.update(v)
+   extra_items_in_deps = extra_items_in_deps - Set(data.keys())
+   L(item) extra_items_in_deps
+      data[item] = Set[String]()
+   [String] r
+   L
+      Set[String] ordered
+      L(item, dep) data
+         I dep.empty
+            ordered.add(item)
+      I ordered.empty
+         L.break
+      r.append(sorted(Array(ordered)).join(‘ ’))
+      [String = Set[String]] new_data
+      L(item, dep) data
+         I item !C ordered
+            new_data[item] = dep - ordered
+      data = move(new_data)
+   assert(data.empty, ‘A cyclic dependency exists’)
+   R r
+print(toposort2(&data).join("\n"))</lang>
+{{out}}
+<pre>
+ieee std synopsys
+dware gtech ramlib std_cell_lib
+dw01 dw02 dw05 dw06 dw07
+des_system_lib dw03 dw04
+</pre>
 =={{header|Ada}}==