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:
- RandomGraph
- From: Gaudium <nesearal@gmail.com>
- RandomGraph