System Services (Runlevel) (formerly known as Runlevel Editor) |
toposort.ycp |
| Topological sorting for script dependencies | |
|
|
|
This module has an unstable interface. |
Imports
Local Functions |
local
TopologicalSort (map<string, list<string> > dag)
->
list< list<string> >
Topologically sort a directed acyclic graph, ie. linearize a partial ordering. (what if the graph is a multigraph??)
- Parameters:
-
dag A DAG as a map: nodes are keys, values are lists of nodes that are reached by an edge from the respective key.
- Return value:
-
[out, rest]
out: a list containing the keys of the map in topological order
rest: a list, empty if the graph was acyclic, otherwise it is a superset of the nodes forming the cycle and "out" is a partial result
Info:
TopologicalSort as implemented above only works on graphs
with string vertices.
Now we will
1. generalize it to arbitrary data ("things")
2. exploit the order of keys in map
local
StableTopologicalSort (list<thing_t> things)
->
list<list<thing_t> >
- Parameters:
-
things a list of things
- Return value:
-
[out, rest]
out: a list of things in topological order (starting with things that have no *incoming* edge)
rest: a list, empty if the graph was acyclic, otherwise it is a superset of the things forming the cycle and "out" is a partial result