Algorithm to convert directed acyclic graphs to sequences

Question

If D depends on B and C which each depend on A, I want ABCD (or ACBD) as the result; that is generate a flat sequence from the graph such that all nodes appear before any of their descendants. For example, we may need to install dependencies for X before installing X.

What is a good algorithm for this?

Answer 1

In questions like this, terminology is crucial in order to find the correct links.

The dependencies you describe form a partially ordered set (poset). Simply put, that is a set with an order operator, for which the comparison of some pairs might be undefined. In your example B and C are incomparible (neither B depends on C, nor C depends on B).

An extension of the order operator is one that respects the original partial order and adds some extra comparisons to previously incomparable elements. In the extreme: a linear extension leads to a total ordering. For every partial ordering such an extension exists.

Algorithms to obtain a linear extension from a poset are called topological sorting. Wikipedia provides the following very simple algorithm:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)