
functions
files
intro
|
|
Runlevel Editor
|
toposort.ycp
|
Topological sorting for script dependencies
|
|
|
|
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:
local ReverseGraph (map<string, list<string> > g) -> map<string, list<string> >
|
|
Reverse edges of an oriented graph
- Parameters:
- Return value:
|