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
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?