Tell me more ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.
up vote 5 down vote favorite
1

How to generate random directed connected graph?

I need to create graph which will pass:

ConnectedGraphQ[^]
share|improve this question
You've seen RandomGraph[]? It has a DirectedEdges option... – J. M.♦ 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
2  
@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
2  
@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
2  
@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
show 5 more comments

4 Answers

up vote 6 down vote

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]

enter image description here

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

enter image description here

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.

enter image description here

share|improve this answer
+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
1  
@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
up vote 1 down vote accepted

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]
   ];
share|improve this answer
up vote 1 down vote

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]

enter image description here

Check:

ConnectedGraphQ /@ %

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

share|improve this answer
up vote 1 down vote

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]]]

random directed connected graph

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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