graph: factor id handling out to internal package uid
MODIFY
graph/simple/directed.go
graph/simple/directed.go
@@ -8,6 +8,7 @@ import (
"fmt"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/uid"
)
// DirectedGraph implements a generalized directed graph.
@@ -16,7 +17,7 @@ type DirectedGraph struct {
from map[int64]map[int64]graph.Edge
to map[int64]map[int64]graph.Edge
- nodeIDs idSet
+ nodeIDs uid.Set
}
// NewDirectedGraph returns a DirectedGraph with the specified self and absent
@@ -27,7 +28,7 @@ func NewDirectedGraph() *DirectedGraph {
from: make(map[int64]map[int64]graph.Edge),
to: make(map[int64]map[int64]graph.Edge),
- nodeIDs: newIDSet(),
+ nodeIDs: uid.NewSet(),
}
}
@@ -37,10 +38,10 @@ func (g *DirectedGraph) NewNode() graph.Node {
if len(g.nodes) == 0 {
return Node(0)
}
- if int64(len(g.nodes)) == maxInt {
+ if int64(len(g.nodes)) == uid.Max {
panic("simple: cannot allocate node: no slot")
}
- return Node(g.nodeIDs.newID())
+ return Node(g.nodeIDs.NewID())
}
// AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.
@@ -51,7 +52,7 @@ func (g *DirectedGraph) AddNode(n graph.Node) {
g.nodes[n.ID()] = n
g.from[n.ID()] = make(map[int64]graph.Edge)
g.to[n.ID()] = make(map[int64]graph.Edge)
- g.nodeIDs.use(n.ID())
+ g.nodeIDs.Use(n.ID())
}
// RemoveNode removes n from the graph, as well as any edges attached to it. If the node
@@ -72,7 +73,7 @@ func (g *DirectedGraph) RemoveNode(n graph.Node) {
}
delete(g.to, n.ID())
- g.nodeIDs.release(n.ID())
+ g.nodeIDs.Release(n.ID())
}
// NewEdge returns a new Edge from the source to the destination node.

MODIFY
graph/simple/simple.go
graph/simple/simple.go
@@ -8,7 +8,6 @@ import (
"math"
"gonum.org/v1/gonum/graph"
- "gonum.org/v1/gonum/graph/internal/set"
)
// Node is a simple graph node.
@@ -50,50 +49,3 @@ func (e WeightedEdge) Weight() float64 { return e.W }
func isSame(a, b float64) bool {
return a == b || (math.IsNaN(a) && math.IsNaN(b))
}
-
-// maxInt is the maximum value of int64.
-const maxInt = int64(^uint64(0) >> 1)
-
-// idSet implements available ID storage.
-type idSet struct {
- maxID int64
- used, free set.Int64s
-}
-
-// newIDSet returns a new idSet. The returned value should not be passed
-// except by pointer.
-func newIDSet() idSet {
- return idSet{maxID: -1, used: make(set.Int64s), free: make(set.Int64s)}
-}
-
-// newID returns a new unique ID. The ID returned is not considered used
-// until passed in a call to use.
-func (s *idSet) newID() int64 {
- for id := range s.free {
- return id
- }
- if s.maxID != maxInt {
- return s.maxID + 1
- }
- for id := int64(0); id <= s.maxID+1; 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 int64) {
- s.used.Add(id)
- s.free.Remove(id)
- if id > s.maxID {
- s.maxID = id
- }
-}
-
-// free frees the id for reuse.
-func (s *idSet) release(id int64) {
- s.free.Add(id)
- s.used.Remove(id)
-}

MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -8,6 +8,7 @@ import (
"fmt"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/uid"
)
// UndirectedGraph implements a generalized undirected graph.
@@ -15,7 +16,7 @@ type UndirectedGraph struct {
nodes map[int64]graph.Node
edges map[int64]map[int64]graph.Edge
- nodeIDs idSet
+ nodeIDs uid.Set
}
// NewUndirectedGraph returns an UndirectedGraph with the specified self and absent
@@ -25,7 +26,7 @@ func NewUndirectedGraph() *UndirectedGraph {
nodes: make(map[int64]graph.Node),
edges: make(map[int64]map[int64]graph.Edge),
- nodeIDs: newIDSet(),
+ nodeIDs: uid.NewSet(),
}
}
@@ -35,10 +36,10 @@ func (g *UndirectedGraph) NewNode() graph.Node {
if len(g.nodes) == 0 {
return Node(0)
}
- if int64(len(g.nodes)) == maxInt {
+ if int64(len(g.nodes)) == uid.Max {
panic("simple: cannot allocate node: no slot")
}
- return Node(g.nodeIDs.newID())
+ return Node(g.nodeIDs.NewID())
}
// AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.
@@ -48,7 +49,7 @@ func (g *UndirectedGraph) AddNode(n graph.Node) {
}
g.nodes[n.ID()] = n
g.edges[n.ID()] = make(map[int64]graph.Edge)
- g.nodeIDs.use(n.ID())
+ g.nodeIDs.Use(n.ID())
}
// RemoveNode removes n from the graph, as well as any edges attached to it. If the node
@@ -64,7 +65,7 @@ func (g *UndirectedGraph) RemoveNode(n graph.Node) {
}
delete(g.edges, n.ID())
- g.nodeIDs.release(n.ID())
+ g.nodeIDs.Release(n.ID())
}
// NewEdge returns a new Edge from the source to the destination node.

