4
$\begingroup$

Is there any known algorithm to generate a random reducible flow graph (single root, single sink) with a given maximum cardinality $N$?

Ideally, the distribution should be uniform over the set of reducible flow graphs of cardinality $\leq N$. Alternatively, it could be uniform over the possible topologies of reducible flow graphs of cardinality $\leq N$ (e.g. graphs that are isomorphic or that differ just for the length of some chain can be considered equivalent). The exact distribution is not dictated by my use case (random testing), so I would also be interested in other non-uniform distributions that assign a non-zero probability to any possible topology.

Two approaches that I found so far are:

  1. Randomly generate a flow graph (same considerations as before regarding the distribution), test if it is reducible, repeat until it is reducible.
  2. Construct a graph from a grammar, for example the one described in Sec. 7 of "Flow Graph Reducibility", randomly choosing the rule to apply and recursively applying the algorithm to generate the sub-graphs.

I'm pretty sure that the time complexity of (1) would be too high to be used in practice (let say, $N=1000$). (2) is feasible, but it lacks forward edges that exit from a loop, which are crucial in my use case. It would be possible to define another grammar, but then the question is whether the new grammar can actually generate any graph topology.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.