Answers · Making it fast enough
How do I know when there is no order that satisfies all the dependencies?
In shortIf you repeatedly remove anything with nothing still waiting on it and cannot remove everything, the dependencies contain a loop, so no valid order exists.
No valid order exists exactly when the dependency graph contains a cycle. The practical test is the peeling method you already use: count how many prerequisites each item is still waiting for, take any item whose count is zero, lower the counts of the items that were waiting on it, and repeat. If the process stops with items left over, those leftovers contain a cycle, so no order can satisfy every dependency.
The arithmetic on a graph that works
Take five items: fetch, library, tool, tests, package. Links run from a prerequisite to what it unlocks: fetch to library, fetch to tool, library to tests, library to package, tool to tests, tests to package. Initial waiting counts are fetch 0, library 1, tool 1, tests 2, package 2. Take fetch: library 1 to 0, tool 1 to 0. Take library: tests 2 to 1, package 2 to 1. Take tool: tests 1 to 0, package stays 1. Take tests: package 1 to 0. Take package. Peeled is 5, n is 5, so the graph has no cycle and the produced order is valid. The counts did all the work; no item was searched for.
Why a stall is not your fault
When the ready set empties early, the natural guess is that a different choice of ready item or a better tie break would have avoided the stall. It cannot. Every leftover item has count above zero, so each leftover is waiting on some other leftover. In a finite set, follow those waits: item to prerequisite, prerequisite to its prerequisite, and eventually an item repeats. The repeated section is a directed cycle, and no ordering of those items can put each after the thing it waits on. With three items A, B, C where A waits on B, B waits on C, C waits on A, the initial counts are A 1, B 1, C 1. The ready set is empty at the start, peeled is 0 against n=3, and every possible first choice violates a dependency: A needs B, B needs C, C needs A.
What the leftovers are
The comparison is one integer against another: peeled equals n, or peeled is less than n. That is the entire cycle test, and it costs nothing beyond the ordering pass. When peeled is less than n, the leftovers are not a random sample. Every one has positive count and every wait points inside the leftover set. The loop itself may be smaller than the leftovers, because anything downstream of a loop also stays behind. Add D that waits on A to the three item loop and n becomes 4. Initial counts are A 1, B 1, C 1, D 1, ready is empty, peeled is 0, and leftovers are A, B, C, D. The cycle is still A to C to B to A; D is merely downstream of it. A deep walk over just the leftovers recovers the loop, which is the part worth printing in an error message.
Where the test stops applying
The test assumes a fixed finite set of items and hard links saying each dependent must come after its prerequisite. If dependencies can be optional, conditional, or satisfied by either of two alternatives, the graph no longer states a single set of prerequisites, and a stall no longer means what it says here. If the graph changes while you peel, an item can become blocked after it was counted. With fixed links, however, the equivalence is exact: no cycle means every item eventually reaches count zero, and a cycle means at least one item never does. If only one component cycles, the rest still peels, but the whole job has no valid order until that component is broken.
If the process finishes, the order is valid because each item was taken only after its count reached zero, which means every prerequisite had already been taken. The order need not be unique. What is left free by the dependencies is exactly what can be done at the same time, so a valid order is a witness of correctness, not the only witness.
Worth keeping
- An order respecting every dependency exists exactly when the dependency graph has no directed cycle.
- If peeling zero-count items stalls with items left over, those leftovers contain a cycle, so no valid order exists.
- When an order does exist, any item with zero remaining prerequisites can be taken next; the alternatives are parallel work, not a risk to validity.
Where this goes next
This question is one step of Graphs and Finding a Path, a course that works through its subject from the beginning. The page that teaches this part of it is Doing Things in a Possible Order, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- Why doesn't breadth-first search give the cheapest path once the links have different costs?Breadth-first search counts links rather than costs, so it can return a route with fewer links that is more expensive than a longer route.
- Why does breadth-first search always find the path with the fewest links?Breadth-first search meets points in order of how many links they are from the start, so the first time it reaches a point it has used the fewest possible links.
- How do I find out if a graph is really in two separate pieces?Walk from one point, mark everything you can reach, then start again at any unmarked point; the number of walks is the number of separate pieces.
- Why is it safe to keep taking the cheapest link that doesn't create a loop?Because the cheapest link joining two separate pieces is the cheapest way across a split, and swapping it into any rival solution cannot raise the total cost.
- Why is O(2n) treated the same as O(n)?Because it describes how cost grows rather than exact cost, doubling every cost does not change the growth class.
- How does a hash function turn a word into an array index?A hash function reads the word as bytes, mixes them into one large number, then takes the remainder after dividing by the table size to get an index from zero to size minus one.