Topological Sorting of Large Networks¶
Kahn, A. B. (1962). Topological Sorting of Large Networks. Communications of the ACM, 5(11), 558-562.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Cycle
- Second, closure forecloses ordering: a graph containing a cycle cannot be topologically ordered, because among the entries of the cycle there is no first or last, so any partial ordering of the whole system must break the cycle or live alongside it — which is why dependency cycles, deadlocks, and circular definitions share one structural pathology.
This sourceGives an algorithm that produces a topological ordering exactly when the directed graph is acyclic; a cycle forecloses ordering, the shared pathology of deadlocks and circular dependencies.
- Second, closure forecloses ordering: a graph containing a cycle cannot be topologically ordered, because among the entries of the cycle there is no first or last, so any partial ordering of the whole system must break the cycle or live alongside it — which is why dependency cycles, deadlocks, and circular definitions share one structural pathology.
Mechanisms¶
- Topological Sort
- Using an in-degree method, it repeatedly takes any node with zero remaining prerequisites, emits it, and removes its outgoing edges, exposing the next layer of now-ready nodes.
This sourceBoth run in time linear in the number of nodes and edges.
- Using an in-degree method, it repeatedly takes any node with zero remaining prerequisites, emits it, and removes its outgoing edges, exposing the next layer of now-ready nodes.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:832b4cea8b9a · see in the full table