> [[Graph traversal]] in which each [[Node|node]] `v` is visited only after all its dependencies are visited. ## Script ```js const topological = graph => { let order = null if (!cycles(graph).hasCycle) { order = depthFirstOrder(graph).reversePost } return { isDag: order !== null, order } } ``` Depends on: - [[Cycles]] to determine before whether dealing with [[Directed acyclic graph|DAG]] - [[Depth First Order#Reverse post]] ## Example [[tinyGraph]] topologically sorted: `8 7 6 9 11 10 12 2 3 0 5 4 1` A graph usually admits many valid topological orders - any two nodes that do not depend on each other may be emitted in either order. This one is what the reverse post-order happens to yield; it is not canonical, and it is not stable either, since the walk follows whatever order the vertices and their neighbours are handed to it in. An order that must survive a re-read has to be pinned by sorting the input, or by an algorithm that tiebreaks explicitly. ![[tinyGraph#^mermaid]] ## Which end is first The order above puts a node *before* everything it points at, reading an edge `A -> B` as "A must come before B". Read the other way - `A -> B` meaning "A depends on B" - the answer is the exact mirror, and the reverse post-order is wrong for it. That reading wants the plain [[Depth First Order#Post|post-order]]: dependencies first, dependents after. Post-order has a second advantage. `topological` refuses a cyclic graph outright, returning `null`, because a strict order does not exist there. Post-order keeps walking and still emits every node, degrading to as ordered as the graph allows - which is what a traversal over a graph that *should* be a DAG, but is not quite, actually needs. [^1]: https://en.wikipedia.org/wiki/Topological_sorting