graph/internal/set: make complex set operations pure functions
MODIFY
graph/graphs/gen/batagelj_brandes_test.go
graph/graphs/gen/batagelj_brandes_test.go
@@ -293,8 +293,8 @@ func TestBipartitePowerLawUndirected(t *testing.T) {
for _, u := range p2 {
p2s.Add(u)
}
- o := set.NewNodes()
- if o.Intersect(p1s, p2s); len(o) != 0 {
+ o := set.IntersectionOfNodes(p1s, p2s)
+ if len(o) != 0 {
t.Errorf("unexpected overlap in partition membership: n=%d, d=%d: got:%d", n, d, len(o))
}
@@ -342,8 +342,8 @@ func TestBipartitePowerLawDirected(t *testing.T) {
for _, u := range p2 {
p2s.Add(u)
}
- o := set.NewNodes()
- if o.Intersect(p1s, p2s); len(o) != 0 {
+ o := set.IntersectionOfNodes(p1s, p2s)
+ if len(o) != 0 {
t.Errorf("unexpected overlap in partition membership: n=%d, d=%d: got:%d", n, d, len(o))
}

MODIFY
graph/internal/set/set.go
graph/internal/set/set.go
@@ -126,37 +126,23 @@ func (s Nodes) Remove(e graph.Node) {
delete(s, e.ID())
}
-// Has reports the existence of the element in the set.
+// Count returns the number of element in the set.
+func (s Nodes) Count() int {
+ return len(s)
+}
+
+// Has reports the existence of the elements in the set.
func (s Nodes) Has(n graph.Node) bool {
_, ok := s[n.ID()]
return ok
}
-// clear clears the set, possibly using the same backing store.
-func (s *Nodes) clear() {
- if len(*s) != 0 {
- *s = make(Nodes)
- }
-}
-
-// Copy performs a perfect copy from src to dst returning the result.
-// If len(dst) is not 0, a new Nodes is made and returned.
-func (dst Nodes) Copy(src Nodes) Nodes {
- // FIXME(kortschak): The behaviour is this method is very surprising.
- // Whether the return is required or not depends on len(dst).
-
- if same(src, dst) {
- return dst
- }
-
- if len(dst) != 0 {
- dst = make(Nodes, len(src))
- }
-
+// CloneNodes returns a clone of src.
+func CloneNodes(src Nodes) Nodes {
+ dst := make(Nodes, len(src))
for e, n := range src {
dst[e] = n
}
-
return dst
}
@@ -180,7 +166,7 @@ func Equal(a, b Nodes) bool {
return true
}
-// Union takes the union of a and b, and stores it in dst.
+// UnionOfNodes returns the union of a and b.
//
// The union of two sets, a and b, is the set containing all the
// elements of each, for instance:
@@ -192,31 +178,23 @@ func Equal(a, b Nodes) bool {
//
// {a,b,c} UNION {b,c,d} = {a,b,c,d}
//
-func (dst Nodes) Union(a, b Nodes) Nodes {
+func UnionOfNodes(a, b Nodes) Nodes {
if same(a, b) {
- return dst.Copy(a)
- }
-
- if !same(a, dst) && !same(b, dst) {
- dst.clear()
+ return CloneNodes(a)
}
- if !same(dst, a) {
+ dst := make(Nodes)
for e, n := range a {
dst[e] = n
}
- }
-
- if !same(dst, b) {
for e, n := range b {
dst[e] = n
}
- }
return dst
}
-// Intersect takes the intersection of a and b, and stores it in dst.
+// IntersectionOfNodes returns the intersection of a and b.
//
// The intersection of two sets, a and b, is the set containing all
// the elements shared between the two sets, for instance:
@@ -233,15 +211,11 @@ func (dst Nodes) Union(a, b Nodes) Nodes {
//
// {a,b,c} INTERSECT {d,e,f} = {}
//
-func (dst Nodes) Intersect(a, b Nodes) Nodes {
+func IntersectionOfNodes(a, b Nodes) Nodes {
if same(a, b) {
- return dst.Copy(a)
+ return CloneNodes(a)
}
-
- var swap Nodes
- switch {
- default:
- dst.clear()
+ dst := make(Nodes)
if len(a) > len(b) {
a, b = b, a
}
@@ -251,17 +225,4 @@ func (dst Nodes) Intersect(a, b Nodes) Nodes {
}
}
return dst
-
- case same(a, dst):
- swap = b
- case same(b, dst):
- swap = a
- }
- for e := range dst {
- if _, ok := swap[e]; !ok {
- delete(dst, e)
- }
- }
-
- return dst
}

MODIFY
graph/internal/set/set_test.go
graph/internal/set/set_test.go
@@ -329,7 +329,7 @@ func TestAddNodes(t *testing.T) {
t.Fatal("Set cannot be created successfully")
}
- if s.count() != 0 {
+ if s.Count() != 0 {
t.Error("Set somehow contains new elements upon creation")
}
@@ -337,7 +337,7 @@ func TestAddNodes(t *testing.T) {
s.Add(node(3))
s.Add(node(5))
- if s.count() != 3 {
+ if s.Count() != 3 {
t.Error("Incorrect number of set elements after adding")
}
@@ -347,9 +347,9 @@ func TestAddNodes(t *testing.T) {
s.Add(node(1))
- if s.count() > 3 {
+ if s.Count() > 3 {
t.Error("Set double-adds element (element not unique)")
- } else if s.count() < 3 {
+ } else if s.Count() < 3 {
t.Error("Set double-add lowered len")
}
@@ -377,7 +377,7 @@ func TestRemoveNodes(t *testing.T) {
s.Remove(node(1))
- if s.count() != 2 {
+ if s.Count() != 2 {
t.Error("Incorrect number of set elements after removing an element")
}
@@ -391,31 +391,17 @@ func TestRemoveNodes(t *testing.T) {
s.Remove(node(1))
- if s.count() != 2 || s.Has(node(1)) {
+ if s.Count() != 2 || s.Has(node(1)) {
t.Error("Double set remove does something strange")
}
s.Add(node(1))
- if s.count() != 3 || !s.Has(node(1)) {
+ if s.Count() != 3 || !s.Has(node(1)) {
t.Error("Cannot add element after removal")
}
}
-func TestClearNodes(t *testing.T) {
- s := NewNodes()
-
- s.Add(node(8))
- s.Add(node(9))
- s.Add(node(10))
-
- s.clear()
-
- if s.count() != 0 {
- t.Error("clear did not properly reset set to size 0")
- }
-}
-
func TestSelfEqualNodes(t *testing.T) {
s := NewNodes()
@@ -457,13 +443,12 @@ func TestEqualNodes(t *testing.T) {
func TestCopyNodes(t *testing.T) {
a := NewNodes()
- b := NewNodes()
a.Add(node(1))
a.Add(node(2))
a.Add(node(3))
- b.Copy(a)
+ b := CloneNodes(a)
if !Equal(a, b) {
t.Fatalf("Two sets not equal after copy: %v != %v", a, b)
@@ -474,31 +459,11 @@ func TestCopyNodes(t *testing.T) {
if Equal(a, b) {
t.Errorf("Mutating one set mutated another after copy: %v == %v", a, b)
}
-
- b = b.Copy(a) // Assignment is needed because b is not empty.
-
- if !Equal(a, b) {
- t.Fatalf("Two sets not equal after second copy: %v != %v", a, b)
- }
-}
-
-func TestSelfCopyNodes(t *testing.T) {
- a := NewNodes()
-
- a.Add(node(1))
- a.Add(node(2))
-
- a.Copy(a)
-
- if a.count() != 2 {
- t.Error("Something strange happened when copying into self")
- }
}
func TestUnionSameNodes(t *testing.T) {
a := NewNodes()
b := NewNodes()
- c := NewNodes()
a.Add(node(1))
a.Add(node(2))
@@ -506,9 +471,9 @@ func TestUnionSameNodes(t *testing.T) {
b.Add(node(1))
b.Add(node(2))
- c.Union(a, b)
+ c := UnionOfNodes(a, b)
- if c.count() != 2 {
+ if c.Count() != 2 {
t.Error("Union of same sets yields set with wrong len")
}
@@ -528,16 +493,15 @@ func TestUnionSameNodes(t *testing.T) {
func TestUnionDiffNodes(t *testing.T) {
a := NewNodes()
b := NewNodes()
- c := NewNodes()
a.Add(node(1))
a.Add(node(2))
b.Add(node(3))
- c.Union(a, b)
+ c := UnionOfNodes(a, b)
- if c.count() != 3 {
+ if c.Count() != 3 {
t.Error("Union of different sets yields set with wrong len")
}
@@ -545,11 +509,11 @@ func TestUnionDiffNodes(t *testing.T) {
t.Error("Union of different sets yields set with wrong elements")
}
- if a.Has(node(3)) || !a.Has(node(2)) || !a.Has(node(1)) || a.count() != 2 {
+ if a.Has(node(3)) || !a.Has(node(2)) || !a.Has(node(1)) || a.Count() != 2 {
t.Error("Union of sets mutates non-destination set (argument 1)")
}
- if !b.Has(node(3)) || b.Has(node(1)) || b.Has(node(2)) || b.count() != 1 {
+ if !b.Has(node(3)) || b.Has(node(1)) || b.Has(node(2)) || b.Count() != 1 {
t.Error("Union of sets mutates non-destination set (argument 2)")
}
@@ -561,7 +525,7 @@ func TestUnionDiffNodes(t *testing.T) {
}
}
- c = c.Union(a, a) // Assignment is necessary because c is not empty.
+ c = UnionOfNodes(a, a)
if !reflect.DeepEqual(c, a) {
t.Errorf("Union of equal sets not equal to sets: %v != %v", c, a)
}
@@ -570,7 +534,6 @@ func TestUnionDiffNodes(t *testing.T) {
func TestUnionOverlappingNodes(t *testing.T) {
a := NewNodes()
b := NewNodes()
- c := NewNodes()
a.Add(node(1))
a.Add(node(2))
@@ -578,9 +541,9 @@ func TestUnionOverlappingNodes(t *testing.T) {
b.Add(node(2))
b.Add(node(3))
- c.Union(a, b)
+ c := UnionOfNodes(a, b)
- if c.count() != 3 {
+ if c.Count() != 3 {
t.Error("Union of overlapping sets yields set with wrong len")
}
@@ -588,11 +551,11 @@ func TestUnionOverlappingNodes(t *testing.T) {
t.Error("Union of overlapping sets yields set with wrong elements")
}
- if a.Has(node(3)) || !a.Has(node(2)) || !a.Has(node(1)) || a.count() != 2 {
+ if a.Has(node(3)) || !a.Has(node(2)) || !a.Has(node(1)) || a.Count() != 2 {
t.Error("Union of sets mutates non-destination set (argument 1)")
}
- if !b.Has(node(3)) || b.Has(node(1)) || !b.Has(node(2)) || b.count() != 2 {
+ if !b.Has(node(3)) || b.Has(node(1)) || !b.Has(node(2)) || b.Count() != 2 {
t.Error("Union of sets mutates non-destination set (argument 2)")
}
@@ -604,7 +567,7 @@ func TestUnionOverlappingNodes(t *testing.T) {
}
}
- c = c.Intersect(a, a) // Assignment is necessary because c is not empty.
+ c = IntersectionOfNodes(a, a)
if !reflect.DeepEqual(c, a) {
t.Errorf("Intersection of equal sets not equal to sets: %v != %v", c, a)
}
@@ -613,7 +576,6 @@ func TestUnionOverlappingNodes(t *testing.T) {
func TestIntersectSameNodes(t *testing.T) {
a := NewNodes()
b := NewNodes()
- c := NewNodes()
a.Add(node(2))
a.Add(node(3))
@@ -621,9 +583,9 @@ func TestIntersectSameNodes(t *testing.T) {
b.Add(node(2))
b.Add(node(3))
- c.Intersect(a, b)
+ c := IntersectionOfNodes(a, b)
- if card := c.count(); card != 2 {
+ if card := c.Count(); card != 2 {
t.Errorf("Intersection of identical sets yields set of wrong len %d", card)
}
@@ -643,7 +605,6 @@ func TestIntersectSameNodes(t *testing.T) {
func TestIntersectDiffNodes(t *testing.T) {
a := NewNodes()
b := NewNodes()
- c := NewNodes()
a.Add(node(2))
a.Add(node(3))
@@ -651,17 +612,17 @@ func TestIntersectDiffNodes(t *testing.T) {
b.Add(node(1))
b.Add(node(4))
- c.Intersect(a, b)
+ c := IntersectionOfNodes(a, b)
- if card := c.count(); card != 0 {
+ if card := c.Count(); card != 0 {
t.Errorf("Intersection of different yields non-empty set %d", card)
}
- if !a.Has(node(2)) || !a.Has(node(3)) || a.Has(node(1)) || a.Has(node(4)) || a.count() != 2 {
+ if !a.Has(node(2)) || !a.Has(node(3)) || a.Has(node(1)) || a.Has(node(4)) || a.Count() != 2 {
t.Error("Intersection of sets mutates non-destination set (argument 1)")
}
- if b.Has(node(2)) || b.Has(node(3)) || !b.Has(node(1)) || !b.Has(node(4)) || b.count() != 2 {
+ if b.Has(node(2)) || b.Has(node(3)) || !b.Has(node(1)) || !b.Has(node(4)) || b.Count() != 2 {
t.Error("Intersection of sets mutates non-destination set (argument 1)")
}
@@ -677,7 +638,6 @@ func TestIntersectDiffNodes(t *testing.T) {
func TestIntersectOverlappingNodes(t *testing.T) {
a := NewNodes()
b := NewNodes()
- c := NewNodes()
a.Add(node(2))
a.Add(node(3))
@@ -685,9 +645,9 @@ func TestIntersectOverlappingNodes(t *testing.T) {
b.Add(node(3))
b.Add(node(4))
- c.Intersect(a, b)
+ c := IntersectionOfNodes(a, b)
- if card := c.count(); card != 1 {
+ if card := c.Count(); card != 1 {
t.Errorf("Intersection of overlapping sets yields set of incorrect len %d", card)
}
@@ -695,11 +655,11 @@ func TestIntersectOverlappingNodes(t *testing.T) {
t.Errorf("Intersection of overlapping sets yields set with wrong element")
}
- if !a.Has(node(2)) || !a.Has(node(3)) || a.Has(node(4)) || a.count() != 2 {
+ if !a.Has(node(2)) || !a.Has(node(3)) || a.Has(node(4)) || a.Count() != 2 {
t.Error("Intersection of sets mutates non-destination set (argument 1)")
}
- if b.Has(node(2)) || !b.Has(node(3)) || !b.Has(node(4)) || b.count() != 2 {
+ if b.Has(node(2)) || !b.Has(node(3)) || !b.Has(node(4)) || b.Count() != 2 {
t.Error("Intersection of sets mutates non-destination set (argument 1)")
}
@@ -711,12 +671,12 @@ func TestIntersectOverlappingNodes(t *testing.T) {
}
}
- c = c.Intersect(c, a) // Assignment is necessary because c is not empty.
+ c = IntersectionOfNodes(c, a)
want := Nodes{3: node(3)}
if !reflect.DeepEqual(c, want) {
t.Errorf("Intersection of sets with dst equal to a not equal: %v != %v", c, want)
}
- c = c.Intersect(a, c) // Assignment is necessary because c is not empty.
+ c = IntersectionOfNodes(a, c)
if !reflect.DeepEqual(c, want) {
t.Errorf("Intersection of sets with dst equal to a not equal: %v != %v", c, want)
}

MODIFY
graph/topo/bron_kerbosch.go
graph/topo/bron_kerbosch.go
@@ -152,7 +152,7 @@ func BronKerbosch(g graph.Undirected) [][]graph.Node {
for _, n := range neighbours {
nv.Add(n)
}
- bk.maximalCliquePivot(g, []graph.Node{v}, set.NewNodes().Intersect(p, nv), set.NewNodes().Intersect(x, nv))
+ bk.maximalCliquePivot(g, []graph.Node{v}, set.IntersectionOfNodes(p, nv), set.IntersectionOfNodes(x, nv))
p.Remove(v)
x.Add(v)
}
@@ -195,7 +195,7 @@ func (bk *bronKerbosch) maximalCliquePivot(g graph.Undirected, r []graph.Node, p
sr = append(r[:len(r):len(r)], v)
}
- bk.maximalCliquePivot(g, sr, set.NewNodes().Intersect(p, nv), set.NewNodes().Intersect(x, nv))
+ bk.maximalCliquePivot(g, sr, set.IntersectionOfNodes(p, nv), set.IntersectionOfNodes(x, nv))
p.Remove(v)
x.Add(v)
}

MODIFY
graph/topo/clique_graph.go
graph/topo/clique_graph.go
@@ -58,7 +58,7 @@ func CliqueGraph(dst Builder, g graph.Undirected) {
case len(vc.Clique.nodes):
edgeNodes = []graph.Node{vc.Clique.nodes[0]}
default:
- for _, n := range set.NewNodes().Intersect(uc.nodes, vc.nodes) {
+ for _, n := range set.IntersectionOfNodes(uc.nodes, vc.nodes) {
edgeNodes = append(edgeNodes, n)
}
sort.Sort(ordered.ByID(edgeNodes))

graph/internal/set: make complex set operations pure functions