random algorithm over all topological sorts of a DAG?

Question

Does anyone know of a random algorithm for generating a topological sort of a DAG, where each invocation of the algorithm has a non-zero probability of generating every valid topological sort of the DAG.

It's crucial that the algorithm does not preclude any valid topological sort, because it's part of a larger algorithm that, given enough iterations, must be demonstrably capable of exploring all topological sorts of a given DAG.

Does anyone know if such an algorithm has been developed?

(Alternatively, if anyone knows of a reasonably efficient algorithm that's guaranteed to generate all topological sorts of a given DAG, I can probably tweak that to get what I need.)

Answer 1

It helps to think in terms of what it means to say that you cover all possible topological sorts. During the topological sort, there is a point where you select a candidate to process from a subset of valid candidates, each of which is a valid choice. Depending on the way you implement the TS, it could be edge to follow from a set of edges each of which is a candidate (set of outgoing edges) or which node to select as the starting point (set of sinks/sources) or the randomly chosen start node.

What you want is to ensure that the selection process produces a distribution which does not show an overwhelming biased towards a particular subset of the candidates.

You can bias your selection process to achieve a more uniform distribution without running for infinite time. For example, you can assign a weight to each candidate of a set. Every time a candidate is selected you reduce the weight of that candidate by an amount "X" and increase the weight of the other candidates by an amount "X/(k-1)" where k is the size of the set of candidate set. This will result in a greater chance that a candidate which was not selected is selected in the next iteration, and result in a quicker convergence to a more uniform distribution.