5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Brian M. Scott Dec 9 '16 at 20:59
  • $\begingroup$ Good point. Then the question remains how to do this. $\endgroup$ – XPlatformer Dec 11 '16 at 13:23
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – XPlatformer Jan 24 '17 at 12:41
  • $\begingroup$ But F is not a child of E. It will never be compared to G. OK, I edit my answer. $\endgroup$ – jcm69 Jan 24 '17 at 13:53
  • $\begingroup$ I get it now. Thanks a lot! $\endgroup$ – XPlatformer Jan 24 '17 at 14:59
-1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.