# random geometric graph generation problem

I'm new to Mathematica. I'm trying to generate a random geometric graph in which to have a secure link between any two arbitrary nodes they should share a common key in their key rings (have assigned some keys to each node) in order to get a random key graph but when I write ShowGraph[g] I'm unable to plot the graph. Here is my code.

v = {};
If[Length[v] == 0,
n = 100,(*Total number of nodes*)
n = Length[v];(*For pre-defined topologies*)
]
nprime = 20;(*Average number of neighbours per node*)rc =
N[Sqrt[(nprime + 1)/(n*\[Pi])]]    (*Transmission range*)
rs = rc;(*Sensory range*)K = 4;(*Key ring size*)
Pstart = 10;(*Initial key pool size*)
Pend = 10;(*Last key pool size*)
If[Length[v] == 0,
nsim = 50,(*Number of iterations per P*)
nsim = 1;(*Only makes sense to simulate once for a fixed topology*)
];
edist[xi_, yi_, xj_, yj_] := {Sqrt[(xi - xj)^2 + (yi - yj)^2], xi, yi};

If[euclidean == True,
dist[xi_, yi_, xj_, yj_] := edist[xi, yi, xj, yj],
dist[xi_, yi_, xj_, yj_] := tdist[xi, yi, xj, yj]];


(* * * * * * * * * * * Main calculation * * * * * * * * * **)

