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)