4
$\begingroup$

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$ RandomGraphs 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?

|improve this question
$\endgroup$
  • $\begingroup$ Graphs cannot be truly "random" if there are specified constraints, e.g., planarity... $\endgroup$ – David G. Stork Jul 4 '18 at 0:27
  • 2
    $\begingroup$ @DavidG.Stork What you say makes no sense to me (or at least severely distorts the usual meaning of "random"). We have a set of elements. A subset satisfies a condition. We can sample uniformly from this subset. BTW there are many papers on the uniform sampling of planar graphs (just google). $\endgroup$ – Szabolcs Jul 4 '18 at 9:01
  • 1
    $\begingroup$ The only truly general method to do it is to sample all graphs, then reject those that do not satisfy your property. This, however, is often not practical at all because you will end up rejecting the vast majority of samples. en.wikipedia.org/wiki/Rejection_sampling If you can restrict your question to one specific problem, then it would be acceptable. Otherwise I'm afraid it would get closed. $\endgroup$ – Szabolcs Jul 4 '18 at 9:04
  • 1
    $\begingroup$ Do you need directed or undirected? Connected only or also unconnected? Uniform sampling of directed acyclic graphs with a given number of edges is easy: fill out a random selection of adjacency matrix elements above the diagonal. Implementation: DirectedGraph[RandomGraph[{n,m}], "Acyclic"]. $\endgroup$ – Szabolcs Jul 4 '18 at 12:28
  • 2
    $\begingroup$ If you want directed and connected, that might be the hardest of all. Please also state if you have any constraint on the number of edges (e.g. fixed). Even seemingly small changes to the constraints can make a big difference to the difficulty of the problem. $\endgroup$ – Szabolcs Jul 4 '18 at 12:43
1
$\begingroup$

Since you have not specified in the question as to what "random" means exactly, let us proceed along the lines you suggest. That is, to get an acyclic graph we sample a tree (but not necessarily uniformly at random from the set of all $n$-vertex trees), and for cyclic graphs we can take a pseudotree.

    RandomTree[n_] := Graph@Table[i <-> RandomInteger[{0, i - 1}], {i, 1, n}];

    RandomPseudotree[n_] := Module[{g = RandomTree[n]},
    u = First[RandomSample[VertexList[g], 1]];
    v = First[RandomSample[
     Complement[Complement[VertexList[g], {u}], 
     AdjacencyList[g, u]], 1]];
    EdgeAdd[g, UndirectedEdge[u, v]]
  ]

Afterwards, the generation is straightforward:

Join[Table[RandomTree[10], {2}], Table[RandomPseudotree[10], {2}]]

As is evident, after we have a way of constructing a tree, a pseudotree is formed by sampling two vertices with an edge added between them. Here we only have to be careful not to sample two adjacent vertices, i.e., ensure that the cycle we put in is of length at least three.

|improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.