Flattening a forest into a sorted list, using only the set of nodes and an "is parent" predicate (or: sorting a list with an incomplete comparison function)

Question

I have a set of objects, and I need to produce a sorted list, but my comparison function is incomplete and leaves some room for "imagination" on the part of the sorting algorithm.

Specifically, given a collection of trees like the following:

  A      E
  |      |
  B--C   F
  |
  D

What I have on hand is the set of nodes {A, B, C, D, E, F}, in no particular order, and a function to test direct parent-child relationships:

parent(A, B)
parent(A, C)
parent(B, D)
parent(E, F)

I need to flatten this into a list where parents come before their children, but other than that, the order is unimportant. So any of these results would be acceptable:

A, B, C, D, E, F.

A, B, D, C, E, F.

E, F, A, B, C, D.

A, E, B, C, F, D.

The set will be small, a few dozen at most, so I'm not too concerned about performance. What I am concerned about is avoiding temporary data structures other than lists: due to limitations of the language I'm using, organizing these items into a temporary tree (for example) would be unpleasant.

Answer 1

I believe you're looking for a topological sort algorithm.

Here's the relevant algorithm from the Wikipedia article:

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes

function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edge from n to m do
            visit(m)
        add n to L

for each node n in S do
    visit(n)

Answer 2

You could use this simple algorithm:

while unsorted set is not empty {
    elem = get element from unsorted set
    while elem has parent and parent is in unsorted set {
        elem = parent of elem
    }
    add elem to result list
    remove elem from unsorted set
}