This is an extension of RandomGraph with specific constraints
Where @Histograms wanted to make $n$ random graphs with a specific constraint (in @Histogram's case, having 2 vertices each with exactly one edge).
My question is if there is a way to sample $n$ random graphs with the following constraints:
- all graphs have exactly $v$ vertices
- generated graphs are either acyclic / cyclic depending on a boolean
- if it simplifies the problem, then either only directed / undirected
As I only care about if there are exactly $v$ vertices (all graphs have the same dimension for their adjacency matrix), the graphs can have any number of edges. Likewise, since these are represented as adjacency matrices, multi-edges are filtered out. Although buckles are still feasible...
For example, suppose I want to sample (randomly) $50$ acyclic graphs with $10$ vertices and $50$ cyclic graphs with $10$ vertices.
One can produce $n$ RandomGraph
s with fixed number of vertices from a distribution from:
RandomGraph[BernoulliGraphDistribution[numVertices, probOfEdge], numGraphs]
However, even with large $n$, these graphs tend to favor one state for these boolean properties of graphs.
Currently I think one could use RandomTree
to produce both acyclic and cyclic graphs, where a tree is acyclic by nature, and adding an edge to a random number of leaves to the root of the tree would produce "random" cyclic graphs. However manipulating vertices in the Graph object returned by Combinatorica
is a bit lost to me.
Thoughts?
DirectedGraph[RandomGraph[{n,m}], "Acyclic"]
. $\endgroup$