Topological Sorting of Large Networks¶
Kahn, A. B. (1962). Topological Sorting of Large Networks. ACM, 5(11), 558-562.
Cited by¶
4 citations across 4 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.
Supported in partVerified against the publisher's abstract
Kahn's abstract establishes only that a general method for obtaining topological order exists; it never states that a cycle forecloses ordering, nor the deadlock/circular-definition pathology.
“The present paper presents a very general method for obtaining topological order.”
- 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.
Domain-specific¶
- Topological Sorting
- Kahn's algorithm (1962) maintains a queue of nodes with in-degree zero, repeatedly extracts one, emits it as the next element of the output order, and decrements the in-degree of each of its successors — adding any successor whose in-degree reaches zero to the queue.
This sourcePresents a general and efficient method for obtaining a topological order of a network. Reports that the method handles larger networks more efficiently than earlier procedures, giving a PERT example of 30,000 activities ordered in under an hour.
Supported in partVerified against the publisher's abstract
“The present paper presents a very general method for obtaining topological order. It permits treatment of larger networks than can be handled on present procedures and achieves this with greater efficiency.”
- Kahn's algorithm (1962) maintains a queue of nodes with in-degree zero, repeatedly extracts one, emits it as the next element of the output order, and decrements the in-degree of each of its successors — adding any successor whose in-degree reaches zero to the queue.
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 sourceDescribes topological sorting as repeatedly outputting zero-indegree vertices and removing their outgoing edges to expose newly ready vertices.
- 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.
- Topological Sorting
- In Kahn's algorithm, you find any element with no unmet dependency, output it, remove it and its outgoing edges, and repeat; if elements remain but none is free, a cycle exists.
This sourcePresents a topological-sorting procedure that repeatedly removes predecessor-free vertices and detects a cycle when no such vertex remains.
- In Kahn's algorithm, you find any element with no unmet dependency, output it, remove it and its outgoing edges, and repeat; if elements remain but none is free, a cycle exists.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 4 citations: 2 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:832b4cea8b9a · see in the full table