README
¶
toposort
Topologically sort a directed acyclic graph (DAG) with cycle detection.
This topological sort can be used to put items in dependency order, where each edge (u, v) has a vertex u that is depended on by v, such that u must come before v.
The result of completing a topological sort is an ordered slice of vertexes, where the position of every vertex in the list is before any of its destination vertexes.
After sorting this graph:
A--> B--> D--> E <---F
| ^ |
| | |
+-------> C <--------+
The following conditions must be true concerning the relative position of the
nodes in the returned list of nodes: A<B, A<C, B<D, D<E, C<D, F<C, F<E. The
slice [F A C B D E] is a correct result.
This implementation uses Kahn's algorithm.
Installation
$ go get github.com/gammazero/toposort
Example
sorted, err := Toposort([]Edge{
{"B", "D"}, {"D", "E"}, {"A", "B"}, {"A", "C"},
{"C", "D"}, {"F", "C"}, {"F", "E"}})
if err != nil {
log.Fatal("Toposort returned error:", err)
}
fmt.Println("Sorted correctly:", sorted)
Documentation
¶
Overview ¶
Topologically sort a directed acyclic graph (DAG) with cycle detection.
A topological sort of a DAG G = (V, E) is a linear ordering of all its vertexes such that if G contains an edge (u, v), then u appears before v in the ordering. In other words u < v.
This topological sort can be used to put items in dependency order, where each edge (u, v) has a vertex u that is depended on by v, such that u must come before v.
This sort finds cycles in the graph. If the graph is determined to have a cycle, then an error is returned.
The result of completing a topological sort is an ordered slice of vertexes, where the position of every vertex in the list is before any of its destination vertexes.
After sorting this graph:
A--> B--> D--> E <---F | ^ | | | | +-------> C <--------+
The following conditions must be true concerning the relative position of the nodes in the returned list of nodes: A<B, A<C, B<D, D<E, C<D, F<C, F<E. The slice [F A C B D E] is a correct result.
When sorting this graph:
+---------------+
| |
A--> B--> D--> E <---F <--+
| ^ |
| | |
+-------> C <--------+
Toposort will return with an error stating that a cycle was detected.
Reversing the order of the returned vertices is the same as reversing the direction of each edge.
This implementation uses Kahn's algorithm. https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm
Example (Clothes) ¶
This example shows dependency-sorting articles of clothing to compute a solution for Professor Bumstead to get dressed correctly. Articles of clothing are arranged into pairs where the first item in a pair must be put on after the second item in the pair.
fmt.Println("Dependency-sorting Professor Bumstead's cloths:")
// Edges are (x, y) where x depends on y. In other words, y must be done
// before x. In a DAG: y --> x. So ToposortR is called for this reversed
// order.
sorted, err := ToposortR([]Edge{
{"jacket", "tie"}, {"jacket", "belt"},
{"tie", "shirt"},
{"belt", "shirt"}, {"belt", "pants"},
{"pants", "undershorts"},
{"shoes", "pants"}, {"shoes", "undershorts"}, {"shoes", "socks"},
{"watch", nil}})
if err != nil {
log.Fatal("Toposort returned error:", err)
}
fmt.Println("Sorted correctly:", sorted)
Output:
Example (Graph) ¶
This example shows sorting of a directed acyclic graph.
// Test sorting a DAG.
fmt.Println("Sorting graph:")
fmt.Println("A--> B--> D--> E <---F")
fmt.Println("| ^ |")
fmt.Println("| | |")
fmt.Println("+-------> C <--------+")
sorted, err := Toposort([]Edge{
{"B", "D"}, {"D", "E"}, {"A", "B"}, {"A", "C"},
{"C", "D"}, {"F", "C"}, {"F", "E"}})
if err != nil {
log.Fatal("Toposort returned error:", err)
}
fmt.Println("Sorted correctly:", sorted)
Output:
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Toposort ¶
Toposort performs a topological sort of the DAG defined by given edges.
Takes a slice of Edge, where each element is a vertex pair representing an edge in the graph. Each pair can also be considered a dependency relationship where Edge[0] must happen before Edge[1]. For a reversed order, call ToposortR().
To include a node that is not connected to the rest of the graph, include a node with one nil vertex. It can appear anywhere in the sorted output.
Returns an ordered list of vertexes where each vertex occurs before any of its destination vertexes. An error is returned if a cycle is detected.
Source Files