Home

# Random Graphs

Sunday 23 August 2015

Randomly generate 2D graphs for toy visualizations.

Random graphs are a vast research area of graph theory, but I just need something simple for a few visualizations. I want to make graphs that represent a rail network between cities, such that neighbouring cities are somewhat connected, and there aren't any long edges that jump halfway across the graph.

## Points

The cities or nodes of the graph are randomly generated 2D points in `[0,1]`. But placing the cities purely at random results in clusters which make it difficult to distinguish individual nodes.

```type Point struct {
X, Y float64
}

type Edge struct {
U, V Point
}
```

I can prevent this by finding the closest existing node before adding another, and rejecting the new point if it would be too close. This is an O(n²) algorithm which is fine for my small n (but there are interesting possible optimizations). There's a danger this loop won't terminate, so I added a hard limit.

```// closest returns the distance from p to the closest point in ps.
func closest(p Point, ps []Point) float64 {
min := 2.0
for _, q := range ps {
if d := dist2(p, q); d < min {
min = d
}
}
return min
}

// dist2 returns the Euclidean distance squared between two points.
func dist2(a, b Point) float64 {
x := a.X - b.X
y := a.Y - b.Y
return x*x + y*y
}

// points returns n nodes so that they're no less that minDist2 apart.
func points(n int, minDist2 float64) []Point {
ps := []Point{ // top-left and bottom-right
{0, 0}, {1, 1},
}
// prevent infinite loop
for i := 0; len(ps) < numPoints && i < 1e4; i++ {
p := Point{rand.Float64(), rand.Float64()}
if closest(p, ps) < minDist2 {
continue
}
ps = append(ps, p)
}
return ps
}
```