System Services (Runlevel) (formerly known as Runlevel Editor) |
toposort.ycp |
Topological sorting for script dependencies | |
|
|
This module has an unstable interface. |
Local Functions |
local
TopologicalSort (map<string, list<string> > g)
->
list< list<string> >
Topologically sort a directed acyclic graph, ie. linearize a partial ordering. (what if the graph is a multigraph??)
- Parameters:
-
g 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
local
ReachableSubgraph (map<string, list<string> > g, string start)
->
map<string, list<string> >
Make a subgraph of g, starting at start
- Parameters:
-
g A directed acyclic graph as a map: nodes are keys, values are lists of nodes that are reached by an edge from the respective key. start starting node
- Return value:
-
the reachable subgraph
local
ReverseGraph (map<string, list<string> > g)
->
map<string, list<string> >
Reverse edges of an oriented graph
- Parameters:
-
g a graph
- Return value:
-
reversed graph