yourbasic · korthaj · May 17, 2017 · May 11, 2017 · May 14, 2017 · May 14, 2017
diff --git a/README.md b/README.md
@@ -1,16 +1,25 @@
 # Your basic graph
 
-Golang library of basic graph algorithms
+### Golang library of basic graph algorithms
 
 ![Topological ordering](top.png)
 
 *Topological ordering, image by [David Eppstein][de], [CC0 1.0][cc010].*
 
-### Generic graph algorithms
+This library offers efficient and well-tested algorithms for
+
+- breadth-first and depth-first search,
+- topological ordering,
+- strongly and weakly connected components,
+- bipartion,
+- shortest paths,
+- maximum flow,
+- Euler walks,
+- and minimum spanning trees.
 
 The algorithms can be applied to any graph data structure implementing
-the two Iterator methods: Order, which returns the number of vertices,
-and Visit, which iterates over the neighbors of a vertex.
+the two `Iterator` methods: `Order`, which returns the number of vertices,
+and `Visit`, which iterates over the neighbors of a vertex.
 
 All algorithms operate on directed graphs with a fixed number
 of vertices, labeled from 0 to n-1, and edges with integer cost.
@@ -21,21 +30,21 @@ is both directed and undirected.
 
 ### Graph data structures
 
-The type Mutable represents a directed graph with a fixed number
+The type `Mutable` represents a directed graph with a fixed number
 of vertices and weighted edges that can be added or removed.
 The implementation uses hash maps to associate each vertex
 in the graph with its adjacent vertices. This gives constant
 time performance for all basic operations.
 
-The type Immutable is a compact representation of an immutable graph.
+The type `Immutable` is a compact representation of an immutable graph.
 The implementation uses lists to associate each vertex in the graph
 with its adjacent vertices. This makes for fast and predictable
 iteration: the Visit method produces its elements by reading
-from a fixed sorted precomputed list. This type supports multigraphs.
+from a fixed sorted precomputed list.
 
 ### Virtual graphs
 
-The subpackage graph/build offers a tool for building virtual graphs.
+The subpackage `graph/build` offers a tool for building virtual graphs.
 In a virtual graph no vertices or edges are stored in memory,
 they are instead computed as needed. New virtual graphs are constructed
 by composing and filtering a set of standard graphs, or by writing
@@ -61,7 +70,7 @@ There is an online reference for the package at
 * Version numbers adhere to [semantic versioning][sv].
 
 The only accepted reason to modify the API of this package is to
-handle bug fixes that can't be resolved in any other reasonable way.
+handle issues that can't be resolved in any other reasonable way.
 
 New features and performance enhancements are limited to basic
 algorithms and data structures, akin to the ones that you might find

diff --git a/build/build.go b/build/build.go
@@ -68,15 +68,15 @@ type Virtual struct {
 	visit  func(v int, a int, do func(w int, c int64) (skip bool)) (aborted bool)
 }
 
-// FilterFunc is a function that tells if there is an edge from v to w.
+// FilterFunc is a function that tells if there is a directed edge from v to w.
 // The nil value represents an edge functions that always returns true.
 type FilterFunc func(v, w int) bool
 
 // CostFunc is a function that computes the cost of an edge from v to w.
 // The nil value represents a cost function that always returns 0.
 type CostFunc func(v, w int) int64
 
-// Cost returns a CostFunc which always returns n.
+// Cost returns a CostFunc that always returns n.
 func Cost(n int64) CostFunc {
 	return func(int, int) int64 { return n }
 }
@@ -432,15 +432,15 @@ func (g *Virtual) AddCostFunc(c CostFunc) *Virtual {
 	return &res
 }
 
-// Order returns the number of vertices in this graph.
+// Order returns the number of vertices in the graph.
 func (g *Virtual) Order() int {
 	return g.order
 }
 
-// Degree returns the number of neighbors of v.
+// Degree returns the number of outward directed edges from v.
 func (g *Virtual) Degree(v int) int {
 	if v < 0 || v >= g.order {
-		return 0
+		panic("vertex out of range")
 	}
 	return g.degree(v)
 }

