# How to generate random directed connected graph?

How to generate random directed connected graph?

I need to create graph which will pass:

ConnectedGraphQ[^]

-
You've seen RandomGraph[]? It has a DirectedEdges option... –  Ｊ. Ｍ. Oct 12 '12 at 13:23
How many vertices and edges do you need? If the number of edges is sufficiently large compared to the number of vertices, then it's highly likely a random graph (with uniform distribution) will be connected anyway, so you can just generate random (possibly disconnected) graphs with RandomGraph until you obtain a connected one. –  whuber Oct 12 '12 at 14:04
@Mark "Random" does not mean arbitrary: it implies that a distribution is specified. See the MMA help page for RandomGraph to get a sense of its emphasis on allowing the user to specify how many vertices, how many edges, and the distribution of the edge frequencies. When you don't pay any attention to the distribution, you open yourself up to silly output. –  whuber Oct 12 '12 at 15:18
@whuber Having published several papers on the growth of trees in random constructions, I'm well aware of the nature of random graphs, thank you. I'm simply suggesting the basis of a strategy for dealing with sparse graphs. If my comment (not answer) seems to lack detail, perhaps that's because the question lacks detail. –  Mark McClure Oct 12 '12 at 15:29
@whuber Now that this question has become popular, I added an answer which should lead to interesting graphs. I guess that yet another approach would be to grab the largest connected component of a randomly generated graph. I still have no clue what the OP was really after, though. –  Mark McClure Oct 16 '12 at 15:04

A random geometric graph is generated by choosing some points in the plane and then connecting two vertices if they are within a certain distance. If the distance is chosen appropriately, the graph will be connected. Here's an implementation that uses a bisection method to determine the smallest appropriate distance.

SeedRandom[3];
pts = RandomReal[{0, 1}, {50, 2}];
vertices = v /@ pts;
len = Length[pts];
a = 0.0; b = 1.5;
While[a < b,
c = a + 0.5 (b - a);
clusters = Table[
Nearest[pts[[i ;; len]], pts[[i]], {len, c}],
{i, 1, len - 1}];
toEdges[pp : {{_Real, _Real} ..}] :=
UndirectedEdge[v[First[pp]], v[#]] & /@ Rest[pp];
edges = Flatten[toEdges /@ clusters];
g = Graph[vertices, edges];
If[! ConnectedGraphQ[g], a = c, b = c]
];
clusters = Table[
Nearest[pts[[i ;; len]], pts[[i]], {len, b}],
{i, 1, len - 1}];
edges = Flatten[toEdges /@ clusters];
g = Graph[vertices, DirectedEdge @@@ edges,
VertexShapeFunction -> ({Disk[#, 0.007]} &),
EdgeStyle -> Opacity[0.3],
VertexCoordinates -> pts]


Not terribly efficient, of course. 1000 vertices took about 30 sec.

Here's a geometric random graph with a highlighted spanning tree which is minimal with respect to total edge length, yielding an interesting dendritic structure.

-
+1 Or, to push this kind of idea even further, generate points uniformly at random within a region and compute their Euclidean minimum spanning tree. With that as a backdrop you could then add more edges according to any distribution you want. –  whuber Oct 16 '12 at 15:15
@whuber See edit. I did this quite some time ago and, unfortunately, the technique is not wholly within mathematica. It relies on a weighted spanning tree algorithm which, as far as I know, is not implemented in Mathematica. There is a SpanningTree command in the SparseArray context, but I'm not clear on how it works. –  Mark McClure Oct 16 '12 at 15:25

Here is my solution:

ConnectComponents[{a_, b_}] :=
DirectedEdge[RandomChoice[a], RandomChoice[b]];
ConnectedGraph[n_, m_, o___] :=
Module[{vertices = n, edges = m, options = o},
rg = RandomGraph[{vertices, edges}, DirectedEdges -> True];
cc = ConnectedComponents[rg];
edges =
If[Length@cc != 1,
ConnectComponents /@ Partition[cc, 2, 1, 1], {}];
Graph[DeleteDuplicates[ edges~Join~EdgeList[rg]],
Sequence@options]
];

-

With even small (reasonably) edge probabilities this function will generate in a reasonably short time random directed connected graph:

gr[n_, p_] := Module[{
g = RandomGraph[BernoulliGraphDistribution[n, p], DirectedEdges -> True]},
While[Not[ConnectedGraphQ[g]],
g = RandomGraph[BernoulliGraphDistribution[n, p], DirectedEdges -> True]]; g]


Use:

gr[#, .2] & /@ Range[7, 22]


Check:

ConnectedGraphQ /@ %


{True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True}

-

Here's a rejection method:

With[{v = 8 (* vertices *), e = 14 (* edges *)},
NestWhile[RandomGraph[{v, e}, DirectedEdges -> True] &,
Graph[{1 \[UndirectedEdge] 1, 2 \[UndirectedEdge] 2}],
Composition[Not, ConnectedGraphQ]]]


-