Random Geometric Graphs

Question

I'm trying to implement an application which uses random geometric graphs in Mathematica, but it seems Mathematica lacks the functionality. I need the following functionalities:

1. Generate a set of uniformly distributed vertices on $[0,1]^2$ with certain properties (this really helps)
2. Add an edge in between the vertices that are closer than a given radius $d$
3. Display the graph (this is not like a regular graph display since the location of each vertex is important)
4. Generate some random source-destination pairs and find the shortest path between them
5. Highlight the path on the displayed graph.

Note that, Mathematica has all of the required functionality for non-geometric graphs. However, when it comes to the geo-graphs, the functionality is quite useless. Here is the code I already have:

Module[
 {nOld, kOld, v, edges},
 nOld = -1;
 kOld = -1;
 Manipulate[
  If[
   n != nOld,
   v = RandomReal[{0, 1}, {n, 2}];
   nOld = n
   ];

  edges = 
   Select[Flatten[Table[{a, b}, {a, v}, {b, v}], 
     1], (#[[1, 1]] > #[[2, 1]] && 
       EuclideanDistance[#[[1]], #[[2]]] < d) &];

  Graphics[
   {Red, Point[v],
    Blue, Thin, Line /@ edges
    }
   ]
  ,
  {n, 10, 100, 10},
  {d, 0, 1}
  ]
 ]

It generates and shows the random graph. But generating and highlighting the shortest paths are not so simple since I don't have any data-structure to keep the graph. What is the best way to implement a geo-graph in Mathematica? Sparse matrices or System`Graph or Combinatorica`Graph? Can I use some of the built-in graph functions of Mathematica to implement geo-graphs?

Answer 1

Slight modification of your code allows using Graph and all options that come with it:

 Module[{nOld, kOld, v, vertices, edges}, nOld = -1; kOld = -1;
 Manipulate[If[n != nOld, v = RandomReal[{0, 1}, {n, 2}];
 nOld = n]; vertices = Range@n;
 edges =   Select[Flatten[Table[{a, b}, {a, v}, {b, v}], 1],
   (#[[1, 1]] > #[[2, 1]] &&  EuclideanDistance[#[[1]], #[[2]]] < d) &];
 edgelst = Map[Rule[First@First@Position[v, #[[1]]], 
     First@First@Position[v, #[[2]]]] &, edges];
 Graph[vertices, edgelst, VertexCoordinates -> v, 
    DirectedEdges -> False], {n, 10, 100, 10}, {d, 0, 1}]]

screenshot:

EDIT: Adding RandomSample, HighlightGraph and ShortestPath:

Module[{nOld, kOld, v, vertices, edges, edgelst}, nOld = -1;  kOld = -1;
Manipulate[If[n != nOld, v = RandomReal[{0, 1}, {n, 2}]; 
  vertices = Range@n; {source, destination} = RandomSample[vertices, 2];
   nOld = n];
edges = Select[Flatten[Table[{a, b}, {a, v}, {b, v}], 1], 
    (#[[1, 1]] > #[[2, 1]] && EuclideanDistance[#[[1]], #[[2]]] < d) &];
edgelst =  Map[Rule[First@First@Position[v, #[[1]]], 
  First@First@Position[v, #[[2]]]] &, edges];
gr = Graph[vertices, edgelst, VertexCoordinates -> v,  DirectedEdges -> False]; 
HighlightGraph[gr, 
  PathGraph[FindShortestPath[gr, vrtx1, vrtx2]]], 
{n, 10, 100, 10}, {d, 0, 1}, Delimiter,  Style["shortestPath", "Subsection"], 
{{vrtx1, source, "fromVertex"}, vertices}, 
{{vrtx2, destination, "toVertex"}, vertices}]]

screenshot:

Answer 2

In the latest version of Mathematica, SpatialGraphDistribution can be use to generate random geometric graphs:

n = 30; d = 0.5;
g = RandomGraph[SpatialGraphDistribution[n, d]];
{source, target} = RandomInteger[{1, n}, 2];
path = FindShortestPath[g, source, target];
HighlightGraph[g, PathGraph[path]]

Answer 3

Change your edges to the indices:

edges = Select[Flatten[Table[{a, b}, {a, n}, {b, a + 1, n}], 1],
    (EuclideanDistance[v[[#[[1]]]], v[[#[[2]]]]] < d) &];

And then tell the Graph where to locate the vertices:

g = Graph[Range[n], edges, VertexCoordinates -> v];

A shortest path display can be taken straight from the help:

HighlightGraph[g, PathGraph[FindShortestPath[g,
   RandomInteger[{1, n}], RandomInteger[{1, n}]]]]