Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: RandomGraph

  • To: mathgroup at smc.vnet.net
  • Subject: [mg86225] Re: [mg86196] RandomGraph
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Thu, 6 Mar 2008 03:00:02 -0500 (EST)
  • References: <200803050841.DAA19502@smc.vnet.net>

Gaudium wrote:
> Hello All,
> 
> 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? Thank you.
> 
> Nese Aral

This should work reasonably well even for large graphs. It does not do 
error checking to make sure lengths agree, entries are nonnegative 
integers, etc. but that is not hard to add if needed.

randomGraph[ins_?VectorQ, outs_?VectorQ] := Module[
   {tot=Total[ins], inedges, outedges},
   inedges = Flatten[MapIndexed[Table[#2,{#1}]&, ins], 2];
   outedges = Flatten[MapIndexed[Table[#2,{#1}]&, outs], 2];
   inedges = RandomSample[inedges, tot];
   Transpose[{outedges,inedges}]
   ]

Using your data:

ins = {1, 2, 2, 1, 4, 3, 2, 3, 5, 5, 2, 1};
outs = {2, 1, 1, 2, 1, 1, 5, 5, 2, 7, 3, 1};

In[34]:= InputForm[randomGraph[ins, outs]]

Out[34]//InputForm=
{{1, 11}, {1, 2}, {2, 10}, {3, 12}, {4, 6}, {4, 10},
  {5, 6}, {6, 1}, {7, 3}, {7, 5}, {7, 11}, {7, 8},
  {7, 7}, {8, 5}, {8, 9}, {8, 4}, {8, 10}, {8, 6}, {9, 8},
  {9, 7}, {10, 5}, {10, 5}, {10, 10}, {10, 8}, {10, 2},
  {10, 9}, {10, 9}, {11, 9}, {11, 9}, {11, 10}, {12, 3}}


Daniel Lichtblau
Wolfram Research


  • References:
  • Prev by Date: Re: FindRoot solving of Excel input columns
  • Next by Date: Re: RandomGraph
  • Previous by thread: RandomGraph
  • Next by thread: Re: RandomGraph