diff --git a/build/cartesian.go b/build/cartesian.go
@@ -2,7 +2,7 @@ package build
 
 import "strconv"
 
-// Cartesian returns the cartesian product of g1 and g2;
+// Cartesian returns the cartesian product of g1 and g2:
 // a graph whose vertices correspond to ordered pairs (v1, v2),
 // where v1 and v2 are vertices in g1 and g2, respectively.
 // The vertices (v1, v2) and (w1, w2) are connected by an edge if

diff --git a/build/cycle.go b/build/cycle.go
@@ -1,7 +1,7 @@
 package build
 
-// Cycle returns a virtual cycle graph with the edges
-// {0, 1}, {1, 2}, {2, 3},... , {n-1, 0}.
+// Cycle returns a virtual cycle graph with n vertices and
+// the edges {0, 1}, {1, 2}, {2, 3},... , {n-1, 0}.
 func Cycle(n int) *Virtual {
 	switch {
 	case n < 0:

diff --git a/build/edgeset.go b/build/edgeset.go
@@ -24,7 +24,7 @@ func NoEdges() EdgeSet {
 	}
 }
 
-// Edge returns a set consisting of the single edge {v, w}, where v ≠ w.
+// Edge returns a set consisting of a single edge {v, w}, v ≠ w, of zero cost.
 func Edge(v, w int) EdgeSet {
 	if v < 0 || w < 0 || v == w {
 		return NoEdges()
@@ -35,7 +35,7 @@ func Edge(v, w int) EdgeSet {
 	}
 }
 
-// Contains tells if the set contains the edge from v to w.
+// Contains tells if the set contains the edge {v, w}.
 func (e EdgeSet) Contains(v, w int) bool {
 	switch {
 	case e.Keep != nil && !e.Keep(v, w):

diff --git a/build/examples_test.go b/build/examples_test.go
@@ -10,10 +10,10 @@ import (
 // Find a shortest path going back and forth between
 // two sets of points in the plane.
 func Example_euclid() {
-	type point struct{ x, y int }
+	type Point struct{ x, y int }
 
 	// Euclidean distance.
-	euclid := func(p, q point) float64 {
+	Euclid := func(p, q Point) float64 {
 		xd := p.x - q.x
 		yd := p.y - q.y
 		return math.Sqrt(float64(xd*xd + yd*yd))
@@ -22,7 +22,7 @@ func Example_euclid() {
 	// 0     3
 	// 1     4
 	// 2     5
-	points := []point{
+	points := []Point{
 		{0, 0}, {0, 1}, {0, 2},
 		{4, 0}, {4, 1}, {4, 2},
 	}
@@ -32,7 +32,7 @@ func Example_euclid() {
 	// and then apply a cost function to the edges of the graph.
 	g := build.Kmn(3, 3).AddCostFunc(func(v, w int) int64 {
 		// Distance to three decimal places.
-		return int64(1000 * euclid(points[v], points[w]))
+		return int64(1000 * Euclid(points[v], points[w]))
 	})
 
 	// Find a shortest path from 0 to 2.

diff --git a/build/grid.go b/build/grid.go
@@ -2,10 +2,10 @@ package build
 
 import "strconv"
 
-// Grid returns a virtual graph whose vertices correspond to points in the plane
-// with integer coordinates, y-coordinates being in the range 0..m-1,
-// and x-coordinates in the range 0..n-1. Two vertices are connected
-// by an edge whenever the corresponding points are at distance 1.
+// Grid returns a virtual graph whose vertices correspond to integer
+// points in the plane: y-coordinates being in the range 0..m-1,
+// and x-coordinates in the range 0..n-1. Two vertices of a grid
+// are adjacent whenever the corresponding points are at distance 1.
 //
 // Point (x, y) gets index nx + y, and index i corresponds to the point (i/n, i%n).
 func Grid(m, n int) *Virtual {

diff --git a/build/match.go b/build/match.go
@@ -3,7 +3,7 @@ package build
 // Match connects g1 to g2 by matching vertices in g1 with vertices in g2.
 // Only vertices belonging to the bridge are included,
 // and the vertices are matched in numerical order.
-// The vertices of g2 are renumbered before the operation:
+// The vertices of g2 are renumbered before the matching:
 // vertex v ∊ g2 becomes v + g1.Order() in the new graph.
 func (g1 *Virtual) Match(g2 *Virtual, bridge EdgeSet) *Virtual {
 	n := g1.order + g2.order

diff --git a/build/tensor.go b/build/tensor.go
@@ -2,7 +2,7 @@ package build
 
 import "strconv"
 
-// Tensor returns the tensor product of g1 and g2;
+// Tensor returns the tensor product of g1 and g2:
 // a graph whose vertices correspond to ordered pairs (v1, v2),
 // where v1 and v2 are vertices in g1 and g2, respectively.
 // The vertices (v1, v2) and (w1, w2) are connected by an edge whenever

diff --git a/build/vertexset.go b/build/vertexset.go
@@ -3,8 +3,8 @@ package build
 import "sort"
 
 // VertexSet represents a set of vertices in a graph.
-// The zero value of a VertexSet is the universe,
-// which represents all vertices in a graph.
+// The zero value of a VertexSet is the universe;
+// the set containing all vertices.
 type VertexSet struct {
 	// A set is an immutable sorted list of non-empty disjoint intervals.
 	// The zero value VertexSet{nil} represents the universe.
@@ -90,7 +90,7 @@ func (s VertexSet) rank(n int) int {
 	return in.index + n - in.a
 }
 
-// Contains tells if v is a member of set s.
+// Contains tells if v is a member of the set.
 func (s VertexSet) Contains(v int) bool {
 	switch {
 	case s.set == nil:

diff --git a/example_dfs_test.go b/example_dfs_test.go
@@ -64,7 +64,8 @@ func (d *DFSData) dfsVisit(g graph.Iterator, v int) {
 	d.Finish[v] = d.Time
 }
 
-// An implementation of DFS demonstrating how to use this package.
+// An implementation of depth-first search
+// demonstrating how to use this package.
 func Example_dFS() {
 	// Build a small directed graph:
 	//

diff --git a/examples_test.go b/examples_test.go
@@ -17,11 +17,11 @@ func Example_basics() {
 	g.AddBoth(1, 3)
 
 	// The vertices of all graphs in this package are numbered 0..n-1.
-	// The edge iterator is a method called Visit; it calls
-	// a do function for each neighbor of a given vertex. Together
-	// with the Order method—which returns the number of vertices
-	// in a graph—it constitutes an Iterator. All algorithms in this
-	// package operate on any graph implementing this interface.
+	// The edge iterator is a method called Visit; it calls a function
+	// for each neighbor of a given vertex. Together with the Order
+	// method — which returns the number of vertices in a graph — it
+	// constitutes an Iterator. All algorithms in this package operate
+	// on any graph implementing this interface.
 
 	// Visit all edges of a graph.
 	for v := 0; v < g.Order(); v++ {
@@ -118,9 +118,8 @@ func ExampleEulerDirected() {
 	g.AddBoth(0, 1)
 	g.Add(1, 2)
 
-	walk, _ := graph.EulerDirected(g)
-	fmt.Println(walk)
-	// Output: [1 0 1 2]
+	fmt.Println(graph.EulerDirected(g))
+	// Output: [1 0 1 2] true
 }
 
 // Find an Euler walk in an undirected graph.
@@ -135,10 +134,9 @@ func ExampleEulerUndirected() {
 	g.AddBoth(2, 3)
 	g.AddBoth(3, 3)
 
-	walk, _ := graph.EulerUndirected(g)
-	fmt.Println(walk)
+	fmt.Println(graph.EulerUndirected(g))
 	// Output:
-	// [1 3 3 2]
+	// [1 3 3 2] true
 }
 
 // Find a shortest path between two vertices in a graph.

diff --git a/graph.go b/graph.go
@@ -2,9 +2,10 @@
 //
 // Generic graph algorithms
 //
-// The algorithms can be applied to any graph data structure implementing
-// the two Iterator methods: Order, which returns the number of vertices,
-// and Visit, which iterates over the neighbors of a vertex.
+// The algorithms in this library can be applied to any graph data
+// structure implementing the two Iterator methods: Order, which returns
+// the number of vertices, and Visit, which iterates over the neighbors
+// of a vertex.
 //
 // All algorithms operate on directed graphs with a fixed number
 // of vertices, labeled from 0 to n-1, and edges with integer cost.
@@ -77,7 +78,7 @@ type edge struct {
 }
 
 // String returns a description of g with two elements:
-// the number of vertices, followed by a list of all edges.
+// the number of vertices, followed by a sorted list of all edges.
 func String(g Iterator) string {
 	n := g.Order()
 	// This may be a multigraph, so we look for duplicates by counting.

diff --git a/immutable.go b/immutable.go
@@ -118,12 +118,12 @@ func (g *Immutable) VisitFrom(v int, a int, do func(w int, c int64) bool) bool {
 	return false
 }
 
-// String returns a string representation of this graph.
+// String returns a string representation of the graph.
 func (g *Immutable) String() string {
 	return String(g)
 }
 
-// Order returns the number of vertices in this graph.
+// Order returns the number of vertices in the graph.
 func (g *Immutable) Order() int {
 	return len(g.edges)
 }
@@ -139,10 +139,7 @@ func (g *Immutable) Edge(v, w int) bool {
 	return i < n && w == edges[i].vertex
 }
 
-// Degree returns the number of neighbors of v.
+// Degree returns the number of outward directed edges from v.
 func (g *Immutable) Degree(v int) int {
-	if v < 0 || v >= g.Order() {
-		return 0
-	}
 	return len(g.edges[v])
 }
diff --git a/immutable_test.go b/immutable_test.go
@@ -178,12 +178,6 @@ func TestEdgeImm(t *testing.T) {
 func TestDegreeImm(t *testing.T) {
 	_, g1, g1c, g5, g5c := SetUpImm()
 
-	if mess, diff := diff(g1.Degree(-1), 0); diff {
-		t.Errorf("g1.Degree(0) %s", mess)
-	}
-	if mess, diff := diff(g1.Degree(1), 0); diff {
-		t.Errorf("g1.Degree(0) %s", mess)
-	}
 	if mess, diff := diff(g1.Degree(0), 1); diff {
 		t.Errorf("g1.Degree(0) %s", mess)
 	}

diff --git a/maxflow.go b/maxflow.go
@@ -2,8 +2,8 @@ package graph
 
 // MaxFlow computes a maximum flow from s to t in a graph
 // with nonnegative edge capacities.
-// The time complexity is O(|V|⋅|E|²), where |V| is the number of vertices
-// and |E| the number of edges in the graph.
+// The time complexity is O(|E|²⋅|V|), where |E| is the number of edges
+// and |V| the number of vertices in the graph.
 func MaxFlow(g Iterator, s, t int) (flow int64, graph Iterator) {
 	// Edmonds-Karp's algorithm
 	n := g.Order()

diff --git a/maxflow_test.go b/maxflow_test.go
@@ -1,6 +1,7 @@
 package graph
 
 import (
+	"math/rand"
 	"testing"
 )
 
@@ -67,3 +68,19 @@ func TestMaxFlow(t *testing.T) {
 		t.Errorf("MaxFlow(3, 1) %s", mess)
 	}
 }
+
+
+func BenchmarkMaxFlow(b *testing.B) {
+	n := 50
+	b.StopTimer()
+	g := New(n)
+	for i := 0; i < n; i++ {
+		for j := i; j < n; j++ {
+			g.AddCost(i, j, int64(rand.Int()))
+		}
+	}
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		_, _ = MaxFlow(g, 0, n-1)
+	}
+}