Please... at least mention Kahn's topological sorting algorithm

[jeffgerickson]

...either in the main text or in an exercise.

Kahn's algorithm is a whatever-first topological sort, predating Tarjan's depth-first algorithm by 14 years. Initialize each vertex with a counter containing its indegree. Put all sinks into a bag. (Kahn's 1962 implementation was equivalent to using a FIFO queue, but that doesn't matter.) As long as the bag is not empty, remove a vertex v from the bag, decrement the counters for each successor of v, and insert any successor whose counter is zero into the bag.

If all vertices are eventually put into the bag, they are removed from the bag in forward topological order; on the other hand, any vertex that is never put into the bag lies on a directed cycle. The algorithm runs in O(V+E) time; each vertex is inserted and extracted at most once, and each edge is scanned once.

[jeffgerickson]

[jeffgerickson]

Actually, Kahn implements the bag using a complete array of vertices. (The graph is represented by a list of directed edges sorted by tail vertex; each entry in the vertex array stores the index of the first edge leaving that vertex. In other words, it's an adjacency array!) His algorithm repeatedly scans this "event list" for vertices with counter zero that have not already been processed. Since at least one vertex is processed in every scan, the algorithm ends after at most V scans, which makes the worst-case running time O(V^2), not O(V+E).

The natural O(V+E)-time variant using a FIFO queue is due to Knuth [TAOCP I].

[jeffgerickson]

And while we're at it, mention that the entire concept of topological ordering seems to have been first "published" (in a US Navy Weapons Lab report) by M. P. Jarnagin in 1960, as part of the Navy's development of the PERT project-management approach, first launched in the late 1950s. (No, not RAND this time!) Jarnagin described an algorithm to find a consistent ordering (topological order) of the activities (edges!) of a PERT diagram (directed graph) if there is one.

Jarnagin's algorithm bears a striking resemblance to the Bellman-Ford shortest path algorithm. (In fact, it's equivalent to Bellman-Ford where every edge has weight –1.) Each vertex stores an integer label, called its "provisional rank", initially equal to 0. The algorithm repeatedly scans for edges u->v such that prank(u)≥prank(v), and then sets prank(v) to prank(u)+1. Specifically, a single pass of Jarnigan's algorithm examines every edge and "relaxes" any "tense" edges that it finds. The algorithm provably terminates after at most V+1 passes if the input graph is acyclic, so the overall running time is O(VE). The final provisional rank of each vertex is the length of the longest path ending at that vertex. Sorting the vertices by their rank (breaking ties arbitrarily) gives a topological order.

Jarnagin also describes algorithms to isolate a single strong component ("irreducible circular network") and to identify the strong component of every vertex. Nothing as clever as Kosaraju-Sharir, though.

[jeffgerickson]

See also the development of the "Critical Path Method" by DuPont as part of the Manhattan project, and later publicly with Remington Rand in the late 1950s. Using linear programming! Sheesh!

See also the 1930 proof by Szpilrajn (= Marczewski), and his claim that it was already known!, that topological orderings exist even for infinite partial orders. (Thanks, Knuth!)

[jeffgerickson]

Okay, one more, because the rabbit hole isn't deep enough yet. "Process charts" were introduced by Gilbreth and Gilbreth in 1921.

[jeffgerickson]

See also this 1961 paper by Lasser, which seems to describe (an inefficient implementation of) Tarjan's now-standard DFS-based algorithm.