Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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][[1]] < rc, 

  If[Extract[keyrings, {i}] \[Intersection] 
     Extract[keyrings, {j}] != {},
                        g = AddEdge[g, {{i, 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?

share|improve this question
    
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 << DiscreteMath`Combinatorica` it gives error like"Get::noopen: Cannot open DiscreteMath`Combinatorica`." >> 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
show 8 more comments

2 Answers 2

up vote 1 down vote accepted

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[___] := {}
 }]
share|improve this answer
    
+1 great effort, nice help for community! –  Vitaliy Kaurov Dec 12 '13 at 9:13
add comment

Random geometric graphs are built-in in Mathematica:

RandomGraph[SpatialGraphDistribution[256, .1]]

enter image description here

Compare to Wikipedia: random geometric graph.

?SpatialGraphDistribution

enter image description here

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 /@ 
     Flatten[Thread[
         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"}
 ]

enter image description here

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.