How to use the topological sort and cycle finder
- Write one dependency per line. "Deploy depends on Test, Package" puts Test and Package before Deploy. "Build -> Test" puts Build before Test. A name alone adds an item with no links.
- Items are matched by their exact spelling, so use one spelling for each item. Lines starting with # are notes and are ignored.
- Read the build order, the level of each item and the groups of items that can run side by side.
- If the dependencies loop, read the cycle the page found and the items stuck behind it.
Formula
ready item = an item whose prerequisites are all done
level of an item = 1 + the highest level among its prerequisites (1 if it has none)
cycle: if items remain and none is ready, follow an unmet prerequisite from item to item until a name repeats
The order comes from Kahn's method. At each step the earliest listed ready item goes next, so the answer is the same every time and follows your order where it can.
Six build steps
Deploy depends on Test and Package, Package and Test depend on Build, Build depends on Install, and Docs comes after Build. The order is Install, Build, Test, Package, Deploy, Docs. Install is level 1, Build is level 2, Test, Package and Docs are level 3 and can run side by side, and Deploy is level 4. The longest chain is four items.
If Utils depends on Lib while Lib depends on Core and Core depends on Utils, nothing can go first in that group. The page finds the loop Utils -> Core -> Lib -> Utils, where each item must come before the next, and lists the items that are stuck behind it.
Why an order may not exist
A valid order exists exactly when the dependencies contain no cycle. A cycle means that some item eventually has to wait for itself, such as two modules that each need the other to be built first. The page shows one cycle, but there may be more. Fix the one it shows and run it again.
A self-dependency such as "A depends on A" is the shortest cycle, and the page reports it as A -> A.
Levels and parallel work
Items on the same level do not depend on each other, so they can be done at the same time if you have the people or machines. The number of levels is the length of the longest chain, which sets the fastest possible finish if each item takes one step. To use real durations and find the critical path, use the Critical Path Method Calculator, and to draw the tasks on a timeline, the Gantt Chart Maker.
To check two lists of names against each other first, use the Compare Two Lists tool.
Assumptions and limits
- Each line is one of the forms "A depends on B, C", "A needs B", "A requires B", "A after B", "B -> A", "B => A", "B before A" or a single name.
- Names are case sensitive and are matched exactly after trimming spaces at the ends.
- Up to 500 lines and 300 items are accepted.
- The page finds one valid order and one cycle. Other valid orders and other cycles may exist.
- Nothing typed here leaves your browser.
Frequently asked questions
What does it mean when the page shows a cycle?
It means no order can satisfy every dependency. The loop shown is one set of items that each wait for the next one, and the last waits for the first. Remove or reverse one link in it.
Why are some items listed after others that do not depend on them?
Several orders are valid. The page picks the one that follows your listed order whenever the dependencies allow it, so unrelated items appear in the order you wrote them.
Can one line list several prerequisites?
Yes. Separate them with commas or the word and, as in "Deploy depends on Test, Package". With arrows, "A -> B, C" puts A before both B and C.
What is a level?
It is how many steps of waiting an item has behind it. Items with no prerequisites are on level 1, and every other item sits one level above its highest prerequisite.