*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 }

I added two special points at (0,0) and (1,1).

## Edges

The roads or edges of the graph are randomly picked such that shorter edges are preferred, but not exclusively.
For every node, I attempt to add 3 edges to other points. I call this `degree`

in the code, but that's
slightly misleading as we have a chance to add each edge twice. The average
degree of the finished graph ends up
higher than `degree`

.

// edges attempts to place degree random edges on each node // such that nearby neighbours are mostly connected. func edges(ps []Point, degree int) []Edge { var es []Edge sorted := make([]Point, len(ps)) copy(sorted, ps) for _, p := range ps { sort.Sort(closestTo{p, sorted}) count := 0 // avoid self edges: sorted[0] == p for _, q := range sorted[1:] { if rand.Intn(2) != 0 { es = append(es, Edge{p, q}) count++ if count >= degree { break } } } } return es }

I sort the points by how far they are from the node in question and give each a 50% chance of being chosen. Nothing guarantees that the result is a connected graph, but in practice this has not been a problem.

type closestTo struct { p Point ps []Point } func (c closestTo) Less(i, j int) bool { return dist2(c.p, c.ps[i]) < dist2(c.p, c.ps[j]) } func (c closestTo) Len() int { return len(c.ps) } func (c closestTo) Swap(i, j int) { c.ps[i], c.ps[j] = c.ps[j], c.ps[i] }

## SVG

These graphs are rendered as an SVG and I use d3 as a simple way of interacting with the elements.d3.select("#graph").append("line") .attr("x1", edges[i].U.X * scale + border) .attr("x2", edges[i].V.X * scale + border) .attr("y1", edges[i].U.Y * scale + border) .attr("y2", edges[i].V.Y * scale + border) .attr("stroke", "red");