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

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