Topological sort
You are encouraged to solve this task according to the task description, using any language you may know.
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. The task is to write a function that will return a valid compile order of VHDL libraries from their dependencies.
- Assume library names are single words.
- Items mentioned as only dependants, (sic), have no dependants of their own, but their order of compiling must be given.
- Any self dependencies should be ignored.
- Any un-orderable dependencies should be flagged.
Use the following data as an example:
LIBRARY LIBRARY DEPENDENCIES ======= ==================== des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib synopsys
Note: the above data would be un-orderable if, for example, dw04
is added to the list of dependencies of dw01
.
Clojure
Here is a quick implementation in Clojure, developed at Java Posse Roundup 2010 in collaboration with Fred Simon, with a bit of subsequent simplification by Joel Neely.
Dependencies are represented by a map from each item to the set of items on which it depends. The first function (dep
), builds a dependency map for a single item.
The next few functions (empty-dep
, pair-dep
, default-deps
, declared-deps
, and deps
) are used to construct the map from a list that alternates items with lists of their dependencies.
The next three functions (no-dep-items
, remove-items
, and topo-sort-deps
) are the core of the topological sort algorithm, which iteratively removes items with no remaining dependencies from the map and "stacks" them onto the result. When the map becomes empty the reversed result is returned. If no dependency-free items can be found, then any non-empty remainder of the map contains cycles.
The last function (topo-sort
) is simply a helper which applies topo-sort-deps
to a dependency map constructed from the item-and-list-of-dependencies input list.
Implementation
<lang clojure>(use 'clojure.set) (use 'clojure.contrib.seq-utils)
(defn dep
"Constructs a single-key dependence, represented as a map from item to a set of items, ensuring that item is not in the set." [item items] {item (difference (set items) (list item))})
(defn empty-dep
"Constructs a single-key dependence from item to an empty set." [item] (dep item '()))
(defn pair-dep
"Invokes dep after destructuring item and items from the argument." item items (dep item items))
(defn default-deps
"Constructs a default dependence map taking every item in the argument to an empty set" [items] (apply merge-with union (map empty-dep (flatten items))))
(defn declared-deps
"Constructs a dependence map from a list containaining alternating items and list of their predecessor items." [items] (apply merge-with union (map pair-dep (partition 2 items))))
(defn deps
"Constructs a full dependence map containing both explicitly represented dependences and default empty dependences for items without explicit predecessors." [items] (merge (default-deps items) (declared-deps items)))
(defn no-dep-items
"Returns all keys from the argument which have no (i.e. empty) dependences." [deps] (filter #(empty? (deps %)) (keys deps)))
(defn remove-items
"Returns a dependence map with the specified items removed from keys and from all dependence sets of remaining keys." [deps items] (let [items-to-remove (set items) remaining-keys (difference (set (keys deps)) items-to-remove) remaining-deps (fn [x] (dep x (difference (deps x) items-to-remove)))] (apply merge (map remaining-deps remaining-keys))))
(defn topo-sort-deps
"Given a dependence map, returns either a list of items in which each item follows all of its predecessors, or a string showing the items among which there is a cyclic dependence preventing a linear order." [deps] (loop [remaining-deps deps result '()] (if (empty? remaining-deps) (reverse result) (let [ready-items (no-dep-items remaining-deps)] (if (empty? ready-items) (str "ERROR: cycles remain among " (keys remaining-deps)) (recur (remove-items remaining-deps ready-items) (concat ready-items result)))))))
(defn topo-sort
"Given a list of alternating items and predecessor lists, constructs a full dependence map and then applies topo-sort-deps to that map." [items] (topo-sort-deps (deps items)))
</lang>
Examples of sortable and non-sortable data:
<lang clojure>(def good-sample
'(:des_system_lib (:std :synopsys :std_cell_lib :des_system_lib :dw02 :dw01 :ramlib :ieee) :dw01 (:ieee :dw01 :dware :gtech) :dw02 (:ieee :dw02 :dware) :dw03 (:std :synopsys :dware :dw03 :dw02 :dw01 :ieee :gtech) :dw04 (:dw04 :ieee :dw01 :dware :gtech) :dw05 (:dw05 :ieee :dware) :dw06 (:dw06 :ieee :dware) :dw07 (:ieee :dware) :dware (:ieee :dware) :gtech (:ieee :gtech) :ramlib (:std :ieee) :std_cell_lib (:ieee :std_cell_lib) :synopsys ()))
(def cyclic-dependence
'(:dw01 (:dw04)))
(def bad-sample
(concat cyclic-dependence good-sample))</lang>
Output
<lang clojure>Clojure 1.1.0 1:1 user=> #<Namespace topo> 1:2 topo=> (topo-sort good-sample) (:std :synopsys :ieee :gtech :ramlib :dware :std_cell_lib :dw07 :dw06 :dw05 :dw01 :dw02 :des_system_lib :dw03 :dw04) 1:3 topo=> (topo-sort bad-sample) "ERROR: cycles remain among (:dw01 :dw04 :dw03 :des_system_lib)"</lang>
Common Lisp
<lang lisp>(defun topological-sort (graph &key (test 'eql))
"Graph is an association list whose keys are objects and whose
values are lists of objects on which the corresponding key depends. Test is used to compare elements, and should be a suitable test for hash-tables. Topological-sort returns two values. The first is a list of objects sorted toplogically. The second is a boolean indicating whether all of the objects in the input graph are present in the topological ordering (i.e., the first value)."
(let ((entries (make-hash-table :test test))) (flet ((entry (vertex) "Return the entry for vertex. Each entry is a cons whose car is the number of outstanding dependencies of vertex and whose cdr is a list of dependants of vertex." (multiple-value-bind (entry presentp) (gethash vertex entries) (if presentp entry (setf (gethash vertex entries) (cons 0 '())))))) ;; populate entries initially (dolist (vertex graph) (destructuring-bind (vertex &rest dependencies) vertex (let ((ventry (entry vertex))) (dolist (dependency dependencies) (let ((dentry (entry dependency))) (unless (funcall test dependency vertex) (incf (car ventry)) (push vertex (cdr dentry)))))))) ;; L is the list of sorted elements, and S the set of vertices ;; with no outstanding dependencies. (let ((L '()) (S (loop for entry being each hash-value of entries using (hash-key vertex) when (zerop (car entry)) collect vertex))) ;; Until there are no vertices with no outstanding dependencies, ;; process vertices from S, adding them to L. (do* () ((endp S)) (let* ((v (pop S)) (ventry (entry v))) (remhash v entries) (dolist (dependant (cdr ventry) (push v L)) (when (zerop (decf (car (entry dependant)))) (push dependant S))))) ;; return (1) the list of sorted items, (2) whether all items ;; were sorted, and (3) if there were unsorted vertices, the ;; hash table mapping these vertices to their dependants (let ((all-sorted-p (zerop (hash-table-count entries)))) (values (nreverse L) all-sorted-p (unless all-sorted-p entries)))))))</lang>
Provided example in which all items can be sorted:
<lang lisp>> (defparameter *dependency-graph*
'((des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee) (dw01 ieee dw01 dware gtech) (dw02 ieee dw02 dware) (dw03 std synopsys dware dw03 dw02 dw01 ieee gtech) (dw04 dw04 ieee dw01 dware gtech) (dw05 dw05 ieee dware) (dw06 dw06 ieee dware) (dw07 ieee dware) (dware ieee dware) (gtech ieee gtech) (ramlib std ieee) (std-cell-lib ieee std-cell-lib) (synopsys)))
- DEPENDENCY-GRAPH*
> (topological-sort *dependency-graph*) (IEEE DWARE DW02 DW05 DW06 DW07 GTECH DW01 DW04 STD-CELL-LIB SYNOPSYS STD DW03 RAMLIB DES-SYSTEM-LIB) T NIL</lang>
Provided example with dw04
added to the dependencies of dw01
. Some vertices are ordered, but the second return is nil
, indicating that not all vertices could be sorted. The third return value is the hash table containing entries for the four vertices that couldn't be sorted. (The variable /
stores the list of values produced by the last form, and describe
prints information about an object.)
<lang lisp>> (defparameter *dependency-graph*
'((des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee) (dw01 ieee dw01 dw04 dware gtech) (dw02 ieee dw02 dware) (dw03 std synopsys dware dw03 dw02 dw01 ieee gtech) (dw04 dw04 ieee dw01 dware gtech) (dw05 dw05 ieee dware) (dw06 dw06 ieee dware) (dw07 ieee dware) (dware ieee dware) (gtech ieee gtech) (ramlib std ieee) (std-cell-lib ieee std-cell-lib) (synopsys)))
- DEPENDENCY-GRAPH*
> (topological-sort *dependency-graph*) (IEEE DWARE DW02 DW05 DW06 DW07 GTECH STD-CELL-LIB SYNOPSYS STD RAMLIB) NIL
- <EQL Hash Table{4} 200C9023>
> (describe (third /))
- <EQL Hash Table{4} 200C9023> is a HASH-TABLE
DW01 (1 DW04 DW03 DES-SYSTEM-LIB) DW04 (1 DW01) DW03 (1) DES-SYSTEM-LIB (1)</lang>
D
<lang d>import std.stdio ; import std.string ; import std.algorithm ; import std.array ;
alias string[][string] DEPType ;
U[V] aadup(U, V)(U[V] aa) {
U[V] bb ; foreach(k,v;aa) bb[k] = v ; return bb ;
}
string pp(DEPType d) {
string s ; foreach(k;d.keys.sort) s ~= format(" %s => %s\n", k, d[k]) ; return s ;
}
string[][] toposort(DEPType d) {
foreach(k, v ; d) d[k] = array(filter!((string s){ return s != k ; } )(uniq(v.sort))) ; auto allDeps = uniq(sort(reduce!("a ~ b")(cast(string[])[], d.values))) ; auto extra = array(filter!((string s){return s !in d ; } )(allDeps)) ; foreach(s ; extra) d[s] = [] ;
string[][] sorted ;
while(true) { string[] ordered ;
foreach(item,dep ;d) if(dep.length == 0) ordered ~= item ; if(ordered.length) sorted ~= ordered.sort ; else break ;
DEPType dd ;
foreach(item, dep ; d) if(find(ordered, item).length == 0) // not found dd[item] = array(filter! ( (string s) { return find(ordered, s).length == 0 ; } )(dep)) ; d = dd ; }
if (d.length > 0) throw new Exception( format("A cyclic dependency exists amongst :\n%s", pp(d)) ) ;
return sorted ;
}
void main() {
DEPType deps ; deps["des_system_lib"] = "std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee".split() ; deps["dw01"] = "ieee dw01 dware gtech".split() ; deps["dw02"] = "ieee dw02 dware".split() ; deps["dw03"] = "std synopsys dware dw03 dw02 dw01 ieee gtech".split() ; deps["dw04"] = "dw04 ieee dw01 dware gtech".split() ; deps["dw05"] = "dw05 ieee dware".split() ; deps["dw06"] = "dw06 ieee dware".split() ; deps["dw07"] = "ieee dware".split() ; deps["dware"] = "ieee dware".split() ; deps["gtech"] = "ieee gtech".split() ; deps["ramlib"] = "std ieee".split() ; deps["std_cell_lib"] = "ieee std_cell_lib".split() ; deps["synopsys"] = [];
auto depw = deps.aadup ; foreach(idx, suborder ; toposort(depw)) writefln("#%d : %s", idx + 1, suborder) ;
writeln() ; depw = deps.aadup ; depw["dw01"] ~= "dw04" ; foreach(suborder ; toposort(depw)) // should throw writeln(suborder) ;
}</lang>
output:
#1 : [ieee, std, synopsys] #2 : [dware, gtech, ramlib, std_cell_lib] #3 : [dw01, dw02, dw05, dw06, dw07] #4 : [des_system_lib, dw03, dw04] object.Exception: A cyclic dependency exists amongst : des_system_lib => [dw01] dw01 => [dw04] dw03 => [dw01] dw04 => [dw01]
E
<lang e>def makeQueue := <elib:vat.makeQueue>
def topoSort(data :Map[any, Set[any]]) {
# Tables of nodes and edges def forwardEdges := [].asMap().diverge() def reverseCount := [].asMap().diverge() def init(node) { reverseCount[node] := 0 forwardEdges[node] := [].asSet().diverge() } for node => deps in data { init(node) for dep in deps { init(dep) } } # 'data' holds the dependencies. Compute the other direction. for node => deps in data { for dep ? (dep != node) in deps { forwardEdges[dep].addElement(node) reverseCount[node] += 1 } }
# Queue containing all elements that have no (initial or remaining) incoming edges def ready := makeQueue() for node => ==0 in reverseCount { ready.enqueue(node) } var result := [] while (ready.optDequeue() =~ node :notNull) { result with= node for next in forwardEdges[node] { # Decrease count of incoming edges and enqueue if none if ((reverseCount[next] -= 1).isZero()) { ready.enqueue(next) } } forwardEdges.removeKey(node) } if (forwardEdges.size().aboveZero()) { throw(`Topological sort failed: $forwardEdges remains`) } return result
}</lang>
<lang e>pragma.enable("accumulator")
def dataText := "\ des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib synopsys\ "
def data := accum [].asMap() for rx`(@item.{17})(@deps.*)` in dataText.split("\n") { _.with(item.trim(), deps.split(" ").asSet()) }
println(topoSort(data))</lang>
Output: ["std", "synopsys", "ieee", "dware", "gtech", "ramlib", "std_cell_lib", "dw02", "dw05", "dw06", "dw07", "dw01", "des_system_lib", "dw03", "dw04"]
Haskell
<lang haskell>import Data.List import Data.Maybe import Control.Arrow import System.Random import Control.Monad
combs 0 _ = [[]] combs _ [] = [] combs k (x:xs) = map (x:) (combs (k-1) xs) ++ combs k xs
depLibs :: [(String, String)] depLibs = [("des_system_lib","std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee"),
("dw01","ieee dw01 dware gtech"), ("dw02","ieee dw02 dware"), ("dw03","std synopsys dware dw03 dw02 dw01 ieee gtech"), ("dw04","dw04 ieee dw01 dware gtech"), ("dw05","dw05 ieee dware"), ("dw06","dw06 ieee dware"), ("dw07","ieee dware"), ("dware","ieee dware"), ("gtech","ieee gtech"), ("ramlib","std ieee"), ("std_cell_lib","ieee std_cell_lib"), ("synopsys",[])]
toposort xs
| (not.null) cycleDetect = error $ "Dependency cycle detected for libs " ++ show cycleDetect | otherwise = foldl makePrecede [] dB
where dB = map ((\(x,y) -> (x,y \\ x)). (return *** words)) xs
makePrecede ts ([x],xs) = nub $ case elemIndex x ts of Just i -> uncurry(++) $ first(++xs) $ splitAt i ts _ -> ts ++ xs ++ [x]
cycleDetect = filter ((>1).length) $ map (\[(a,as), (b,bs)] -> (a `intersect` bs) ++ (b `intersect`as)) $ combs 2 dB</lang>
output: <lang haskell>*Main> toposort depLibs ["std","synopsys","ieee","std_cell_lib","dware","dw02","gtech","dw01","ramlib","des_system_lib","dw03","dw04","dw05","dw06","dw07"]
- Main> toposort $ (\(xs,(k,ks):ys) -> xs++ (k,ks++" dw04"):ys) $ splitAt 1 depLibs
- Exception: Dependency cycle detected for libs "dw01","dw04"</lang>
Icon and Unicon
Icon
This solution uses an efficient internal representation for a graph that limits the number of nodes to no more than 256.
The resulting topological ordering is displayed so elements on each line are independent and so can be built in parallel once the preceding lines of elements have been built.
<lang icon>record graph(nodes,arcs) global ex_name, in_name
procedure main()
show(tsort(getgraph()))
end
procedure tsort(g)
t := "" while (n := g.nodes -- pnodes(g)) ~== "" do { t ||:= "("||n||")" g := delete(g,n) } if g.nodes == then return t write("graph contains the cycle:") write("\t",genpath(fn := !g.nodes,fn,g))
end
- pnodes(g) -- return the predecessor nodes of g
- (those that have an arc from them)
procedure pnodes(g)
static labels, fromnodes initial { labels := &ucase fromnodes := 'ACEGIKMOQSUWY' } return cset(select(g.arcs,labels, fromnodes))
end
- select(s,image,object) - efficient node selection
procedure select(s,image,object)
slen := *s ilen := *image return if slen <= ilen then map(object[1+:slen/2],image[1+:slen],s) else map(object,image,s[1+:ilen]) || select(s[1+ilen:0],image,object)
end
- delete(g,x) -- deletes all nodes in x from graph g
- note that arcs must be deleted as well
procedure delete(g,x)
t := "" g.arcs ? while arc := move(2) do if not upto(x,arc) then t ||:= arc return graph(g.nodes--x,t)
end
- getgraph() -- read and construct a graph
- graph is described via sets of arcs, as in:
- from to1 to2 to3
- external names are converted to single character names for efficiency
- self-referential arcs are ignored
procedure getgraph()
static labels initial labels := &cset ex_name := table() in_name := table() count := 0 arcstr := "" nodes := every line := !&input do { nextWord := create genWords(line) if nfrom := @nextWord then { /in_name[nfrom] := &cset[count +:= 1] /ex_name[in_name[nfrom]] := nfrom nodes ++:= in_name[nfrom] while nto := @nextWord do { if nfrom ~== nto then { /in_name[nto] := &cset[count +:= 1] /ex_name[in_name[nto]] := nto nodes ++:= in_name[nto] arcstr ||:= in_name[nfrom] || in_name[nto] } } } } return graph(nodes,arcstr)
end
- generate all 'words' in string
procedure genWords(s)
static wchars initial wchars := &cset -- ' \t' s ? while tab(upto(wchars))\1 do suspend tab(many(wchars))\1
end
- show(t) - return the external names (in order) for the nodes in t
- Each output line contains names that are independent of each other
procedure show(t)
line := "" every n := !t do case n of { "(" : line ||:= "\n\t(" ")" : line[-1] := ")" default : line ||:= ex_name[n] || " " } write(line)
end
- genpath(f,t,g) -- generate paths from f to t in g
procedure genpath(f,t,g, seen)
/seen := seen ++:= f sn := nnodes(f,g) if t ** sn == t then return ex_name[f] || " -> " || ex_name[t] suspend ex_name[f] || " -> " || genpath(!(sn --seen),t,g,seen)
end
- nnodes(f,g) -- compute all nodes that could follow f in g
procedure nnodes(f,g)
t := g.arcs ? while arc := move(2) do if arc[1] == f then t ++:= arc[2] return t
end</lang>
Sample output:
->tsort <tsort.data (std synopsys ieee) (std_cell_lib ramlib dware gtech) (dw02 dw01 dw05 dw06 dw07) (des_system_lib dw03 dw04) ->
When run with the cycle suggested in the problem statement:
->tsort <tsort.data graph contains the cycle: dw01 -> dw04 -> dw01 ->
Unicon
The Icon solution also works in Unicon, but the following variant removes the 256-node limit by using sets instead of csets with the same algorithm that produces output so each line gives the elements that can be built in parallel once the elements in the preceding lines have been built.
<lang icon>record graph(nodes,arcs)
procedure main()
show(tsort(getgraph()))
end
procedure tsort(g)
t := [] while *(n := g.nodes -- pnodes(g)) > 0 do { every put(p := [], !n) put(t, p) g := delete(g,n) } if *g.nodes = 0 then return t write("graph contains the cycle:") write("\t",genpath(fn := !g.nodes,fn,g))
end
procedure pnodes(g)
cp := create !g.arcs every insert(p := set(), |1(@cp,@cp)) return p
end
procedure delete(g,x)
arcs := [] cp := create !g.arcs while (f := @cp, t := @cp) do { if !x == (f|t) then next every put(arcs,f|t) } return graph(g.nodes--x, arcs)
end
procedure getgraph()
arcs := [] nodes := set() every line := !&input do { nextWord := create genWords(line) if nfrom := @nextWord then { insert(nodes, nfrom) while nto := @nextWord do { if nfrom ~== nto then { insert(nodes, nto) every put(arcs, nfrom | nto) } } } } return graph(nodes,arcs)
end
procedure genWords(s)
static wchars initial wchars := &cset -- ' \t' s ? while tab(upto(wchars))\1 do suspend tab(many(wchars))\1
end
procedure show(t)
line := "" every n := !t do case type(n) of { "list" : line ||:= "\n\t("||toString(n)||")" default : line ||:= " "||n } write(line)
end
procedure toString(n)
every (s := "") ||:= !n || " " return s[1:-1] | s
end
procedure genpath(f,t,g, seen)
/seen := set() insert(seen, f) sn := nnodes(f,g) if member(sn, t) then return f || " -> " || t suspend f || " -> " || genpath(!(sn--seen),t,g,seen)
end
procedure nnodes(f,g)
t := set() cp := create !g.arcs while (af := @cp, at := @cp) do if af == f then insert(t, at) return t
end</lang>
J
<lang J>dependencySort=: monad define
parsed=. <@;:;._2 y names=. {.&>parsed depends=. (> =@i.@#) names e.S:1 parsed depends=. (+. +./ .*.~)^:_ depends assert.-.1 e. (<0 1)|:depends (-.&names ~.;parsed),names /: +/"1 depends
)</lang>
With the sample data set:
dependencies=: noun define des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib synopsys )
We would get:
>dependencySort dependencies std ieee dware gtech ramlib std_cell_lib synopsys dw02 dw05 dw06 dw07 dw01 dw04 dw03 des_system_lib
Here is an alternate implementation which uses a slightly different representation for the dependencies:
<lang J>depSort=: monad define
parsed=. <@;:;._2 y names=. {.&>parsed depends=. (-.L:0"_1 #,.i.@#) names i.L:1 parsed depends=. (~.@,&.> ;@:{L:0 1~)^:_ depends assert.-.1 e. (i.@# e.S:0"0 ])depends (-.&names ~.;parsed),names /: #@> depends
)</lang>
It's results are identical to the first implementation, but this might be more efficient in typical cases.
OCaml
<lang ocaml>let dep_libs = [
("des_system_lib", ["std"; "synopsys"; "std_cell_lib"; "des_system_lib"; "dw02"; "dw01"; "ramlib"; "ieee"]); ("dw01", (*"dw04"::*)["ieee"; "dw01"; "dware"; "gtech"]); ("dw02", ["ieee"; "dw02"; "dware"]); ("dw03", ["std"; "synopsys"; "dware"; "dw03"; "dw02"; "dw01"; "ieee"; "gtech"]); ("dw04", ["dw04"; "ieee"; "dw01"; "dware"; "gtech"]); ("dw05", ["dw05"; "ieee"; "dware"]); ("dw06", ["dw06"; "ieee"; "dware"]); ("dw07", ["ieee"; "dware"]); ("dware", ["ieee"; "dware"]); ("gtech", ["ieee"; "gtech"]); ("ramlib", ["std"; "ieee"]); ("std_cell_lib", ["ieee"; "std_cell_lib"]); ("synopsys", []);
]
let dep_libs =
let f (lib, deps) = (* remove self dependency *) (lib, List.filter (fun d -> d <> lib) deps) in List.map f dep_libs
let libs = (* list items, each being unique *)
let rec aux acc = function | [] -> (acc) | x::xs -> aux (if List.mem x acc then acc else x::acc) xs in aux [] (List.flatten(List.map (fun (lib, deps) -> lib::deps) dep_libs))
let get_deps lib =
try (List.assoc lib dep_libs) with Not_found -> []
let res =
let rec aux acc later todo progress = match todo, later with | [], [] -> (List.rev acc) | [], _ -> if progress then aux acc [] later false else invalid_arg "un-orderable data" | x::xs, _ -> let deps = get_deps x in let ok = List.for_all (fun dep -> List.mem dep acc) deps in if ok then aux (x::acc) later xs true else aux acc (x::later) xs progress in let starts, todo = List.partition (fun lib -> get_deps lib = []) libs in aux starts [] todo false
let () =
print_string "result: \n "; print_endline (String.concat ", " res);
- </lang>
If dw04 is added to the set of dependencies of dw01 to make the data un-orderable (uncomment it), an exception is raised:
Exception: Invalid_argument "un-orderable data".
Oz
Using constraint propagation and search: <lang oz>declare
Deps = unit( des_system_lib: [std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee] dw01: [ieee dw01 dware gtech] dw02: [ieee dw02 dware] dw03: [std synopsys dware dw03 dw02 dw01 ieee gtech] dw04: [dw04 ieee dw01 dware gtech] dw05: [dw05 ieee dware] dw06: [dw06 ieee dware] dw07: [ieee dware] dware: [ieee dware] gtech: [ieee gtech] ramlib: [std ieee] std_cell_lib: [ieee std_cell_lib] synopsys:nil )
%% Describe possible solutions proc {TopologicalOrder Solution} FullDeps = {Complete Deps} in %% The solution is a record that maps library names %% to finite domain variables. %% The smaller the value, the earlier it must be compiled Solution = {FD.record sol {Arity FullDeps} 1#{Width FullDeps}} %% for every lib on the left side {Record.forAllInd FullDeps proc {$ LibName Dependants} %% ... and every dependant on the right side for Dependant in Dependants do %% propagate compilation order if Dependant \= LibName then Solution.LibName >: Solution.Dependant end end end } %% enumerate solutions {FD.distribute naive Solution} end
%% adds empty list of dependencies for libs that only occur on the right side fun {Complete Dep} AllLibs = {Nub {Record.foldL Dep Append nil}} in {Adjoin {List.toRecord unit {Map AllLibs fun {$ L} L#nil end}} Dep} end
%% removes duplicates fun {Nub Xs} D = {Dictionary.new} in for X in Xs do D.X := unit end {Dictionary.keys D} end
%% print grouped by parallelizable jobs proc {PrintSolution Sol} for I in 1..{Record.foldL Sol Value.max 1} do for Lib in {Arity {Record.filter Sol fun {$ X} X == I end}} do {System.printInfo Lib#" "} end {System.printInfo "\n"} end end
fun {GetOrderedLibs Sol} {Map {Sort {Record.toListInd Sol} CompareSecond} SelectFirst} end fun {CompareSecond A B} A.2 < B.2 end fun {SelectFirst X} X.1 end
in
case {SearchOne TopologicalOrder} of nil then {System.showInfo "Un-orderable."} [] [Sol] then {System.showInfo "A possible topological ordering: "} {ForAll {GetOrderedLibs Sol} System.showInfo} {System.showInfo "\nBONUS - grouped by parallelizable compile jobs:"} {PrintSolution Sol} end</lang>
Output:
A possible topological ordering: synopsys std ieee std_cell_lib ramlib gtech dware dw07 dw06 dw05 dw02 dw01 dw04 dw03 des_system_lib BONUS - grouped by parallelizable compile jobs: ieee std synopsys dware gtech ramlib std_cell_lib dw01 dw02 dw05 dw06 dw07 des_system_lib dw03 dw04
Perl
In July 2002, Topological Sort was the monthly Perl Golf course. The post-mortem contains many solutions. This code was adapted from the solution that scored 144.39.
The algorithm used allows the output to be clustered; libraries on the same line are all independent (given the building of any previous lines of libraries), and so could be built in parallel.
<lang perl>sub print_topo_sort {
my %deps = @_;
my %ba; while ( my ( $before, $afters_aref ) = each %deps ) { for my $after ( @{ $afters_aref } ) { $ba{$before}{$after} = 1 if $before ne $after; $ba{$after} ||= {}; } }
while ( my @afters = sort grep { ! %{ $ba{$_} } } keys %ba ) { print "@afters\n"; delete @ba{@afters}; delete @{$_}{@afters} for values %ba; }
print !!%ba ? "Cycle found! ". join( ' ', sort keys %ba ). "\n" : "---\n";
}
my %deps = (
des_system_lib => [qw( std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee )], dw01 => [qw( ieee dw01 dware gtech )], dw02 => [qw( ieee dw02 dware )], dw03 => [qw( std synopsys dware dw03 dw02 dw01 ieee gtech )], dw04 => [qw( dw04 ieee dw01 dware gtech )], dw05 => [qw( dw05 ieee dware )], dw06 => [qw( dw06 ieee dware )], dw07 => [qw( ieee dware )], dware => [qw( ieee dware )], gtech => [qw( ieee gtech )], ramlib => [qw( std ieee )], std_cell_lib => [qw( ieee std_cell_lib )], synopsys => [qw( )],
); print_topo_sort(%deps); push @{ $deps{'dw01'} }, 'dw04'; # Add unresolvable dependency print_topo_sort(%deps);</lang>
Output:
ieee std synopsys dware gtech ramlib std_cell_lib dw01 dw02 dw05 dw06 dw07 des_system_lib dw03 dw04 --- ieee std synopsys dware gtech ramlib std_cell_lib dw02 dw05 dw06 dw07 Cycle found! des_system_lib dw01 dw03 dw04
Perl 6
<lang perl6>sub print_topo_sort ( %deps ) {
my %ba; for %deps.kv -> $before, @afters { for @afters -> $after { %ba{$before}{$after} = 1 if $before ne $after; %ba{$after} //= {}; } }
while %ba.grep( not *.value )».key -> @afters { say ~@afters.sort; %ba.delete(@afters); %ba.values».delete(@afters); }
say %ba ?? "Cycle found! {%ba.keys.sort}" !! '---';
}
my %deps = (
des_system_lib => [< std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee >], dw01 => [< ieee dw01 dware gtech >], dw02 => [< ieee dw02 dware >], dw03 => [< std synopsys dware dw03 dw02 dw01 ieee gtech >], dw04 => [< dw04 ieee dw01 dware gtech >], dw05 => [< dw05 ieee dware >], dw06 => [< dw06 ieee dware >], dw07 => [< ieee dware >], dware => [< ieee dware >], gtech => [< ieee gtech >], ramlib => [< std ieee >], std_cell_lib => [< ieee std_cell_lib >], synopsys => [< >],
); print_topo_sort(%deps); %deps<dw01>.push: 'dw04'; # Add unresolvable dependency print_topo_sort(%deps);</lang>
Output:
ieee std synopsys dware gtech ramlib std_cell_lib dw01 dw02 dw05 dw06 dw07 des_system_lib dw03 dw04 --- ieee std synopsys dware gtech ramlib std_cell_lib dw02 dw05 dw06 dw07 Cycle found! des_system_lib dw01 dw03 dw04
PicoLisp
<lang PicoLisp>(de sortDependencies (Lst)
(setq Lst # Build a flat list (uniq (mapcan '((L) (put (car L) 'dep (cdr L)) # Store dependencies in 'dep' properties (copy L) ) (mapcar uniq Lst) ) ) ) # without self-dependencies (make (while Lst (ifn (find '((This) (not (: dep))) Lst) # Found non-depending lib? (quit "Can't resolve dependencies" Lst) (del (link @) 'Lst) # Yes: Store in result (for This Lst # and remove from 'dep's (=: dep (delete @ (: dep))) ) ) ) ) )</lang>
Output:
: (sortDependencies (quote (des-system-lib std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee) (dw01 ieee dw01 dware gtech) (dw02 ieee dw02 dware) (dw03 std synopsys dware dw03 dw02 dw01 ieee gtech) (dw04 dw04 ieee dw01 dware gtech) (dw05 dw05 ieee dware) (dw06 dw06 ieee dware) (dw07 ieee dware) (dware ieee dware) (gtech ieee gtech) (ramlib std ieee) (std-cell-lib ieee std-cell-lib) (synopsys) ) ) -> (std synopsys ieee std-cell-lib ramlib dware dw02 gtech dw01 des-system-lib dw03 dw04 dw05 dw06 dw07)
PowerShell
<lang PowerShell>#Input Data $a=@" des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib synopsys "@
- Convert to Object[]
$c = switch ( $a.split([char] 10) ) {
$_ { $b=$_.split(' ') New-Object PSObject -Property @{ Library = $b[0] "Library Dependencies" = @( $( $b[1..($b.length-1)] | Where-Object { $_ -match '\w' } ) ) } }
}
- Add pure dependencies
$c | ForEach-Object {
$_."Library Dependencies" | Where-Object { $d=$_ $(:andl foreach($i in $c) { if($d -match $i.Library) { $false break andl } }) -eq $null } | ForEach-Object { $c+=New-Object PSObject -Property @{ Library=$_ "Library Dependencies"=@() } }
}
- Associate with a dependency value
- Initial Dependency Value
$d = $c | Sort Library | Select-Object Library,"Library Dependencies",@{
Name="Dep Value" Expression={ 1 }
}
- Modify Dependency Value, perform check for incorrect dependency
- Dep Value is determined by a parent child relationship, if a library is a parent, all libraries dependant on it are children
for( $i=0; $i -lt $d.count; $i++ ) {
$errmsg="" foreach( $j in ( 0..( $d.count - 1 ) | Where-Object { $_ -ne $i } ) ) { #Foreach other Child Library where this is a dependency, increase the Dep Value of the Child if( $( :orl foreach( $k in $d[$j]."Library Dependencies" ) { if( $k -match $d[$i].Library ) { foreach( $n in $d[$i]."Library Dependencies" ) { if( $n -match $d[$j].Library ) { $errmsg="Error Cyclic Dependency {0}<->{1}" -f $d[$i].Library, $d[$j].Library break } } $true break orl } } ) ) { #If the child has already been processed, increase the Dep Value of its children if( $j -lt $i ) { foreach( $l in ( 0..( $d.count - 1 ) | Where-Object { $_ -ne $j } ) ) { if( $( :orl2 foreach( $m in $d[$l]."Library Dependencies" ) { if( $m -match $d[$j].Library ) { $true break orl2 } } ) ) { $d[$l]."Dep Value"+=$d[$i]."Dep Value" } } } $d[$j]."Dep Value"+=$d[$i]."Dep Value" } if( $errmsg -ne "" ) { $errmsg $d=$null break } }
}
- Sort and Display
if( $d ) {
$d | Sort "Dep Value",Library | ForEach-Object { "{0,-14} LIBRARY DEPENDENCIES`n{1,-14} ====================" -f "LIBRARY", "=======" } { "{0,-14} $($_."Library Dependencies")" -f $_.Library }
}</lang>
PureBasic
<lang PureBasic>#EndOfDataMarker$ = "::EndOfData::" DataSection
;"LIBRARY: [LIBRARY_DEPENDENCY_1 LIBRARY_DEPENDENCY_2 ... LIBRARY_DEPENDENCY_N] Data.s "des_system_lib: [std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee]" Data.s "dw01: [ieee dw01 dware gtech]" ;Data.s "dw01: [ieee dw01 dware gtech dw04]" ;comment the previous line and uncomment this one for cyclic dependency Data.s "dw02: [ieee dw02 dware]" Data.s "dw03: [std synopsys dware dw03 dw02 dw01 ieee gtech]" Data.s "dw04: [dw04 ieee dw01 dware gtech]" Data.s "dw05: [dw05 ieee dware]" Data.s "dw06: [dw06 ieee dware]" Data.s "dw07: [ieee dware]" Data.s "dware: [ieee dware]" Data.s "gtech: [ieee gtech]" Data.s "ramlib: [std ieee]" Data.s "std_cell_lib: [ieee std_cell_lib]" Data.s "synopsys: nil" Data.s #EndOfDataMarker$
EndDataSection
Structure DAG_node
Value.s forRemoval.i ;flag marks elements that should be removed the next time they are accessed List dependencies.s()
EndStructure
If Not OpenConsole()
MessageRequester("Error","Unable to open console") End
EndIf
- // initialize Directed Acyclic Graph //
Define i, itemData.s, firstBracketPos NewList DAG.DAG_node() Repeat
Read.s itemData itemData = Trim(itemData) If itemData <> #EndOfDataMarker$ AddElement(DAG()) ;add library DAG()\Value = Trim(Left(itemData, FindString(itemData, ":", 1) - 1)) ;parse library dependencies firstBracketPos = FindString(itemData, "[", 1) If firstBracketPos itemData = Trim(Mid(itemData, firstBracketPos + 1, FindString(itemData, "]", 1) - firstBracketPos - 1)) For i = (CountString(itemData, " ") + 1) To 1 Step -1 AddElement(DAG()\dependencies()) DAG()\dependencies() = StringField(itemData, i, " ") Next EndIf EndIf
Until itemData = #EndOfDataMarker$
- // process DAG //
- create DAG entry for nodes listed in dependencies but without their own entry
NewMap libraries() ForEach DAG()
ForEach DAG()\dependencies() libraries(DAG()\dependencies()) = #True If DAG()\dependencies() = DAG()\Value DeleteElement(DAG()\dependencies()) ;remove self-dependencies EndIf Next
Next
ForEach DAG()
If FindMapElement(libraries(),DAG()\Value) DeleteMapElement(libraries(),DAG()\Value) EndIf
Next
ResetList(DAG()) ForEach libraries()
AddElement(DAG()) DAG()\Value = MapKey(libraries())
Next ClearMap(libraries())
- process DAG() repeatedly until no changes occur
NewList compileOrder.s() Repeat
noChangesMade = #True ForEach DAG() If DAG()\forRemoval DeleteElement(DAG()) Else ;remove dependencies that have been placed in the compileOrder ForEach DAG()\dependencies() If FindMapElement(libraries(),DAG()\dependencies()) DeleteElement(DAG()\dependencies()) EndIf Next ;add DAG() entry to compileOrder if it has no more dependencies If ListSize(DAG()\dependencies()) = 0 AddElement(compileOrder()) compileOrder() = DAG()\Value libraries(DAG()\Value) = #True ;mark the library for removal as a dependency DAG()\forRemoval = #True noChangesMade = #False EndIf EndIf Next
Until noChangesMade
If ListSize(DAG())
PrintN("Cyclic dependencies detected in:" + #CRLF$) ForEach DAG() PrintN(" " + DAG()\Value) Next
Else
PrintN("Compile order:" + #CRLF$) ForEach compileOrder() PrintN(" " + compileOrder()) Next
EndIf
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit") Input() CloseConsole()</lang> Sample output for no dependencies:
Compile order: ieee std dware gtech ramlib std_cell_lib synopsys dw01 dw02 dw03 dw04 dw05 dw06 dw07 des_system_lib
Sample output when cyclic dependencies are present:
Cyclic dependencies detected in: des_system_lib dw01 dw03 dw04
Python
<lang python>try:
from functools import reduce
except:
pass
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(), }
def toposort2(data):
for k, v in data.items(): v.discard(k) # Ignore self dependencies extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys()) data.update({item:set() for item in extra_items_in_deps}) while True: ordered = set(item for item,dep in data.items() if not dep) if not ordered: break yield ' '.join(sorted(ordered)) data = {item: (dep - ordered) for item,dep in data.items() if item not in ordered} assert not data, "A cyclic dependency exists amongst %r" % data
print ('\n'.join( toposort2(data) ))</lang>
Ordered output
items on a line could be processed in any sub-order or, indeed, in parallel:
ieee std synopsys dware gtech ramlib std_cell_lib dw01 dw02 dw05 dw06 dw07 des_system_lib dw03 dw04
If dw04 is added to the set of dependencies of dw01 to make the data un-orderable, an exception is raised:
Traceback (most recent call last): File "C:\Documents and Settings\All Users\Documents\Paddys\topological_sort.py", line 115, in <module> print ('\n'.join( toposort2(data) )) File "C:\Documents and Settings\All Users\Documents\Paddys\topological_sort.py", line 113, in toposort2 assert not data, "A cyclic dependency exists amongst %r" % data AssertionError: A cyclic dependency exists amongst {'dw04': {'dw01'}, 'dw03': {'dw01'}, 'dw01': {'dw04'}, 'des_system_lib': {'dw01'}}
R
First make the list <lang R> deps <- list( "des_system_lib" = c("std", "synopsys", "std_cell_lib", "des_system_lib", "dw02", "dw01", "ramlib", "ieee"), "dw01" = c("ieee", "dw01", "dware", "gtech", "dw04"), "dw02" = c("ieee", "dw02", "dware"), "dw03" = c("std", "synopsys", "dware", "dw03", "dw02", "dw01", "ieee", "gtech"), "dw04" = c("dw04", "ieee", "dw01", "dware", "gtech"), "dw05" = c("dw05", "ieee", "dware"), "dw06" = c("dw06", "ieee", "dware"), "dw07" = c("ieee", "dware"), "dware" = c("ieee", "dware"), "gtech" = c("ieee", "gtech"), "ramlib" = c("std", "ieee"), "std_cell_lib" = c("ieee", "std_cell_lib"), "synopsys" = c()) </lang>
Topological sort function. It will throw an error if it cannot complete, printing the list of items which cannot be ordered. If it succeeds, returns the list of items in topological order. <lang R> tsort <- function(deps) { nm <- names(deps) libs <- union(as.vector(unlist(deps)), nm)
s <- c() # first libs that depend on nothing for(x in libs) { if(!(x %in% nm)) { s <- c(s, x) } }
k <- 1 while(k > 0) { k <- 0 for(x in setdiff(nm, s)) { r <- c(s, x) if(length(setdiff(depsx, r)) == 0) { s <- r k <- 1 } } }
if(length(s) < length(libs)) { v <- setdiff(libs, s) stop(sprintf("Unorderable items :\n%s", paste("", v, sep="", collapse="\n"))) }
s } </lang>
On the given example : <lang R> tsort(deps)
- [1] "std" "ieee" "dware" "gtech" "ramlib"
- [6] "std_cell_lib" "synopsys" "dw01" "dw02" "dw03"
- [11] "dw04" "dw05" "dw06" "dw07" "des_system_lib"
</lang>
If dw01 depends on dw04 as well :
<lang R> Unorderable items : des_system_lib dw01 dw04 dw03 </lang>
Ruby
Uses the TSort module from the Ruby stdlib. <lang ruby>require 'tsort' class Hash
include TSort alias tsort_each_node each_key def tsort_each_child(node, &block) fetch(node).each(&block) end
end
depends = {} DATA.each do |line|
libs = line.split(' ') key = libs.shift depends[key] = libs libs.each {|lib| depends[lib] ||= []}
end
begin
p depends.tsort depends["dw01"] << "dw04" p depends.tsort
rescue TSort::Cyclic => e
puts "cycle detected: #{e}"
end
__END__ des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib synopsys</lang> Produces:
["ieee", "dware", "gtech", "dw01", "dw02", "std", "synopsys", "dw03", "dw04", "dw05", "std_cell_lib", "ramlib", "des_system_lib", "dw06", "dw07"] cycle detected: topological sort failed: ["dw01", "dw04"]
Tcl
<lang tcl>package require Tcl 8.5 proc topsort {data} {
# Clean the data dict for {node depends} $data {
if {[set i [lsearch -exact $depends $node]] >= 0} { set depends [lreplace $depends $i $i] dict set data $node $depends } foreach node $depends {dict lappend data $node}
} # Do the sort set sorted {} while 1 {
# Find available nodes set avail [dict keys [dict filter $data value {}]] if {![llength $avail]} { if {[dict size $data]} { error "graph is cyclic, possibly involving nodes \"[dict keys $data]\"" } return $sorted } # Note that the lsort is only necessary for making the results more like other langs lappend sorted {*}[lsort $avail]
# Remove from working copy of graph
dict for {node depends} $data { foreach n $avail { if {[set i [lsearch -exact $depends $n]] >= 0} { set depends [lreplace $depends $i $i] dict set data $node $depends } } } foreach node $avail { dict unset data $node }
}
}</lang> Demonstration code (which parses it from the format that the puzzle was posed in): <lang tcl>set inputData {
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib synopsys
} foreach line [split $inputData \n] {
if {[string trim $line] eq ""} continue dict set parsedData [lindex $line 0] [lrange $line 1 end]
} puts [topsort $parsedData]</lang> Sample output:
ieee std synopsys dware gtech ramlib std_cell_lib dw01 dw02 dw05 dw06 dw07 des_system_lib dw03 dw04
If the suggested extra arc is added, this is the error output:
graph is cyclic, possibly involving nodes "des_system_lib dw01 dw03 dw04"
UNIX Shell
The unix tsort utility does a topological sort where dependencies on multiple items must be reformatted as multiple lines of dependencies of an item and only one dependant.
<lang bash>bash$ tsort <<! > des_system_lib des_system_lib > des_system_lib dw01 > des_system_lib dw02 > des_system_lib ieee > des_system_lib ramlib > des_system_lib std > des_system_lib std_cell_lib > des_system_lib synopsys > dw01 dw01 > dw01 dware > dw01 gtech > dw01 ieee > dw02 dw02 > dw02 dware > dw02 ieee > dw03 dw01 > dw03 dw02 > dw03 dw03 > dw03 dware > dw03 gtech > dw03 ieee > dw03 std > dw03 synopsys > dw04 dw01 > dw04 dw04 > dw04 dware > dw04 gtech > dw04 ieee > dw05 dw05 > dw05 dware > dw05 ieee > dw06 dw06 > dw06 dware > dw06 ieee > dw07 dware > dw07 ieee > dware dware > dware ieee > gtech gtech > gtech ieee > ramlib ieee > ramlib std > std_cell_lib ieee > std_cell_lib std_cell_lib ! des_system_lib dw03 dw04 dw05 dw06 dw07 std_cell_lib ramlib synopsys dw02 dw01 std gtech dware ieee bash$</lang>
Ursala
The tsort function takes a list of pairs <(lib: <dep...>)...> and returns a pair of lists (<lib...>,<lib...>) with the topologically sorted libraries on the left and the unorderable libraries, if any, on the right. Self-dependences are ignored and unlisted libraries are presumed independent. <lang Ursala>tsort = ~&nmnNCjA*imSLs2nSjiNCSPT; @NiX ^=lxPrnSPX ^(~&rlPlT,~&rnPrmPljA*D@r)^|/~& ~&m!=rnSPlX</lang> test program: <lang Ursala>#import std
dependence_table = -[
LIBRARY LIBRARY DEPENDENCIES
= ==============
des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee dw01 ieee dw01 dware gtech dw02 ieee dw02 dware dw03 std synopsys dware dw03 dw02 dw01 ieee gtech dw04 dw04 ieee dw01 dware gtech dw05 dw05 ieee dware dw06 dw06 ieee dware dw07 ieee dware dware ieee dware gtech ieee gtech ramlib std ieee std_cell_lib ieee std_cell_lib synopsys ]-
parse = ~&htA*FS+ sep` *tttt
- show+
main = <.~&l,@r ~&i&& 'unorderable: '--> mat` ~~ tsort parse dependence_table</lang> With the given table, the output is
std ieee synopsys std_cell_lib ramlib gtech dware dw07 dw06 dw05 dw02 dw01 dw04 dw03 des_system_lib
When the suggested dependence is added, the output becomes
std ieee synopsys std_cell_lib ramlib gtech dware dw07 dw06 dw05 dw02 unorderable: des_system_lib dw01 dw03 dw04
VBScript
Implementation
<lang vb> class topological dim dictDependencies dim dictReported dim depth
sub class_initialize set dictDependencies = createobject("Scripting.Dictionary") set dictReported = createobject("Scripting.Dictionary") depth = 0 end sub
sub reset dictReported.removeall end sub
property let dependencies( s ) 'assuming token tab token-list newline dim i, j ,k dim aList dim dep dim a1 aList = Split( s, vbNewLine ) '~ remove empty lines at end do while aList( UBound( aList ) ) = vbnullstring redim preserve aList( UBound( aList ) - 1 ) loop
for i = lbound( aList ) to ubound( aList ) aList( i ) = Split( aList( i ), vbTab, 2 ) a1 = Split( aList( i )( 1 ), " " ) k = 0 for j = lbound( a1) to ubound(a1) if a1(j) <> aList(i)(0) then a1(k) = a1(j) k = k + 1 end if next redim preserve a1(k-1) aList(i)(1) = a1 next for i = lbound( aList ) to ubound( aList ) dep = aList(i)(0) if not dictDependencies.Exists( dep ) then dictDependencies.add dep, aList(i)(1) end if next
end property
sub resolve( s ) dim i dim deps '~ wscript.echo string(depth,"!"),s depth = depth + 1 if dictDependencies.Exists(s) then deps = dictDependencies(s) for i = lbound(deps) to ubound(deps) resolve deps(i) next end if if not seen(s) then wscript.echo s see s end if depth = depth - 1 end sub
function seen( key ) seen = dictReported.Exists( key ) end function
sub see( key ) dictReported.add key, "" end sub
property get keys keys = dictDependencies.keys end property end class </lang>
Invocation
<lang vb> dim toposort set toposort = new topological toposort.dependencies = "des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee" & vbNewLine & _ "dw01 ieee dw01 dware gtech" & vbNewLine & _ "dw02 ieee dw02 dware" & vbNewLine & _ "dw03 std synopsys dware dw03 dw02 dw01 ieee gtech" & vbNewLine & _ "dw04 dw04 ieee dw01 dware gtech" & vbNewLine & _ "dw05 dw05 ieee dware" & vbNewLine & _ "dw06 dw06 ieee dware" & vbNewLine & _ "dw07 ieee dware" & vbNewLine & _ "dware ieee dware" & vbNewLine & _ "gtech ieee gtech" & vbNewLine & _ "ramlib std ieee" & vbNewLine & _ "std_cell_lib ieee std_cell_lib" & vbNewLine & _ "synopsys "
dim k for each k in toposort.keys wscript.echo "----- " & k toposort.resolve k wscript.echo "-----" toposort.reset next </lang>
Output
----- des_system_lib std synopsys ieee std_cell_lib dware dw02 gtech dw01 ramlib des_system_lib ----- ----- dw01 ieee dware gtech dw01 ----- ----- dw02 ieee dware dw02 ----- ----- dw03 std synopsys ieee dware dw02 gtech dw01 dw03 ----- ----- dw04 ieee dware gtech dw01 dw04 ----- ----- dw05 ieee dware dw05 ----- ----- dw06 ieee dware dw06 ----- ----- dw07 ieee dware dw07 ----- ----- dware ieee dware ----- ----- gtech ieee gtech ----- ----- ramlib std ieee ramlib ----- ----- std_cell_lib ieee std_cell_lib ----- ----- synopsys synopsys -----
Visual Basic .Net
Adapted from http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html which was itself an adaptation of Java code. I added the Rosetta code specific format of dependencies, as well as checks for references to self. <lang Visual Basic .Net> ' Adapted from: ' http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html ' added/changed: ' - conversion to VB.Net (.Net 2 framework) ' - added Rosetta Code dependency format parsing ' - check & removal of self-dependencies before sorting Module Program Sub Main() Dim Fields As New List(Of Field)() ' You can also add Dependson using code like: ' .DependsOn = New String() {"ieee", "dw01", "dware"} _
fields.Add(New Field() With { _ .Name = "des_system_lib", _ .DependsOn = Split("std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee", " ") _ }) fields.Add(New Field() With { _ .Name = "dw01", _ .DependsOn = Split("ieee dw01 dware gtech", " ") _ }) fields.Add(New Field() With { _ .Name = "dw02", _ .DependsOn = Split("ieee dw02 dware", " ") _ }) fields.Add(New Field() With { _ .Name = "dw03", _ .DependsOn = Split("std synopsys dware dw03 dw02 dw01 ieee gtech", " ") _ }) fields.Add(New Field() With { _ .Name = "dw04", _ .DependsOn = Split("dw04 ieee dw01 dware gtech", " ") _ }) fields.Add(New Field() With { _ .Name = "dw05", _ .DependsOn = Split("dw05 ieee dware", " ") _ }) fields.Add(New Field() With { _ .Name = "dw06", _ .DependsOn = Split("dw06 ieee dware", " ") _ }) fields.Add(New Field() With { _ .Name = "dw07", _ .DependsOn = Split("ieee dware", " ") _ }) fields.Add(New Field() With { _ .Name = "dware", _ .DependsOn = Split("ieee dware", " ") _ }) fields.Add(New Field() With { _ .Name = "gtech", _ .DependsOn = Split("ieee gtech", " ") _ }) fields.Add(New Field() With { _ .Name = "ramlib", _ .DependsOn = Split("std ieee", " ") _ }) fields.Add(New Field() With { _ .Name = "std_cell_lib", _ .DependsOn = Split("ieee std_cell_lib", " ") _ }) fields.Add(New Field() With { _ .Name = "synopsys" _ }) Console.WriteLine("Input:") For Each ThisField As field In fields Console.WriteLine(ThisField.Name) If ThisField.DependsOn IsNot Nothing Then For Each item As String In ThisField.DependsOn Console.WriteLine(" -{0}", item) Next End If Next
Console.WriteLine(vbLf & "...Sorting..." & vbLf)
Dim sortOrder As Integer() = getTopologicalSortOrder(fields)
For i As Integer = 0 To sortOrder.Length - 1 Dim field = fields(sortOrder(i)) Console.WriteLine(field.Name) ' Write up dependencies, too: 'If field.DependsOn IsNot Nothing Then ' For Each item As String In field.DependsOn ' Console.WriteLine(" -{0}", item) ' Next 'End If Next Console.Write("Press any key to continue . . . ") Console.ReadKey(True) End Sub
Private Sub CheckDependencies (ByRef Fields As List(Of Field)) ' Make sure all objects we depend on are part of the field list ' themselves, as there may be dependencies that are not specified as fields themselves. ' Remove dependencies on fields themselves.Y Dim AField As Field, ADependency As String
For i As Integer = Fields.Count - 1 To 0 Step -1 AField=fields(i) If AField.DependsOn IsNot Nothing then For j As Integer = 0 To Ubound(AField.DependsOn) ADependency = Afield.DependsOn(j) ' We ignore fields that depends on themselves: If AField.Name <> ADependency then If ListContainsVertex(fields, ADependency) = False Then ' Add the dependent object to the field list, as it ' needs to be there, without any dependencies Fields.Add(New Field() With { _ .Name = ADependency _ }) End If End If Next j End If Next i End Sub
Private Sub RemoveSelfDependencies (ByRef Fields As List(Of Field)) ' Make sure our fields don't depend on themselves. ' If they do, remove the dependency. Dim InitialUbound as Integer For Each AField As Field In Fields If AField.DependsOn IsNot Nothing Then InitialUbound = Ubound(AField.DependsOn) For i As Integer = InitialUbound to 0 Step - 1 If Afield.DependsOn(i) = Afield.Name Then ' This field depends on itself, so remove For j as Integer = i To UBound(AField.DependsOn)-1 Afield.DependsOn(j)=Afield.DependsOn(j+1) Next ReDim Preserve Afield.DependsOn(UBound(Afield.DependsOn)-1) End If Next End If Next End Sub
Private Function ListContainsVertex(Fields As List(Of Field), VertexName As String) As Boolean ' Check to see if the list of Fields already contains a vertext called VertexName Dim Found As Boolean = False For i As Integer = 0 To fields.Count - 1 If Fields(i).Name = VertexName Then Found = True Exit For End If Next Return Found End Function
Private Function getTopologicalSortOrder(ByRef Fields As List(Of Field)) As Integer() ' Gets sort order. Will also add required dependencies to ' Fields.
' Make sure we don't have dependencies on ourselves. ' We'll just get rid of them. RemoveSelfDependencies(Fields)
'First check depencies, add them to Fields if required: CheckDependencies(Fields) ' Now we have the correct Fields list, so we can proceed: Dim g As New TopologicalSorter(fields.Count) Dim _indexes As New Dictionary(Of String, Integer)(fields.count)
'add vertex names to our lookup dictionaey For i As Integer = 0 To fields.Count - 1 _indexes(fields(i).Name.ToLower()) = g.AddVertex(i) Next
'add edges For i As Integer = 0 To fields.Count - 1 If fields(i).DependsOn IsNot Nothing Then For j As Integer = 0 To fields(i).DependsOn.Length - 1 g.AddEdge(i, _indexes(fields(i).DependsOn(j).ToLower())) Next End If Next
Dim result As Integer() = g.Sort() Return result End Function
Private Class Field Public Property Name() As String Get Return m_Name End Get Set m_Name = Value End Set End Property Private m_Name As String Public Property DependsOn() As String() Get Return m_DependsOn End Get Set m_DependsOn = Value End Set End Property Private m_DependsOn As String() End Class End Module Class TopologicalSorter source adapted from: http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html which was adapted from: http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm #Region "- Private Members -"
Private ReadOnly _vertices As Integer() ' list of vertices Private ReadOnly _matrix As Integer(,) ' adjacency matrix Private _numVerts As Integer ' current number of vertices Private ReadOnly _sortedArray As Integer() ' Sorted vertex labels
#End Region
#Region "- CTors -"
Public Sub New(size As Integer) _vertices = New Integer(size - 1) {} _matrix = New Integer(size - 1, size - 1) {} _numVerts = 0 For i As Integer = 0 To size - 1 For j As Integer = 0 To size - 1 _matrix(i, j) = 0 Next Next ' sorted vert labels _sortedArray = New Integer(size - 1) {} End Sub
#End Region
#Region "- Public Methods -"
Public Function AddVertex(vertex As Integer) As Integer _vertices(System.Threading.Interlocked.Increment(_numVerts)-1) = vertex Return _numVerts - 1 End Function
Public Sub AddEdge(start As Integer, [end] As Integer) _matrix(start, [end]) = 1 End Sub
Public Function Sort() As Integer() ' Topological sort While _numVerts > 0 ' while vertices remain, ' get a vertex with no successors, or -1 Dim currentVertex As Integer = noSuccessors() If currentVertex = -1 Then ' must be a cycle Throw New Exception("Graph has cycles") End If
' insert vertex label in sorted array (start at end) _sortedArray(_numVerts - 1) = _vertices(currentVertex)
' delete vertex deleteVertex(currentVertex) End While
' vertices all gone; return sortedArray Return _sortedArray End Function
#End Region
#Region "- Private Helper Methods -"
' returns vert with no successors (or -1 if no such verts) Private Function noSuccessors() As Integer For row As Integer = 0 To _numVerts - 1 Dim isEdge As Boolean = False ' edge from row to column in adjMat For col As Integer = 0 To _numVerts - 1 If _matrix(row, col) > 0 Then ' if edge to another, isEdge = True ' this vertex has a successor try another Exit For End If Next If Not isEdge Then ' if no edges, has no successors Return row End If Next Return -1 ' no End Function
Private Sub deleteVertex(delVert As Integer) ' if not last vertex, delete from vertexList If delVert <> _numVerts - 1 Then For j As Integer = delVert To _numVerts - 2 _vertices(j) = _vertices(j + 1) Next
For row As Integer = delVert To _numVerts - 2 moveRowUp(row, _numVerts) Next
For col As Integer = delVert To _numVerts - 2 moveColLeft(col, _numVerts - 1) Next End If _numVerts -= 1 ' one less vertex End Sub
Private Sub moveRowUp(row As Integer, length As Integer) For col As Integer = 0 To length - 1 _matrix(row, col) = _matrix(row + 1, col) Next End Sub
Private Sub moveColLeft(col As Integer, length As Integer) For row As Integer = 0 To length - 1 _matrix(row, col) = _matrix(row, col + 1) Next End Sub
#End Region End Class </lang>
Output
Input: des_system_lib -std -synopsys -std_cell_lib -des_system_lib -dw02 -dw01 -ramlib -ieee dw01 -ieee -dw01 -dware -gtech dw02 -ieee -dw02 -dware dw03 -std -synopsys -dware -dw03 -dw02 -dw01 -ieee -gtech dw04 -dw04 -ieee -dw01 -dware -gtech dw05 -dw05 -ieee -dware dw06 -dw06 -ieee -dware dw07 -ieee -dware dware -ieee -dware gtech -ieee -gtech ramlib -std -ieee std_cell_lib -ieee -std_cell_lib synopsys ...Sorting... des_system_lib ramlib dw03 std std_cell_lib dw04 dw01 gtech dw07 dw06 dw05 dw02 dware ieee synopsys Press any key to continue . . .