MODIFY
graph/simple/weighted_directed.go
graph/simple/weighted_directed.go
@@ -8,6 +8,7 @@ import (
"fmt"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/uid"
)
// WeightedDirectedGraph implements a generalized weighted directed graph.
@@ -18,7 +19,7 @@ type WeightedDirectedGraph struct {
self, absent float64
- nodeIDs idSet
+ nodeIDs uid.Set
}
// NewWeightedDirectedGraph returns a WeightedDirectedGraph with the specified self and absent
@@ -32,7 +33,7 @@ func NewWeightedDirectedGraph(self, absent float64) *WeightedDirectedGraph {
self: self,
absent: absent,
- nodeIDs: newIDSet(),
+ nodeIDs: uid.NewSet(),
}
}
@@ -42,10 +43,10 @@ func (g *WeightedDirectedGraph) NewNode() graph.Node {
if len(g.nodes) == 0 {
return Node(0)
}
- if int64(len(g.nodes)) == maxInt {
+ if int64(len(g.nodes)) == uid.Max {
panic("simple: cannot allocate node: no slot")
}
- return Node(g.nodeIDs.newID())
+ return Node(g.nodeIDs.NewID())
}
// AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.
@@ -56,7 +57,7 @@ func (g *WeightedDirectedGraph) AddNode(n graph.Node) {
g.nodes[n.ID()] = n
g.from[n.ID()] = make(map[int64]graph.WeightedEdge)
g.to[n.ID()] = make(map[int64]graph.WeightedEdge)
- g.nodeIDs.use(n.ID())
+ g.nodeIDs.Use(n.ID())
}
// RemoveNode removes n from the graph, as well as any edges attached to it. If the node
@@ -77,7 +78,7 @@ func (g *WeightedDirectedGraph) RemoveNode(n graph.Node) {
}
delete(g.to, n.ID())
- g.nodeIDs.release(n.ID())
+ g.nodeIDs.Release(n.ID())
}
// NewWeightedEdge returns a new weighted edge from the source to the destination node.

MODIFY
graph/simple/weighted_undirected.go
graph/simple/weighted_undirected.go
@@ -8,6 +8,7 @@ import (
"fmt"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/uid"
)
// WeightedUndirectedGraph implements a generalized weighted undirected graph.
@@ -17,7 +18,7 @@ type WeightedUndirectedGraph struct {
self, absent float64
- nodeIDs idSet
+ nodeIDs uid.Set
}
// NewWeightedUndirectedGraph returns an WeightedUndirectedGraph with the specified self and absent
@@ -30,7 +31,7 @@ func NewWeightedUndirectedGraph(self, absent float64) *WeightedUndirectedGraph {
self: self,
absent: absent,
- nodeIDs: newIDSet(),
+ nodeIDs: uid.NewSet(),
}
}
@@ -40,10 +41,10 @@ func (g *WeightedUndirectedGraph) NewNode() graph.Node {
if len(g.nodes) == 0 {
return Node(0)
}
- if int64(len(g.nodes)) == maxInt {
+ if int64(len(g.nodes)) == uid.Max {
panic("simple: cannot allocate node: no slot")
}
- return Node(g.nodeIDs.newID())
+ return Node(g.nodeIDs.NewID())
}
// AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.
@@ -53,7 +54,7 @@ func (g *WeightedUndirectedGraph) AddNode(n graph.Node) {
}
g.nodes[n.ID()] = n
g.edges[n.ID()] = make(map[int64]graph.WeightedEdge)
- g.nodeIDs.use(n.ID())
+ g.nodeIDs.Use(n.ID())
}
// RemoveNode removes n from the graph, as well as any edges attached to it. If the node
@@ -69,7 +70,7 @@ func (g *WeightedUndirectedGraph) RemoveNode(n graph.Node) {
}
delete(g.edges, n.ID())
- g.nodeIDs.release(n.ID())
+ g.nodeIDs.Release(n.ID())
}
// NewWeightedEdge returns a new weighted edge from the source to the destination node.

graph: factor id handling out to internal package uid