1
$\begingroup$

I have some code I've been using to generate some random geometric graphs as fast as possible.

The boundary conditions on the rectangular domain I am using sometimes interferes with a clean measurement of some sensitive exponents.

Can I modify the distance metric between the random points from the Euclidean to the toroidal, which simply implies I have a rectangle with periodic boundary conditions?

I'm able to write out only a simple function which takes two positions and gives their toroidal distance (given this is a rectangle $[0,w] \times [0,h]$), but I may need something a bit more efficient.

For example, this code adds edges randomly between 20 random points in the unit square, but with exponentially greater likelihood when close, according to the Euclidean metric.

edges = Function[{subsets}, 
   Pick[subsets, 
    UnitStep[
     RandomReal[{0, 1}, Length@subsets] - 
      Exp[- Dot[(subsets[[All, 1]] - subsets[[All, 2]])^2, {1., 
          1.}]]], 0]];
makegraphs[vert_] := 
  Graph[vert, UndirectedEdge @@@ edges[Subsets[vert, {2}], 1], 
   VertexCoordinates -> vert];
(*construct v as a list of packed arrays*)
ngraphs = 1;
randompoints = 
  Table[RandomReal[{-1/2, 1/2}, {20, 2}], {i, 1, ngraphs}];
graphs = makegraphs /@ randompoints; // AbsoluteTiming

{0.000722, Null}

It simply generates a random geometric graph. With

graphs[[1]]

I get

enter image description here

I cannot see a simple way to get the connectivity to "wrap around", and give the graph on the surface of a "flat torus" i.e. the rectangle with periodic boundary conditions.

$\endgroup$
  • 1
    $\begingroup$ There is too much noise in your code. What does PoissonDistribution have to do with the question? Give us a Minimal Working Example. $\endgroup$ – Hector Aug 13 '18 at 16:07
  • $\begingroup$ Ok I will edit it, it is a portion of a longer code $\endgroup$ – Alexander Kartun-Giles Aug 13 '18 at 16:52
  • $\begingroup$ Ok I added simpler code. $\endgroup$ – Alexander Kartun-Giles Aug 13 '18 at 19:40
  • 2
    $\begingroup$ IGGeometricGame from IGraph/M does have a toroidal option, but otherwise you can't change the metric with it. $\endgroup$ – Szabolcs Aug 14 '18 at 15:13
1
$\begingroup$

Between your original post and this edit, it seems to me that you want to solve the following problem:

Given a set of 2D points in a toroid [0,w]x[0,h], compute a table of distances in an efficient way.


The following function assumes that width and height have been given some suitable values. It uses Mod to “wrap around”.

toroidalDelta[pointA_, pointB_] := 
  With[{delta = pointA - pointB}, {
    Min[Mod[{delta[[1]], -delta[[1]]}, width]], 
    Min[Mod[{delta[[2]], -delta[[2]]}, height]]
  }];

Let us check its action

width = 1; height = 2;
toroidalDelta[{0.1, 0.2}, {0.9, 1.8}]
(*{0.2, 0.4}*)

Note that the delta in the x direction wrapped around 1.0 while the delta in the y direction wrapped around 2.0 (as expected).

Let us check that the delta does not depend on the order of the points:

toroidalDelta[{0.9, 1.8}, {0.1, 0.2}]
(*{0.2, 0.4}*)

Once you have the delta, getting the norm is trivial:

toroidalNorm = Norm[toroidalDelta[##]] &;

From there, you can compute the probabilities with your favorite distribution. Using the function in your post:

prob = Exp[-toroidalNorm[##]] &;
prob[{0.9, 1.8}, {0.1, 0.2}]
(*0.639407*)

You might want to normalize the distribution. Also, take into acount (or not) the fact that width != height; but that is the subject for a different question.

Let us generate a list of random points in [0,1]x[0,2] and pick some random edges:

noPoints = 40; width = 1; height = 2;
points = Transpose[{RandomReal[{0, width}, {noPoints}], 
    RandomReal[{0, height}, {noPoints}]}];
edges = Reap[
    Table[If[prob[points[[i]], points[[j]]] > 0.6, 
      Sow[{points[[i]], points[[j]]}]], 
      {i, noPoints}, {j, i + 1, noPoints}]][[2, 1]];

Note that Sow is collecting the coordinates of the points instead of their indices because those points will be visualized using Graphics3D. You might want to change the sowing instruction to Sow[{i,j}] if you want to use those edges within a Graph. The visualization in 3D is important because it shows that the edges do not cross the holes.

from2DtoCyl[
   point_] := {(3 + Cos[(2 π)/width point[[1]]]) Sin[(2 π)/
      height point[[2]]], (3 + Cos[(2 π)/width point[[1]]]) Cos[(
      2 π)/height point[[2]]], Sin[(2 π)/width point[[1]]]};
Graphics3D[{PointSize[.03], Red, Point[from2DtoCyl /@ points], Black, 
  Line /@ Map[from2DtoCyl, edges, {2}], Opacity[0.05], 
  ParametricPlot3D[{(3 + Cos[v]) Sin[u], (3 + Cos[v]) Cos[u], 
     Sin[v]}, {u, 0, 2 Pi}, {v, 0, 2 Pi}][[1]]}]

enter image description here

$\endgroup$
  • $\begingroup$ This is ideal, thank you. Initially I saw it as building a random geometric graph with toroidal boundary conditions, but yes it is of course no more difficult than constructing toroidal distances on a rectangle. $\endgroup$ – Alexander Kartun-Giles Aug 14 '18 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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