graph/graphs/gen: check for all node id collisions
This incurs a greater cost for well-behaved code, but prevents subtle
errors that would otherwise not be caught, for example cycle(1,2,3,4,5,3)
not being a single cycle.
MODIFY
graph/graphs/gen/gen.go
graph/graphs/gen/gen.go
@@ -54,13 +54,17 @@ func (s IDSet) Len() int { return len(s) }
func (s IDSet) ID(i int) int64 { return s[i] }
// Complete constructs a complete graph in dst using nodes with the given IDs.
-func Complete(dst NodeIDGraphBuilder, ids IDer) error {
- if ids.Len() == 1 {
+// If any ID appears twice in ids, Complete will panic.
+func Complete(dst NodeIDGraphBuilder, ids IDer) {
+ switch ids.Len() {
+ case 0:
+ return
+ case 1:
u, new := dst.NodeWithID(ids.ID(0))
if new {
dst.AddNode(u)
}
- return nil
+ return
}
for i := 0; i < ids.Len(); i++ {
uid := ids.ID(i)
@@ -68,92 +72,132 @@ func Complete(dst NodeIDGraphBuilder, ids IDer) error {
for j := i + 1; j < ids.Len(); j++ {
vid := ids.ID(j)
if uid == vid {
- return fmt.Errorf("gen: node ID collision i=%d j=%d: %d", i, j, uid)
+ panic(fmt.Errorf("gen: node ID collision i=%d j=%d: id=%d", i, j, uid))
}
v, _ := dst.NodeWithID(vid)
dst.SetEdge(dst.NewEdge(u, v))
}
}
- return nil
}
// Cycle constructs a cycle in dst using the node IDs in cycle.
// If dst is a directed graph, edges are directed from earlier nodes to later
-// nodes in cycle.
-func Cycle(dst NodeIDGraphBuilder, cycle IDer) error {
- if cycle.Len() == 1 {
+// nodes in cycle. If any ID appears twice in cycle, Cycle will panic.
+func Cycle(dst NodeIDGraphBuilder, cycle IDer) {
+ switch cycle.Len() {
+ case 0:
+ return
+ case 1:
u, new := dst.NodeWithID(cycle.ID(0))
if new {
dst.AddNode(u)
}
- return nil
+ return
+ }
+ err := check(cycle)
+ if err != nil {
+ panic(err)
+ }
+ cycleNoCheck(dst, cycle)
}
+
+func cycleNoCheck(dst NodeIDGraphBuilder, cycle IDer) {
for i := 0; i < cycle.Len(); i++ {
uid := cycle.ID(i)
vid := cycle.ID((i + 1) % cycle.Len())
- if uid == vid {
- return fmt.Errorf("gen: adjacent node IDs equal at %d: %d", i, uid)
- }
u, _ := dst.NodeWithID(uid)
v, _ := dst.NodeWithID(vid)
dst.SetEdge(dst.NewEdge(u, v))
}
- return nil
}
// Path constructs a path graph in dst with
// If dst is a directed graph, edges are directed from earlier nodes to later
-// nodes in path.
-func Path(dst NodeIDGraphBuilder, path IDer) error {
- if path.Len() == 1 {
+// nodes in path. If any ID appears twice in path, Path will panic.
+func Path(dst NodeIDGraphBuilder, path IDer) {
+ switch path.Len() {
+ case 0:
+ return
+ case 1:
u, new := dst.NodeWithID(path.ID(0))
if new {
dst.AddNode(u)
}
- return nil
+ return
+ }
+ err := check(path)
+ if err != nil {
+ panic(err)
}
for i := 0; i < path.Len()-1; i++ {
uid := path.ID(i)
vid := path.ID(i + 1)
- if uid == vid {
- return fmt.Errorf("gen: adjacent node IDs equal at %d: %d", i, uid)
- }
u, _ := dst.NodeWithID(uid)
v, _ := dst.NodeWithID(vid)
dst.SetEdge(dst.NewEdge(u, v))
}
- return nil
}
// Star constructs a star graph in dst with edges between the center node ID to
// node with IDs specified in leaves.
// If dst is a directed graph, edges are directed from the center node to the
-// leaves.
-func Star(dst NodeIDGraphBuilder, center int64, leaves IDer) error {
+// leaves. If any ID appears twice in leaves and center, Star will panic.
+func Star(dst NodeIDGraphBuilder, center int64, leaves IDer) {
c, new := dst.NodeWithID(center)
if new {
dst.AddNode(c)
}
+ if leaves.Len() == 0 {
+ return
+ }
+ err := check(leaves, center)
+ if err != nil {
+ panic(err)
+ }
for i := 0; i < leaves.Len(); i++ {
id := leaves.ID(i)
- if id == center {
- return fmt.Errorf("gen: leaf %d ID matches central node ID: %d", i, center)
- }
n, _ := dst.NodeWithID(id)
dst.SetEdge(dst.NewEdge(c, n))
}
- return nil
}
// Wheel constructs a wheel graph in dst with edges from the center
// node ID to node with IDs specified in cycle and between nodes with IDs
// adjacent in the cycle.
// If dst is a directed graph, edges are directed from the center node to the
-// cycle and from earlier nodes to later nodes in cycle.
-func Wheel(dst NodeIDGraphBuilder, center int64, cycle IDer) error {
- err := Star(dst, center, cycle)
- if err != nil {
- return err
+// cycle and from earlier nodes to later nodes in cycle. If any ID appears
+// twice in cycle and center, Wheel will panic.
+func Wheel(dst NodeIDGraphBuilder, center int64, cycle IDer) {
+ Star(dst, center, cycle)
+ if cycle.Len() <= 1 {
+ return
}
- return Cycle(dst, cycle)
+ cycleNoCheck(dst, cycle)
+}
+
+// check confirms that no node ID exists more than once in ids and extra.
+func check(ids IDer, extra ...int64) error {
+ seen := make(map[int64]int, ids.Len()+len(extra))
+ for j := 0; j < ids.Len(); j++ {
+ uid := ids.ID(j)
+ if prev, exists := seen[uid]; exists {
+ return fmt.Errorf("gen: node ID collision i=%d j=%d: id=%d", prev, j, uid)
+ }
+ seen[uid] = j
+ }
+ lenIDs := ids.Len()
+ for j, uid := range extra {
+ if prev, exists := seen[uid]; exists {
+ if prev < lenIDs {
+ if len(extra) == 1 {
+ return fmt.Errorf("gen: node ID collision i=%d with extra: id=%d", prev, uid)
+ }
+ return fmt.Errorf("gen: node ID collision i=%d with extra j=%d: id=%d", prev, j, uid)
+ }
+ prev -= lenIDs
+ return fmt.Errorf("gen: extra node ID collision i=%d j=%d: id=%d", prev, j, uid)
+ }
+ seen[uid] = j + lenIDs
+ }
+ return nil
}

MODIFY
graph/graphs/gen/gen_example_test.go
graph/graphs/gen/gen_example_test.go
@@ -16,10 +16,7 @@ import (
func ExampleStar_undirectedRange() {
dst := simple.NewUndirectedGraph()
- err := gen.Star(dst, 0, gen.IDRange{First: 1, Last: 6})
- if err != nil {
- log.Fatal(err)
- }
+ gen.Star(dst, 0, gen.IDRange{First: 1, Last: 6})
b, err := dot.Marshal(dst, "star", "", "\t")
if err != nil {
log.Fatal(err)
@@ -49,10 +46,7 @@ func ExampleStar_undirectedRange() {
func ExampleWheel_directedRange() {
dst := simple.NewDirectedGraph()
- err := gen.Wheel(dst, 0, gen.IDRange{First: 1, Last: 6})
- if err != nil {
- log.Fatal(err)
- }
+ gen.Wheel(dst, 0, gen.IDRange{First: 1, Last: 6})
b, err := dot.Marshal(dst, "wheel", "", "\t")
if err != nil {
log.Fatal(err)
@@ -88,10 +82,7 @@ func ExampleWheel_directedRange() {
func ExamplePath_directedSet() {
dst := simple.NewDirectedGraph()
- err := gen.Path(dst, gen.IDSet{2, 4, 5, 9})
- if err != nil {
- log.Fatal(err)
- }
+ gen.Path(dst, gen.IDSet{2, 4, 5, 9})
b, err := dot.Marshal(dst, "path", "", "\t")
if err != nil {
log.Fatal(err)
@@ -115,10 +106,7 @@ func ExamplePath_directedSet() {
func ExampleComplete_directedSet() {
dst := simple.NewDirectedGraph()
- err := gen.Complete(dst, gen.IDSet{2, 4, 5, 9})
- if err != nil {
- log.Fatal(err)
- }
+ gen.Complete(dst, gen.IDSet{2, 4, 5, 9})
b, err := dot.Marshal(dst, "complete", "", "\t")
if err != nil {
log.Fatal(err)
@@ -155,10 +143,7 @@ func (g Bidirected) SetEdge(e graph.Edge) {
func ExampleComplete_biDirectedSet() {
dst := simple.NewDirectedGraph()
- err := gen.Complete(Bidirected{dst}, gen.IDSet{2, 4, 5, 9})
- if err != nil {
- log.Fatal(err)
- }
+ gen.Complete(Bidirected{dst}, gen.IDSet{2, 4, 5, 9})
b, err := dot.Marshal(dst, "complete", "", "\t")
if err != nil {
log.Fatal(err)
@@ -191,10 +176,7 @@ func ExampleComplete_biDirectedSet() {
func ExampleComplete_undirectedSet() {
dst := simple.NewUndirectedGraph()
- err := gen.Complete(dst, gen.IDSet{2, 4, 5, 9})
- if err != nil {
- log.Fatal(err)
- }
+ gen.Complete(dst, gen.IDSet{2, 4, 5, 9})
b, err := dot.Marshal(dst, "complete", "", "\t")
if err != nil {
log.Fatal(err)

MODIFY
graph/graphs/gen/gen_test.go
graph/graphs/gen/gen_test.go
@@ -6,6 +6,7 @@ package gen
import (
"bytes"
+ "fmt"
"testing"
"gonum.org/v1/gonum/graph"
@@ -26,12 +27,25 @@ type empty struct{}
func (r empty) Len() int { return 0 }
func (r empty) ID(i int) int64 { panic("called ID on empty IDer") }
+func panics(fn func()) (panicked bool, msg string) {
+ defer func() {
+ r := recover()
+ if r != nil {
+ panicked = true
+ msg = fmt.Sprint(r)
+ }
+ }()
+ fn()
+ return
+}
+
func TestComplete(t *testing.T) {
tests := []struct {
name string
ids IDer
dst func() nodeIDGraphBuilder
want string
+ panics string
}{
{
name: "empty",
@@ -115,13 +129,22 @@ func TestComplete(t *testing.T) {
3 -> 4;
}`,
},
+ {
+ name: "collision",
+ ids: IDSet{1, 2, 3, 2},
+ dst: undirected,
+ panics: "gen: node ID collision i=1 j=3: id=2",
+ },
}
for _, test := range tests {
dst := test.dst()
- err := Complete(dst, test.ids)
- if err != nil {
- t.Errorf("unexpected error constructing graph: %v", err)
+ panicked, msg := panics(func() { Complete(dst, test.ids) })
+ if msg != test.panics {
+ t.Errorf("unexpected panic message for %q: got:%q want:%q", test.name, msg, test.panics)
+ }
+ if panicked {
+ continue
}
got, err := dot.Marshal(dst, test.name, "", " ")
if err != nil {
@@ -139,6 +162,7 @@ func TestCycle(t *testing.T) {
ids IDer
dst func() nodeIDGraphBuilder
want string
+ panics string
}{
{
name: "empty",
@@ -219,13 +243,22 @@ func TestCycle(t *testing.T) {
4 -> 1;
}`,
},
+ {
+ name: "collision",
+ ids: IDSet{1, 2, 3, 2},
+ dst: undirected,
+ panics: "gen: node ID collision i=1 j=3: id=2",
+ },
}
for _, test := range tests {
dst := test.dst()
- err := Cycle(dst, test.ids)
- if err != nil {
- t.Errorf("unexpected error constructing graph: %v", err)
+ panicked, msg := panics(func() { Cycle(dst, test.ids) })
+ if msg != test.panics {
+ t.Errorf("unexpected panic message for %q: got:%q want:%q", test.name, msg, test.panics)
+ }
+ if panicked {
+ continue
}
got, err := dot.Marshal(dst, test.name, "", " ")
if err != nil {
@@ -243,6 +276,7 @@ func TestPath(t *testing.T) {
ids IDer
dst func() nodeIDGraphBuilder
want string
+ panics string
}{
{
name: "empty",
@@ -320,13 +354,22 @@ func TestPath(t *testing.T) {
3 -> 4;
}`,
},
+ {
+ name: "collision",
+ ids: IDSet{1, 2, 3, 2},
+ dst: undirected,
+ panics: "gen: node ID collision i=1 j=3: id=2",
+ },
}
for _, test := range tests {
dst := test.dst()
- err := Path(dst, test.ids)
- if err != nil {
- t.Errorf("unexpected error constructing graph: %v", err)
+ panicked, msg := panics(func() { Path(dst, test.ids) })
+ if msg != test.panics {
+ t.Errorf("unexpected panic message for %q: got:%q want:%q", test.name, msg, test.panics)
+ }
+ if panicked {
+ continue
}
got, err := dot.Marshal(dst, test.name, "", " ")
if err != nil {
@@ -345,6 +388,7 @@ func TestStar(t *testing.T) {
leaves IDer
dst func() nodeIDGraphBuilder
want string
+ panics string
}{
{
name: "empty_leaves",
@@ -358,6 +402,7 @@ func TestStar(t *testing.T) {
},
{
name: "single",
+ center: 0,
leaves: IDRange{First: 1, Last: 1},
dst: undirected,
want: `strict graph single {
@@ -371,6 +416,7 @@ func TestStar(t *testing.T) {
},
{
name: "pair_undirected",
+ center: 0,
leaves: IDRange{First: 1, Last: 2},
dst: undirected,
want: `strict graph pair_undirected {
@@ -386,6 +432,7 @@ func TestStar(t *testing.T) {
},
{
name: "pair_directed",
+ center: 0,
leaves: IDRange{First: 1, Last: 2},
dst: directed,
want: `strict digraph pair_directed {
@@ -401,6 +448,7 @@ func TestStar(t *testing.T) {
},
{
name: "quad_undirected",
+ center: 0,
leaves: IDRange{First: 1, Last: 4},
dst: undirected,
want: `strict graph quad_undirected {
@@ -420,6 +468,7 @@ func TestStar(t *testing.T) {
},
{
name: "quad_directed",
+ center: 0,
leaves: IDRange{First: 1, Last: 4},
dst: directed,
want: `strict digraph quad_directed {
@@ -437,13 +486,30 @@ func TestStar(t *testing.T) {
0 -> 4;
}`,
},
+ {
+ name: "center collision",
+ center: 1,
+ leaves: IDRange{First: 1, Last: 4},
+ dst: undirected,
+ panics: "gen: node ID collision i=0 with extra: id=1",
+ },
+ {
+ name: "leaf collision",
+ center: 0,
+ leaves: IDSet{1, 2, 3, 2},
+ dst: undirected,
+ panics: "gen: node ID collision i=1 j=3: id=2",
+ },
}
for _, test := range tests {
dst := test.dst()
- err := Star(dst, test.center, test.leaves)
- if err != nil {
- t.Errorf("unexpected error constructing graph: %v", err)
+ panicked, msg := panics(func() { Star(dst, test.center, test.leaves) })
+ if msg != test.panics {
+ t.Errorf("unexpected panic message for %q: got:%q want:%q", test.name, msg, test.panics)
+ }
+ if panicked {
+ continue
}
got, err := dot.Marshal(dst, test.name, "", " ")
if err != nil {
@@ -462,6 +528,7 @@ func TestWheel(t *testing.T) {
cycle IDer
dst func() nodeIDGraphBuilder
want string
+ panics string
}{
{
name: "empty_cycle",
@@ -488,6 +555,7 @@ func TestWheel(t *testing.T) {
},
{
name: "pair_undirected",
+ center: 0,
cycle: IDRange{First: 1, Last: 2},
dst: undirected,
want: `strict graph pair_undirected {
@@ -504,6 +572,7 @@ func TestWheel(t *testing.T) {
},
{
name: "pair_directed",
+ center: 0,
cycle: IDRange{First: 1, Last: 2},
dst: directed,
want: `strict digraph pair_directed {
@@ -521,6 +590,7 @@ func TestWheel(t *testing.T) {
},
{
name: "quad_undirected",
+ center: 0,
cycle: IDRange{First: 1, Last: 4},
dst: undirected,
want: `strict graph quad_undirected {
@@ -544,6 +614,7 @@ func TestWheel(t *testing.T) {
},
{
name: "quad_directed",
+ center: 0,
cycle: IDRange{First: 1, Last: 4},
dst: directed,
want: `strict digraph quad_directed {
@@ -565,13 +636,30 @@ func TestWheel(t *testing.T) {
4 -> 1;
}`,
},
+ {
+ name: "center collision",
+ center: 1,
+ cycle: IDRange{First: 1, Last: 4},
+ dst: undirected,
+ panics: "gen: node ID collision i=0 with extra: id=1",
+ },
+ {
+ name: "cycle collision",
+ center: 0,
+ cycle: IDSet{1, 2, 3, 2},
+ dst: undirected,
+ panics: "gen: node ID collision i=1 j=3: id=2",
+ },
}
for _, test := range tests {
dst := test.dst()
- err := Wheel(dst, test.center, test.cycle)
- if err != nil {
- t.Errorf("unexpected error constructing graph: %v", err)
+ panicked, msg := panics(func() { Wheel(dst, test.center, test.cycle) })
+ if msg != test.panics {
+ t.Errorf("unexpected panic message for %q: got:%q want:%q", test.name, msg, test.panics)
+ }
+ if panicked {
+ continue
}
got, err := dot.Marshal(dst, test.name, "", " ")
if err != nil {
@@ -582,3 +670,32 @@ func TestWheel(t *testing.T) {
}
}
}
+
+func TestCheck(t *testing.T) {
+ tests := []struct {
+ ids IDer
+ extra []int64
+ want string
+ }{
+ {
+ ids: IDSet{1, 2, 3, 4}, extra: []int64{1},
+ want: "gen: node ID collision i=0 with extra: id=1",
+ },
+ {
+ ids: IDSet{1, 2, 3, 4}, extra: []int64{5, 2},
+ want: "gen: node ID collision i=1 with extra j=1: id=2",
+ },
+ {
+ ids: IDSet{}, extra: []int64{1, 2, 1},
+ want: "gen: extra node ID collision i=0 j=2: id=1",
+ },
+ }
+
+ for _, test := range tests {
+ msg := fmt.Sprint(check(test.ids, test.extra...))
+ if msg != test.want {
+ t.Errorf("unexpected check panic for ids=%#v extra=%v: got:%q want:%q",
+ test.ids, test.extra, msg, test.want)
+ }
+ }
+}

graph/graphs/gen: check for all node id collisions

This incurs a greater cost for well-behaved code, but prevents subtle
errors that would otherwise not be caught, for example cycle(1,2,3,4,5,3)
not being a single cycle.