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

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 == 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");
```