Random Graph Generation using Hyperedge Replacement Grammars
This work addresses the problem to satisfy the necessity of graph based applications when requesting random test data. May they involve classical algorithms, software testing, pointer manipulation, pattern recognition or even complex networks, the proposed solution, allows for the specification of any graph domain. Such approach, that, to the best of our knowledge has never been followed by any pre-existing method, uses context-free hyperedge replacement grammars to define graph classes, over which, elements are sampled uniformly at random. In order to achieve this, a generalised efficient version of Mairson’s algorithms for the sampling of strings over non-ambiguous context-free grammars in Chomsky normal form is adapted to the setting of hyperedge replacement. The presented method is correct in that given a non-ambiguous hyperedge replacement grammar in Chomsky normal form and a size , a -hypergraph in the language is generated uniformly at random.