Re: RandomGraph

*To*: mathgroup at smc.vnet.net*Subject*: [mg86212] Re: RandomGraph*From*: mcmcclur at unca.edu*Date*: Thu, 6 Mar 2008 02:57:34 -0500 (EST)*References*: <fqlmrq$jh4$1@smc.vnet.net>

On Mar 5, 3:50 am, Gaudium <nesea... at gmail.com> wrote: > How can I construct a directed random graph with exactly 12 vertices > and 31 edges, where the indegrees of the vertices are {1, 2, 2, 1, 4, > 3, 2, 3, 5, 5, 2, 1} and outdegrees of the vertices are {2, 1, 1, 2, > 1, 1, 5, 5, 2, 7, 3, 1} respectively? We'll represent each edge as a rule: v1 -> v2. We then generate a list of all possible v1s and v2s, duplicating entries adjacent to multiple edges. Finally, we pair up the v1 set with a random permutation of the v2 set. Here's the result. inDegrees={1,2,2,1,4,3,2,3,5,5,2,1}; outDegrees={2,1,1,2,1,1,5,5,2,7,3,1}; ins = Flatten[MapIndexed[Table[#2, {#1}] &, inDegrees]]; outs = Flatten[MapIndexed[Table[#2, {#1}] &, outDegrees]]; G = Inner[Rule, outs, RandomSample[ins], List]; GraphPlot[G, VertexLabeling -> True, DirectedEdges -> True] The above graph will frequently have self-loops. We can avoid the self-loops, if desired, by generating the random sample of in vertices more carefully. Here's one approach that works most of the time given your degree sequences. ins = Flatten[MapIndexed[Table[#2, {#1}] &, inDegrees]]; outs = Flatten[MapIndexed[Table[#2, {#1}] &, outDegrees]]; ins2 = {}; addIn[n_] := Module[{in}, in = RandomChoice[Select[ins, # != outs[[n]] &]]; ins2 = Append[ins2, in]; ins = Delete[ins, First[Position[ins, in]]];]; addIn /@ Range[Length[outs]]; G = Inner[Rule, outs, ins2, List]; GraphPlot[G, VertexLabeling -> True, DirectedEdges -> True] This works by moving points one at a time from ins to ins2, always making sure that the new point in ins2 doesn't match the corresponding point in outs. This can ultimately fail near the end, though, but there is a warning and you can just try again. Mark