# 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"] – tchronis Dec 10 '13 at 8:05
• You must first form the graph correctly... – tchronis Dec 10 '13 at 9:20
• how can i do that??? – user89335 Dec 10 '13 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... – user89335 Dec 10 '13 at 13:06
• Please update your code above so I can check properly. – tchronis Dec 10 '13 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.... – user89335 Dec 11 '13 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. – user89335 Dec 11 '13 at 12:49
• @user89335 I added keyring detection in Manipulate. Yellow edges represent edges in the range but don't share key rings. – halmir Dec 12 '13 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. – Vitaliy Kaurov Dec 12 '13 at 9:24