graph/simple: factor id handling out of graphs
MODIFY
graph/simple/directed.go
graph/simple/directed.go
@@ -7,8 +7,6 @@ package simple
import (
"fmt"
- "golang.org/x/tools/container/intsets"
-
"gonum.org/v1/gonum/graph"
)
@@ -20,8 +18,7 @@ type DirectedGraph struct {
self, absent float64
- freeIDs intsets.Sparse
- usedIDs intsets.Sparse
+ nodeIDs idSet
}
// NewDirectedGraph returns a DirectedGraph with the specified self and absent
@@ -44,22 +41,9 @@ func (g *DirectedGraph) NewNodeID() int {
return 0
}
if len(g.nodes) == maxInt {
- panic(fmt.Sprintf("simple: cannot allocate node: no slot"))
- }
-
- var id int
- if g.freeIDs.Len() != 0 && g.freeIDs.TakeMin(&id) {
- return id
- }
- if id = g.usedIDs.Max(); id < maxInt {
- return id + 1
+ panic("simple: cannot allocate node: no slot")
}
- for id = 0; id < maxInt; id++ {
- if !g.usedIDs.Has(id) {
- return id
- }
- }
- panic("unreachable")
+ return g.nodeIDs.newID()
}
// AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.
@@ -70,9 +54,7 @@ func (g *DirectedGraph) AddNode(n graph.Node) {
g.nodes[n.ID()] = n
g.from[n.ID()] = make(map[int]graph.Edge)
g.to[n.ID()] = make(map[int]graph.Edge)
-
- g.freeIDs.Remove(n.ID())
- g.usedIDs.Insert(n.ID())
+ g.nodeIDs.use(n.ID())
}
// RemoveNode removes n from the graph, as well as any edges attached to it. If the node
@@ -93,8 +75,7 @@ func (g *DirectedGraph) RemoveNode(n graph.Node) {
}
delete(g.to, n.ID())
- g.freeIDs.Insert(n.ID())
- g.usedIDs.Remove(n.ID())
+ g.nodeIDs.release(n.ID())
}
// SetEdge adds e, an edge from one node to another. If the nodes do not exist, they are added.

MODIFY
graph/simple/simple.go
graph/simple/simple.go
@@ -9,6 +9,8 @@ package simple // import "gonum.org/v1/gonum/graph/simple"
import (
"math"
+ "golang.org/x/tools/container/intsets"
+
"gonum.org/v1/gonum/graph"
)
@@ -43,3 +45,37 @@ const maxInt int = int(^uint(0) >> 1)
func isSame(a, b float64) bool {
return a == b || (math.IsNaN(a) && math.IsNaN(b))
}
+
+// idSet implements available ID storage.
+type idSet struct {
+ used, free intsets.Sparse
+}
+
+// newID returns a new unique ID.
+func (s *idSet) newID() int {
+ var id int
+ if s.free.TakeMin(&id) {
+ return id
+ }
+ if id = s.used.Max(); id < maxInt {
+ return id + 1
+ }
+ for id = 0; id < maxInt; id++ {
+ if !s.used.Has(id) {
+ return id
+ }
+ }
+ panic("unreachable")
+}
+
+// use adds the id to the used IDs in the idSet.
+func (s *idSet) use(id int) {
+ s.free.Remove(id)
+ s.used.Insert(id)
+}
+
+// free frees the id for reuse.
+func (s *idSet) release(id int) {
+ s.free.Insert(id)
+ s.used.Remove(id)
+}

MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -7,8 +7,6 @@ package simple
import (
"fmt"
- "golang.org/x/tools/container/intsets"
-
"gonum.org/v1/gonum/graph"
)
@@ -19,8 +17,7 @@ type UndirectedGraph struct {
self, absent float64
- freeIDs intsets.Sparse
- usedIDs intsets.Sparse
+ nodeIDs idSet
}
// NewUndirectedGraph returns an UndirectedGraph with the specified self and absent
@@ -42,22 +39,9 @@ func (g *UndirectedGraph) NewNodeID() int {
return 0
}
if len(g.nodes) == maxInt {
- panic(fmt.Sprintf("simple: cannot allocate node: no slot"))
- }
-
- var id int
- if g.freeIDs.Len() != 0 && g.freeIDs.TakeMin(&id) {
- return id
- }
- if id = g.usedIDs.Max(); id < maxInt {
- return id + 1
+ panic("simple: cannot allocate node: no slot")
}
- for id = 0; id < maxInt; id++ {
- if !g.usedIDs.Has(id) {
- return id
- }
- }
- panic("unreachable")
+ return g.nodeIDs.newID()
}
// AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.
@@ -67,9 +51,7 @@ func (g *UndirectedGraph) AddNode(n graph.Node) {
}
g.nodes[n.ID()] = n
g.edges[n.ID()] = make(map[int]graph.Edge)
-
- g.freeIDs.Remove(n.ID())
- g.usedIDs.Insert(n.ID())
+ g.nodeIDs.use(n.ID())
}
// RemoveNode removes n from the graph, as well as any edges attached to it. If the node
@@ -85,9 +67,7 @@ func (g *UndirectedGraph) RemoveNode(n graph.Node) {
}
delete(g.edges, n.ID())
- g.freeIDs.Insert(n.ID())
- g.usedIDs.Remove(n.ID())
-
+ g.nodeIDs.release(n.ID())
}
// SetEdge adds e, an edge from one node to another. If the nodes do not exist, they are added.

graph/simple: factor id handling out of graphs