(* * * * * * * * * * * * Main calculation * * * * * * * * * * * *)
For[P = Pstart, P <= Pend, P++,
For[sim = 1, sim <= nsim, sim++,
SeedRandom[sim];
(* Generate vertices if not using a fixed topology {{{ *)
If[Length[v] == 0 || sim > 1,
v = {};
For[i = 1, i <= n, i++, v = Append[v, {{Random[], Random[]}}]];
];
g = Graph[{}, v];
Print["Vertices: ", v]; (* Debug *)

(* Distribute keys randomly {{{ *)
keyrings = {};
For[i = 1, i <= n, i++,
keyring = {};
If[P == K,
For[k = 1, Length[keyring] < K, k++,
keyring = Append[keyring, k]
],
(* P > K *)
For[k = 1, Length[keyring] < K, k++,
key = Random[Integer, {1, P}];
If[MemberQ[keyring, key] == False,
keyring = Append[keyring, key]
]
]
];
keyrings = Append[keyrings, keyring];
];
Print["Key rings: ", keyrings]; (* Debug *)

(* Determine edges {{{ *)
For[i = 1, i <= n, i++,
For[j = i + 1, j <= n, j++,
xi = Extract[Extract[Extract[v, i], 1], 1];
xj = Extract[Extract[Extract[v, j], 1], 1];
yi = Extract[Extract[Extract[v, i], 1], 2];
yj = Extract[Extract[Extract[v, j], 1], 2];
If[dist[xi, yi, xj, yj][] < rc,

If[Extract[keyrings, {i}] \[Intersection]
Extract[keyrings, {j}] != {},
(* Else *)
Print["No secure link between ",  i, " ", j]
]
]
]
];
(*g=Graph[vertices,edgelst,VertexCoordinates\[Rule]v,
DirectedEdges\[Rule]False];*)
ShowGraph[g];
]
];


What’s the problem? Can anyone help?

• If you try to see the contents of g you will find out that you exceed the recursion limit 1024. So the Graph is not formed correctly... Also to use ShowGraph you must load Needs["Combinatorica"] Dec 10, 2013 at 8:05
• You must first form the graph correctly... Dec 10, 2013 at 9:20
• how can i do that??? Dec 10, 2013 at 9:45
• i corrected the code,it is executing properly but still i'm unable to plot the graph....if i include << DiscreteMathCombinatorica it gives error like"Get::noopen: Cannot open DiscreteMathCombinatorica." >> and without this it runs correctly it's may be because i'm using mathematica9... what should i do to plot the graph??plzz help... Dec 10, 2013 at 13:06
• Please update your code above so I can check properly. Dec 10, 2013 at 13:35

You should evaluate Needs["Combinatorica"] prior to run your main evaluation code. If so, you should see your Graph by doing ShowGraph.

And here's another code you can do with System graph functionality:

Options[RandomKeyGeoGraph] = Join[Options[Graph], {DistanceFunction -> Automatic}];

RandomKeyGeoGraph[n_, r_, keyrings_List, opt : OptionsPattern[]] :=
Block[{g,dist,opts},
If[Length[keyrings] != n || ! VectorQ[keyrings, ListQ], Return["Invalid Keyrings."]];
dist = OptionValue[DistanceFunction];
opts = FilterRules[{opt}, Options[Graph]];

g = RandomGraph[SpatialGraphDistribution[n, r, DistanceFunction -> dist], opts];
EdgeDelete[g,
EdgeList[g, x_ \[UndirectedEdge] y_ /; Length[Intersection @@ keyrings[[{x, y}]]] == 0]]
]

RandomKeyGeoGraph[n_, r_, kpsize_Integer: 10, krsize_Integer: 4, opt : OptionsPattern[]] :=
Block[{keypool, keyrings},
keypool = Range[kpsize];
keyrings = Table[RandomSample[keypool, krsize], {i, 1, n}];
RandomKeyGeoGraph[n, r, keyrings, opt]
]


With Vitaliy's Manipulate:

Manipulate[
If[p < k, k = p];
keyrings = Table[RandomSample[Range[p], k], {i, 1, n}];
SeedRandom[s];
g = RandomKeyGeoGraph[n, r, keyrings, VertexSize -> {"Scaled", .01},
VertexStyle -> Red, PlotRange -> {{-.01, 1.01}, {-.01, 1.01}}];
vcoord = GraphEmbedding[g];

Overlay[{If[range,
ClickPane[
Graphics[{Dynamic[rangeCircle[pt, r, vcoord],
TrackedSymbols :> {vcoord, pt, r}]},
PlotRange -> {{-.01, 1.01}, {-.01, 1.01}}], (pt = #) &],
Graphics[{}]], g}, All, 1],

{keyrings, ControlType -> None},
{vcoord, ControlType -> None},
{g, ControlType -> None},
{{pt, {1/2, 1/2}}, ControlType -> None},
{{s, 2, "configuration"}, 1, 100, 1,  Appearance -> "Labeled"},
{{k, 4, "keyring size"}, 1, 10, 1, Appearance -> "Labeled"},
{{p, 10, "key pool size"}, 1, 50, 1, Appearance -> "Labeled"},
{{n, 256, "points number"}, 10, 500, 1, Appearance -> "Labeled"},
{{r, .1, "nearest radius"}, .001, .5, Appearance -> "Labeled"},
{{range, False, "show range disk"}, {True, False}},
Initialization -> {
rangeCircle[c_List, r_, vcoord_List] :=
Block[{center},
center = First[Nearest[vcoord, c, 1]];
{Yellow, Disk[center, r], Green,
Disk[#, .015] & /@ Rest[Nearest[vcoord, center, {Infinity, r}]],
Orange, Disk[center, .015]}
];
rangeCircle[___] := {}
}]


Random geometric graphs are built-in in Mathematica:

RandomGraph[SpatialGraphDistribution[256, .1]] Compare to Wikipedia: random geometric graph.

?SpatialGraphDistribution If you want an exercise to do it old school, here is functional code:

Manipulate[

SeedRandom[s];

vts = Thread[Rule[RandomReal[1, {#, 2}], Range[#]]] &[n];

edgs = DeleteCases[
Union[Sort /@
UndirectedEdge[#1, #2]] & @@@ (({#,
Nearest[vts[[All, 1]], #, {Infinity, r}]} & /@
vts[[All, 1]]) /. vts)]], x_ \[UndirectedEdge] x_];

Graph[Range[n], edgs, VertexCoordinates -> vts[[All, 1]],
VertexStyle -> Red, VertexSize -> {"Scaled", .01},
PlotRange -> {{0, 1}, {0, 1}}]

, {vts, ControlType -> None}
, {edgs, ControlType -> None}
, {{s, 2, "configuration"}, 1, 100, 1, Appearance -> "Labeled"}
, {{n, 256, "points number"}, 10, 500, 1, Appearance -> "Labeled"}
, {{r, .1, "nearest radius"}, .001, .5, Appearance -> "Labeled"}
] • thank u sir for ur response, but sir i don't want to use built-in random geometric graph of mathematica...i want to generate a random graph to implement wireless sensor network functionality in which any two nodes can have a secure link only when the two nodes share a common key(that i stored in each node's keyring)...for that i've written the code it executes properlt but it is not showing graph whwn i write ShowGraph(g)...can u plz help me in generting such random graph based on random key predistribution scheme.... Dec 11, 2013 at 6:19
• i am unable to load combinatorica packages in my program that is why it is not showing graph...i tried all sort of things to include it but nothing worked...plz help. Dec 11, 2013 at 12:49
• @user89335 I added keyring detection in Manipulate. Yellow edges represent edges in the range but don't share key rings. Dec 12, 2013 at 2:44
• @halmir you were correct to post your code as a new answer. But it is against site etiquette to alter significantly code of another person - not due to mistakes, but due to change of the concept. It confuses things. I changed it back. Please in future just post as a new answer - as you already did in this case. In general - good job on your code. Dec 12, 2013 at 9:24