Unique Topological Sort for DAG

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?

• If you can get all solutions, you can simply order them lexicographically and pick the first. In your last example that would be $E,G,H,F$. – Brian M. Scott Dec 9 '16 at 20:59
• Good point. Then the question remains how to do this. – XPlatformer Dec 11 '16 at 13:23

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.

• That will not work. If my program "prefers G to H", because of the alphabetic sorting, then it will also prefer F to G and also always answer E, H, F, G. – XPlatformer Jan 24 '17 at 12:41
• But F is not a child of E. It will never be compared to G. OK, I edit my answer. – jcm69 Jan 24 '17 at 13:53
• I get it now. Thanks a lot! – XPlatformer Jan 24 '17 at 14:59

No. The Wikipedia article on topological sort does say that it's possible, in linear time, to determine whether a unique sort exists.

• please read the question again – XPlatformer Dec 11 '16 at 13:27