Stable topological sort

Puts the vertices of a graph without cycles in an order where every edge points forward, taking the ready vertex that comes first alphabetically.

Time complexity O((V+E) log V), gograph function gograph.StableTopologySort.

How it works

The stable topological sort works like Kahn's algorithm, but the ready vertices wait in a priority queue instead of a plain queue. Whenever more than one is ready, it takes the smallest by the compare function you pass, such as cmp.Compare for alphabetical labels.

As long as compare only returns zero for equal labels, the order depends on the labels alone, not on the order the graph was built. Two programs that add the same edges in a different order get the same result, which keeps generated files and test output from changing between runs. The priority queue adds a log factor, for O((V+E) log V). Like gograph.TopologySort, it returns ErrDAGHasCycle when the graph has a cycle.

Use it when the order is shown to people or written to a file, such as the steps of a build plan, and every run has to give the same result.

Spreadsheet formulas

A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each cell takes 1 to 4 milliseconds to work out. Each edge points from a cell to a formula that reads it.

A directed graph with 25 vertices and 41 edges.

In what order should the sheet recompute its cells, so that every formula reads cells that are already up to date?

In this order, every edge points forward, and vertices that are ready together go in alphabetical order: B2, C2, D2, G2, B3, C3, D3, E3, G3, B4, and so on to E8.

Step by step

  1. Count the incoming edges of each vertex, its in-degree. B2, C2, D2, G2, G3, G4 and G5 have none, so they start the ready list, which stays in alphabetical order. Labels are compared character by character, as cmp.Compare does.
  2. Take B2, the ready vertex that comes first alphabetically, and add it to the order.
  3. Remove the 2 edges out of B2. B3 and B4 still have incoming edges.
  4. Take C2, the ready vertex that comes first alphabetically, and add it to the order.
  5. Remove the 2 edges out of C2. C3 and C4 still have incoming edges.
  6. Take D2, the ready vertex that comes first alphabetically, and add it to the order.

44 more steps lead to the last one:

  1. Done. All 25 vertices are in the order, and every edge points from an earlier vertex to a later one.

Use it in Go

order, err := gograph.StableTopologySort(g, cmp.Compare)
if err != nil {
	return err // gograph.ErrDAGHasCycle
}
for _, v := range order {
	fmt.Println(v.Label())
}

Example graphs

More in Ordering

  • Topological sort: Puts the vertices of a graph without cycles in an order where every edge points forward, taking vertices in the order they become ready.
  • Topological levels: Splits a graph without cycles into levels, so that every edge goes to a later level and each level can run at the same time.
  • Ready-set tracker: Hands out the tasks of a graph without cycles as soon as every task they depend on is done, so a slow task holds up only the tasks that wait for it.
  • Dynamic topological sort: Keeps a topological order while edges are added one at a time, and moves only the vertices between the two ends of an edge that points backward.

All algorithms