Constraint-based random testing is a powerful technique which aims at generating random test cases to verify functional properties of a program. Its objective is to determine whether a function satisfies a given property for every possible input. This approach requires firstly defining the property to satisfy, then secondly to provide a "generator of inputs" able to feed the program with the inputs generated. Besides, function inputs often need to satisfy certain constraints to ensure the function operates correctly, which makes the crafting of such a generator a hard task. In this paper, we are interested in the problem of manufacturing a uniform and efficient generator for the solutions of a CSP. In order to do that, we propose a specialized solving method that produces a well-suited representation for random sampling. Our solving method employs a dedicated propagation scheme based on the hypergraph representation of a CSP, and a custom split heuristic called birdge-first that emphasizes the interests of our propagation scheme. The generators we build are general enough to handle a wide range of use-cases. They are moreover uniform by construction, iterative and self-improving. We present a prototype built upon the AbSolute constraint solving library and demonstrate its performances on several realistic examples.

Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. DAGs are an omnipresent data structure in computer science and the problem of counting the DAGs of a given number of vertices has been solved in the 70’s by Robinson. In many applications one needs to construct connected DAGs and to control their number of edges, but the adaptation of Robinson’s enumeration to take this into account led to counting formulas based on the inclusion-exclusion principle, inducing a high computational cost for the uniform random sampling of DAGs based on this formula. In the present paper we propose two contributions. First we enumerate a new class of DAGs, enriched with an independent ordering of the children of each vertex, according to their numbers of vertices and edges. We obtain a constructive recursive counting formula for them (i.e. without using the inclusion-exclusion principle) using a new decomposition scheme. Then we show the applicability of our method by proposing a constructive enumeration of Robinson’s labelled DAGs, by vertices and edges, based on the same decomposition. As a consequence we are able to derive efficient uniform random samplers for both models.