Random algorithm for all topological DAG types?

Question

Does anyone know of a random algorithm for generating a topological DAG type, where each call to the algorithm has a nonzero probability of generating each real topological DAG type.

It is very important that the algorithm does not exclude any valid topological sorting, because it is part of a larger algorithm that, with sufficient iterations, should be clearly able to examine all the topological types of a given DAG.

Does anyone know if such an algorithm has been developed?

(Alternatively, if anyone knows of a sufficiently efficient algorithm that is guaranteed to generate all the topological types of a given DAG, I can probably tweak this to get what I need.)

Answer 1

It helps you think in terms of what it means to say that you cover all possible topological types. During topological sorting, there is a point at which you select a candidate for processing from a subset of valid candidates, each of which is an acceptable choice. Depending on how you implement TS, this may be the edge to follow from a set of edges, each of which is a candidate (a set of outgoing edges) or which node chooses as a starting point (a set of receivers / sources) or a randomly chosen start node .

What you want is to ensure that the selection process produces a distribution that does not show an overwhelming prejudice against a specific subset of candidates.

You can bias your selection process to achieve a more even distribution without infinite time. For example, you can assign a weight to each set candidate. Each time a selected candidate is selected, you reduce the weight of this candidate by the amount of "X" and increase the weight of other candidates by the amount of "X / (k-1)", where k is the size of the set of candidates. This will result in the selected candidate , which was not selected, is selected at the next iteration and will lead to faster convergence into a more uniform distribution.