graph: rename nodeFilterIterator => nodeIteratorPair and minor fixes
The length calculation is now correct. This had not effect previously as
NodesOf is lenient in how it handles mis-estimated iterator lengths.
MODIFY
graph/undirect.go
graph/undirect.go
@@ -20,7 +20,10 @@ func (g Undirect) Nodes() Nodes { return g.G.Nodes() }
// From returns all nodes in g that can be reached directly from u.
func (g Undirect) From(uid int64) Nodes {
- return newNodeFilterIterator(g.G.From(uid), g.G.To(uid))
+ if g.G.Node(uid) == nil {
+ return Empty
+ }
+ return newNodeIteratorPair(g.G.From(uid), g.G.To(uid))
}
// HasEdgeBetween returns whether an edge exists between nodes x and y.
@@ -86,7 +89,10 @@ func (g UndirectWeighted) Nodes() Nodes { return g.G.Nodes() }
// From returns all nodes in g that can be reached directly from u.
func (g UndirectWeighted) From(uid int64) Nodes {
- return newNodeFilterIterator(g.G.From(uid), g.G.To(uid))
+ if g.G.Node(uid) == nil {
+ return Empty
+ }
+ return newNodeIteratorPair(g.G.From(uid), g.G.To(uid))
}
// HasEdgeBetween returns whether an edge exists between nodes x and y.
@@ -218,53 +224,61 @@ func (e WeightedEdgePair) ReversedEdge() Edge {
// Weight returns the merged edge weights of the two edges.
func (e WeightedEdgePair) Weight() float64 { return e.W }
-// nodeFilterIterator combines two Nodes to produce a single stream of
+// nodeIteratorPair combines two Nodes to produce a single stream of
// unique nodes.
-type nodeFilterIterator struct {
+type nodeIteratorPair struct {
a, b Nodes
+ curr, cnt int
+
// unique indicates the node in b with the key ID is unique.
unique map[int64]bool
}
-func newNodeFilterIterator(a, b Nodes) *nodeFilterIterator {
- n := nodeFilterIterator{a: a, b: b, unique: make(map[int64]bool)}
+func newNodeIteratorPair(a, b Nodes) *nodeIteratorPair {
+ n := nodeIteratorPair{a: a, b: b, unique: make(map[int64]bool)}
for n.b.Next() {
n.unique[n.b.Node().ID()] = true
+ n.cnt++
}
n.b.Reset()
for n.a.Next() {
+ if _, ok := n.unique[n.a.Node().ID()]; !ok {
+ n.cnt++
+ }
n.unique[n.a.Node().ID()] = false
}
n.a.Reset()
return &n
}
-func (n *nodeFilterIterator) Len() int {
- return len(n.unique)
+func (n *nodeIteratorPair) Len() int {
+ return n.cnt - n.curr
}
-func (n *nodeFilterIterator) Next() bool {
- n.Len()
+func (n *nodeIteratorPair) Next() bool {
if n.a.Next() {
+ n.curr++
return true
}
for n.b.Next() {
if n.unique[n.b.Node().ID()] {
+ n.curr++
return true
}
}
return false
}
-func (n *nodeFilterIterator) Node() Node {
+func (n *nodeIteratorPair) Node() Node {
if n.a.Len() != 0 {
return n.a.Node()
}
return n.b.Node()
}
-func (n *nodeFilterIterator) Reset() {
+func (n *nodeIteratorPair) Reset() {
+ n.curr = 0
n.a.Reset()
n.b.Reset()
}

MODIFY
graph/undirect_test.go
graph/undirect_test.go
@@ -9,6 +9,7 @@ import (
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/iterator"
"gonum.org/v1/gonum/graph/simple"
"gonum.org/v1/gonum/mat"
)
@@ -175,3 +176,36 @@ func (m unit) At(i, j int) float64 {
}
return 1
}
+
+var nodeIteratorPairTests = []struct {
+ a, b graph.Nodes
+ len int
+}{
+ {a: graph.Empty, b: graph.Empty, len: 0},
+ {a: iterator.NewOrderedNodes(nil), b: iterator.NewOrderedNodes(nil), len: 0},
+ {a: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), b: graph.Empty, len: 1},
+ {a: graph.Empty, b: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), len: 1},
+ {a: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), b: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), len: 1},
+ {a: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), b: iterator.NewOrderedNodes([]graph.Node{simple.Node(1)}), len: 2},
+ {a: iterator.NewOrderedNodes([]graph.Node{simple.Node(0), simple.Node(1)}), b: iterator.NewOrderedNodes([]graph.Node{simple.Node(1)}), len: 2},
+ {a: iterator.NewOrderedNodes([]graph.Node{simple.Node(1)}), b: iterator.NewOrderedNodes([]graph.Node{simple.Node(0), simple.Node(1)}), len: 2},
+}
+
+func TestNodeIteratorPair(t *testing.T) {
+ for _, test := range nodeIteratorPairTests {
+ it := graph.NewNodeIteratorPair(test.a, test.b)
+ for i := 0; i < 2; i++ {
+ n := it.Len()
+ if n != test.len {
+ t.Errorf("unexpected length of iterator construction/reset: got:%d want:%d", n, test.len)
+ }
+ for it.Next() {
+ n--
+ }
+ if n != 0 {
+ t.Errorf("unexpected remaining nodes after iterator completion: got:%d want:0", n)
+ }
+ it.Reset()
+ }
+ }
+}

graph: rename nodeFilterIterator => nodeIteratorPair and minor fixes

The length calculation is now correct. This had not effect previously as
NodesOf is lenient in how it handles mis-estimated iterator lengths.