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[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");

Previous (A Lazy Sieve of Eratosthenes)