[Math] Unique Topological Sort for DAG

graph theorysortingtopological-graph-theory

I have a DAG (directed acyclic graph) which has more than one valid topological sorting. I'm looking for a way to sort it topologically and always get the same, well defined result.

For example take this graph:

A-->B
A-->C
B-->D
C-->D

There are two solutions to a topological sort:

1: A, B, C, D and
2: A, C, B, D

We notice that B and C can be sorted in any order. Therefore we choose alphabetic sorting as secondary sorting to get only one solution: A, B, C, D.

Here's an other example:

E-->G
E-->H
H-->F

There are three solutions to a topological sort:

1: E, G, H, F
1: E, H, G, F
3: E, H, F, G

But here, there's no obvious solution. No solution seems to be more "alphabetic" than the others.

Is there a way to get a unique, deterministic solution for any DAG?

Best Answer

If you are programming the sort algorithm, unless you use a random choice of the child of a parent node, your algorithm will always return the same answer. In your example, make a program that, starting from E, will prefer G to H and so forth. It will always answer E, G, H, F.
EDIT : here is the algo. 

While there is a vertex in the graph do
    Display the vertex with 0 incoming edge (if many choose the one with lower lexical order)
    Remove it and its out-going links from the graph
end

The order is what the algo displays.
It will start with E. It is displayed and removed. Then G and H are candidates. The one with the lower lexical order is G. It is displayed and removed. The next candidate is H. It is displayed and removed. Then F is displayed and removed.
The algo make a breadth-first search. Its display is E, G, H, F.

Related Question