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.)

Plowshare

Why not just start the topological sort from random nodes...also this sounds pretty homeworky, considering I had done something like this last year. – Sammiesammons

if you return the results at random then the larger algorithm is only guaranteed correct in the limit of an infinite number of iterations. wouldn't it be better to enumerate the different orders? – Kermanshah

@Sammiesammons - It's possible that starting at a random node might work, but I need an algorithm that's been proven to have the quality of potentially hitting any topological sort. It's the chasm between intuition and proof that makes me want to find some algorithm that's already been proven to have that quality. I've already got one version that doesn't use topsort at all. But if a random algorithm for topological sorts (of the kind I mentioned) exists, I'd just like to mention it as an alternative. If not, I'll toss it into the "future work" section of the paper I'm writing. – Plowshare

@andrew - The difference between finite-but-unbounded and infinite matters for the kind of mathematical analysis I'm doing on the algorithm, and finite-but-unbounded is good enough. (Infinite searches don't terminate, finite-but-bounded do.) Regarding full enumeration: that works on very small DAG's, but I need something reasonably efficient for bigger ones. O(V^2) or O(V^3) are okay, but not O(V!). – Plowshare

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.

Niall