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
}

...continue reading...

Older posts:

About