yourbasic · korthaj · Apr 29, 2017 · Apr 29, 2017 · Apr 29, 2017 · Apr 29, 2017
diff --git a/README.md b/README.md
@@ -2,6 +2,10 @@
 
 Golang library of basic graph algorithms
 
+![Topological ordering](top.png)
+
+*Topological ordering, image by [David Eppstein][de], [CC0 1.0][cc010].*
+
 ### Generic graph algorithms
 
 The algorithms can be applied to any graph data structure implementing
@@ -42,7 +46,7 @@ functions that describe the edges of a graph.
 * The API of this library is frozen.
 * Bug fixes and performance enhancement can be expected.
 * New functionality might be included.
-* The version numbers adhere to [semantic versioning](http://semver.org/).
+* The 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.
@@ -52,3 +56,8 @@ algorithms and data structures, akin to the ones that you might find
 in a computer science textbook.
 
 Stefan Nilsson – [korthaj](https://github.com/korthaj)
+
+[cc010]: https://creativecommons.org/publicdomain/zero/1.0/deed.en
+[de]: https://commons.wikimedia.org/wiki/User:David_Eppstein
+[sv]: http://semver.org/
+
diff --git a/build/build.go b/build/build.go
@@ -249,7 +249,14 @@ func generic0(n int, edge func(v, w int) bool) *Virtual {
 // Generic returns a virtual graph with n vertices; its edge set consists of
 // all edges (v, w), v ≠ w, for which edge(v, w) returns true.
 func Generic(n int, edge FilterFunc) *Virtual {
-	if edge == nil {
+	switch {
+	case n < 0:
+		return nil
+	case n == 0:
+		return null
+	case n == 1:
+		return singleton()
+	case edge == nil:
 		return Kn(n)
 	}
 	return generic0(n, edge)
@@ -277,7 +284,9 @@ func Specific(g graph.Iterator) *Virtual {
 		return res
 	}
 	res.cost = func(v, w int) (cost int64) {
-		// Only called when w is a neighbor of v.
+		if !res.edge(v, w) {
+			return 0
+		}
 		h.VisitFrom(v, w, func(w int, c int64) (skip bool) {
 			cost = c
 			return true

diff --git a/build/build_test.go b/build/build_test.go
@@ -149,6 +149,9 @@ func TestEdge(t *testing.T) {
 }
 
 func TestLine(t *testing.T) {
+	if mess, diff := diff(line(-1), (*Virtual)(nil)); diff {
+		t.Errorf("line %s", mess)
+	}
 	if mess, diff := diff(line(0).String(), "0 []"); diff {
 		t.Errorf("line %s", mess)
 	}
@@ -167,7 +170,73 @@ func TestLine(t *testing.T) {
 }
 
 func TestGeneric(t *testing.T) {
-	g := Generic(0, func(v, w int) bool { return v != 0 })
+	g := generic0(-1, alwaysEdge)
+	if mess, diff := diff(g, (*Virtual)(nil)); diff {
+		t.Errorf("generic0 %s", mess)
+	}
+	Consistent("generic0", t, g)
+
+	g = generic0(0, alwaysEdge)
+	if mess, diff := diff(g.String(), "0 []"); diff {
+		t.Errorf("generic0 %s", mess)
+	}
+	Consistent("generic0", t, g)
+
+	g = generic0(1, alwaysEdge)
+	if mess, diff := diff(g.String(), "1 []"); diff {
+		t.Errorf("generic0 %s", mess)
+	}
+	Consistent("generic0", t, g)
+
+	g = generic(-1, zero, alwaysEdge)
+	if mess, diff := diff(g, (*Virtual)(nil)); diff {
+		t.Errorf("generic %s", mess)
+	}
+	Consistent("generic", t, g)
+
+	g = generic(0, zero, alwaysEdge)
+	if mess, diff := diff(g.String(), "0 []"); diff {
+		t.Errorf("generic %s", mess)
+	}
+	Consistent("generic", t, g)
+
+	g = generic(1, zero, alwaysEdge)
+	if mess, diff := diff(g.String(), "1 []"); diff {
+		t.Errorf("generic %s", mess)
+	}
+	Consistent("generic", t, g)
+
+	g = generic(2, zero, alwaysEdge)
+	if mess, diff := diff(g.String(), "2 [{0 1}]"); diff {
+		t.Errorf("generic %s", mess)
+	}
+	Consistent("generic", t, g)
+
+	g = Generic(-1, nil)
+	if mess, diff := diff(g, (*Virtual)(nil)); diff {
+		t.Errorf("Generic %s", mess)
+	}
+	Consistent("Generic", t, g)
+
+	g = Generic(0, nil)
+	if mess, diff := diff(g.String(), "0 []"); diff {
+		t.Errorf("Generic %s", mess)
+	}
+	Consistent("Generic", t, g)
+
+	g = Generic(1, nil)
+	if mess, diff := diff(g.String(), "1 []"); diff {
+		t.Errorf("Generic %s", mess)
+	}
+	Consistent("Generic", t, g)
+
+	g = Generic(2, nil)
+	if mess, diff := diff(g.String(), "2 [{0 1}]"); diff {
+		t.Errorf("Generic %s", mess)
+	}
+	Consistent("Generic", t, g)
+
+	g = Generic(0, func(v, w int) bool { return v != 0 })
 	if mess, diff := diff(g.String(), "0 []"); diff {
 		t.Errorf("Generic %s", mess)
 	}
@@ -205,9 +274,22 @@ func TestSpecific(t *testing.T) {
 		t.Errorf("Specific %s", mess)
 	}
 	Consistent("Specific", t, Specific(Kn(4)))
+
+	if mess, diff := diff(res.cost(0, 0), int64(0)); diff {
+		t.Errorf("Specific cost %s", mess)
+	}
+	if mess, diff := diff(res.cost(0, 1), int64(1)); diff {
+		t.Errorf("Specific cost %s", mess)
+	}
+	if mess, diff := diff(res.cost(1, 0), int64(10)); diff {
+		t.Errorf("Specific cost %s", mess)
+	}
 }
 
 func TestEmpty(t *testing.T) {
+	if mess, diff := diff(Empty(-1), (*Virtual)(nil)); diff {
+		t.Errorf("Empty %s", mess)
+	}
 	if mess, diff := diff(Empty(0).String(), "0 []"); diff {
 		t.Errorf("Empty %s", mess)
 	}
@@ -223,6 +305,9 @@ func TestEmpty(t *testing.T) {
 }
 
 func TestKn(t *testing.T) {
+	if mess, diff := diff(Kn(-1), (*Virtual)(nil)); diff {
+		t.Errorf("Kn %s", mess)
+	}
 	if mess, diff := diff(Kn(0).String(), "0 []"); diff {
 		t.Errorf("Kn %s", mess)
 	}
@@ -289,6 +374,12 @@ func TestKeep(t *testing.T) {
 		t.Errorf("Keep %s", mess)
 	}
 	Consistent("Keep", t, g)
+
+	g = Cycle(3).AddCost(1).Keep(nil)
+	if mess, diff := diff(g.String(), "3 [{0 1}:1 {0 2}:1 {1 2}:1]"); diff {
+		t.Errorf("Keep %s", mess)
+	}
+	Consistent("Keep", t, g)
 }
 
 func TestAddCost(t *testing.T) {
@@ -315,10 +406,58 @@ func TestAddCostFunc(t *testing.T) {
 	}
 	Consistent("AccCostFunc", t, res)
 
+	if mess, diff := diff(res.Cost(0, 0), int64(0)); diff {
+		t.Errorf("Cost %s", mess)
+	}
+	if mess, diff := diff(res.Cost(0, 1), int64(5)); diff {
+		t.Errorf("Cost %s", mess)
+	}
+	if mess, diff := diff(res.Cost(-1, 0), int64(0)); diff {
+		t.Errorf("Cost %s", mess)
+	}
+
+	res = Grid(1, 2).AddCostFunc(nil)
+	exp = "2 [{0 1}]"
+	if mess, diff := diff(res.String(), exp); diff {
+		t.Errorf("AddCostFunc %s", mess)
+	}
+	Consistent("AccCostFunc", t, res)
+
 	res = Empty(0).AddCostFunc(Cost(5))
 	exp = "0 []"
 	if mess, diff := diff(res.String(), exp); diff {
 		t.Errorf("AddCostFunc %s", mess)
 	}
 	Consistent("AddCostFunc", t, res)
 }
+
+func TestVisit(t *testing.T) {
+	g := Grid(1, 2).AddCost(5)
+	res := g.Visit(0, func(w int, c int64) (skip bool) {
+		return w == 1 && c == 5
+	})
+	if mess, diff := diff(res, true); diff {
+		t.Errorf("Visit %s", mess)
+	}
+
+	res = g.VisitFrom(0, 0, func(w int, c int64) (skip bool) {
+		return w == 1 && c == 5
+	})
+	if mess, diff := diff(res, true); diff {
+		t.Errorf("Visit %s", mess)
+	}
+
+	res = g.VisitFrom(0, -1, func(w int, c int64) (skip bool) {
+		return w == 1 && c == 5
+	})
+	if mess, diff := diff(res, true); diff {
+		t.Errorf("Visit %s", mess)
+	}
+
+	res = g.VisitFrom(0, 2, func(w int, c int64) (skip bool) {
+		return w == 1 && c == 5
+	})
+	if mess, diff := diff(res, false); diff {
+		t.Errorf("Visit %s", mess)
+	}
+}
diff --git a/build/cartesian.go b/build/cartesian.go
@@ -13,8 +13,6 @@ import "strconv"
 func (g1 *Virtual) Cartesian(g2 *Virtual) *Virtual {
 	m, n := g1.Order(), g2.Order()
 	switch {
-	case m < 0 || n < 0:
-		return nil
 	case m == 0 || n == 0:
 		return null
 	case m*n/m != n:

diff --git a/build/circulant_test.go b/build/circulant_test.go
@@ -12,6 +12,18 @@ func TestCirculant(t *testing.T) {
 	}
 	Consistent("Circulant", t, res)
 
+	res = Circulant(-1)
+	if mess, diff := diff(res, (*Virtual)(nil)); diff {
+		t.Errorf("Circulant %s", mess)
+	}
+	Consistent("Circulant", t, res)
+
+	res = Circulant(0)
+	if mess, diff := diff(res.String(), "0 []"); diff {
+		t.Errorf("Circulant %s", mess)
+	}
+	Consistent("Circulant", t, res)
+
 	res = Circulant(1)
 	if mess, diff := diff(res.String(), "1 []"); diff {
 		t.Errorf("Circulant %s", mess)

diff --git a/build/cycle_test.go b/build/cycle_test.go
@@ -3,6 +3,10 @@ package build
 import "testing"
 
 func TestCycle(t *testing.T) {
+	if mess, diff := diff(Cycle(-1), (*Virtual)(nil)); diff {
+		t.Errorf("Cycle %s", mess)
+	}
+
 	if mess, diff := diff(Cycle(0).String(), "0 []"); diff {
 		t.Errorf("Cycle %s", mess)
 	}

diff --git a/build/join_test.go b/build/join_test.go
@@ -18,6 +18,13 @@ func TestJoin(t *testing.T) {
 	}
 	Consistent("Join", t, res)
 
+	res = Empty(0).Join(g, b)
+	exp = "4 [{0 1} {0 2} {1 3} {2 3}]"
+	if mess, diff := diff(res.String(), exp); diff {
+		t.Errorf("Join %s", mess)
+	}
+	Consistent("Join", t, res)
+
 	b = EdgeSet{
 		From: Vertex(1),
 		To:   Vertex(3),

diff --git a/build/subgraph_test.go b/build/subgraph_test.go
@@ -12,26 +12,33 @@ func TestSubgraph(t *testing.T) {
 	}
 	Consistent("Subgraph1", t, res)
 
+	res = Kn(2).Subgraph(Range(-1, 10))
+	exp = "2 [{0 1}]"
+	if mess, diff := diff(res.String(), exp); diff {
+		t.Errorf("Subgraph %s", mess)
+	}
+	Consistent("Subgraph2", t, res)
+
 	res = Kn(6).AddCostFunc(cost).Subgraph(Range(3, 6))
 	exp = "3 [(0 1):34 (0 2):35 (1 0):43 (1 2):45 (2 0):53 (2 1):54]"
 	if mess, diff := diff(res.String(), exp); diff {
 		t.Errorf("Subgraph %s", mess)
 	}
-	Consistent("Subgraph2", t, res)
+	Consistent("Subgraph3", t, res)
 
 	res = Kn(6).AddCostFunc(cost).Subgraph(Vertex(1).Or(Vertex(3)))
 	exp = "2 [(0 1):13 (1 0):31]"
 	if mess, diff := diff(res.String(), exp); diff {
 		t.Errorf("Subgraph %s", mess)
 	}
-	Consistent("Subgraph3", t, res)
+	Consistent("Subgraph4", t, res)
 
 	res = Grid(3, 3).Subgraph(Range(0, 4).Or(Range(5, 9)))
 	exp = "8 [{0 1} {0 3} {1 2} {2 4} {3 5} {4 7} {5 6} {6 7}]"
 	if mess, diff := diff(res.String(), exp); diff {
 		t.Errorf("Subgraph %s", mess)
 	}
-	Consistent("Subgraph4", t, res)
+	Consistent("Subgraph5", t, res)
 
 	for m := 0; m < 6; m++ {
 		for n := 0; n < 6; n++ {