Sort a sequence of items with ‘before’, ‘after’, and ‘id’ attributes.
The sort is topological. If an item does not specify a ‘before’ or ‘after’, it is placed after the preceding item.
If a cycle is found in the dependecies, a warning is logged and the order of the items is undefined.
Topologically sort a list of (parent, child) pairs.
Returns a tuple containing the list of elements sorted in dependency order (parent to child order), if possible, and a boolean indicating whether the graph contains cycles.
A simple algorithm due to Kahn, in which vertices are chosen from the graph in the same order as the eventual topological sort, is used.
Note that this implementation is stable in the following sense: if we have the input list [..., (parent, child1), ..., (parent, child2), ...], then child1 will be before child2 in the output list (if there there is no additional dependency forcing another ordering).