graph/simple: update for int64 IDs
MODIFY
graph/simple/dense_directed_matrix.go
graph/simple/dense_directed_matrix.go
@@ -54,7 +54,7 @@ func NewDirectedMatrix(n int, init, self, absent float64) *DirectedMatrix {
func NewDirectedMatrixFrom(nodes []graph.Node, init, self, absent float64) *DirectedMatrix {
sort.Sort(ordered.ByID(nodes))
for i, n := range nodes {
- if i != n.ID() {
+ if int64(i) != n.ID() {
panic("simple: non-contiguous node IDs")
}
}
@@ -64,7 +64,7 @@ func NewDirectedMatrixFrom(nodes []graph.Node, init, self, absent float64) *Dire
}
// Node returns the node in the graph with the given ID.
-func (g *DirectedMatrix) Node(id int) graph.Node {
+func (g *DirectedMatrix) Node(id int64) graph.Node {
if !g.has(id) {
return nil
}
@@ -79,9 +79,9 @@ func (g *DirectedMatrix) Has(n graph.Node) bool {
return g.has(n.ID())
}
-func (g *DirectedMatrix) has(id int) bool {
+func (g *DirectedMatrix) has(id int64) bool {
r, _ := g.mat.Dims()
- return 0 <= id && id < r
+ return 0 <= id && id < int64(r)
}
// Nodes returns all the nodes in the graph.
@@ -109,7 +109,7 @@ func (g *DirectedMatrix) Edges() []graph.Edge {
continue
}
if w := g.mat.At(i, j); !isSame(w, g.absent) {
- edges = append(edges, Edge{F: g.Node(i), T: g.Node(j), W: w})
+ edges = append(edges, Edge{F: g.Node(int64(i)), T: g.Node(int64(j)), W: w})
}
}
}
@@ -125,11 +125,12 @@ func (g *DirectedMatrix) From(n graph.Node) []graph.Node {
var neighbors []graph.Node
_, c := g.mat.Dims()
for j := 0; j < c; j++ {
- if j == id {
+ if int64(j) == id {
continue
}
- if !isSame(g.mat.At(id, j), g.absent) {
- neighbors = append(neighbors, g.Node(j))
+ // id is not greater than maximum int by this point.
+ if !isSame(g.mat.At(int(id), j), g.absent) {
+ neighbors = append(neighbors, g.Node(int64(j)))
}
}
return neighbors
@@ -144,11 +145,12 @@ func (g *DirectedMatrix) To(n graph.Node) []graph.Node {
var neighbors []graph.Node
r, _ := g.mat.Dims()
for i := 0; i < r; i++ {
- if i == id {
+ if int64(i) == id {
continue
}
- if !isSame(g.mat.At(i, id), g.absent) {
- neighbors = append(neighbors, g.Node(i))
+ // id is not greater than maximum int by this point.
+ if !isSame(g.mat.At(i, int(id)), g.absent) {
+ neighbors = append(neighbors, g.Node(int64(i)))
}
}
return neighbors
@@ -165,14 +167,16 @@ func (g *DirectedMatrix) HasEdgeBetween(x, y graph.Node) bool {
if !g.has(yid) {
return false
}
- return xid != yid && (!isSame(g.mat.At(xid, yid), g.absent) || !isSame(g.mat.At(yid, xid), g.absent))
+ // xid and yid are not greater than maximum int by this point.
+ return xid != yid && (!isSame(g.mat.At(int(xid), int(yid)), g.absent) || !isSame(g.mat.At(int(yid), int(xid)), g.absent))
}
// Edge returns the edge from u to v if such an edge exists and nil otherwise.
// The node v must be directly reachable from u as defined by the From method.
func (g *DirectedMatrix) Edge(u, v graph.Node) graph.Edge {
if g.HasEdgeFromTo(u, v) {
- return Edge{F: g.Node(u.ID()), T: g.Node(v.ID()), W: g.mat.At(u.ID(), v.ID())}
+ // x.ID() and y.ID() are not greater than maximum int by this point.
+ return Edge{F: g.Node(u.ID()), T: g.Node(v.ID()), W: g.mat.At(int(u.ID()), int(v.ID()))}
}
return nil
}
@@ -187,7 +191,8 @@ func (g *DirectedMatrix) HasEdgeFromTo(u, v graph.Node) bool {
if !g.has(vid) {
return false
}
- return uid != vid && !isSame(g.mat.At(uid, vid), g.absent)
+ // uid and vid are not greater than maximum int by this point.
+ return uid != vid && !isSame(g.mat.At(int(uid), int(vid)), g.absent)
}
// Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge.
@@ -201,7 +206,8 @@ func (g *DirectedMatrix) Weight(x, y graph.Node) (w float64, ok bool) {
return g.self, true
}
if g.has(xid) && g.has(yid) {
- return g.mat.At(xid, yid), true
+ // xid and yid are not greater than maximum int by this point.
+ return g.mat.At(int(xid), int(yid)), true
}
return g.absent, false
}
@@ -214,7 +220,14 @@ func (g *DirectedMatrix) SetEdge(e graph.Edge) {
if fid == tid {
panic("simple: set illegal edge")
}
- g.mat.Set(fid, tid, e.Weight())
+ if int64(int(fid)) != fid {
+ panic("simple: unavailable from node ID for dense graph")
+ }
+ if int64(int(tid)) != tid {
+ panic("simple: unavailable to node ID for dense graph")
+ }
+ // fid and tid are not greater than maximum int by this point.
+ g.mat.Set(int(fid), int(tid), e.Weight())
}
// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
@@ -228,27 +241,33 @@ func (g *DirectedMatrix) RemoveEdge(e graph.Edge) {
if !g.has(tid) {
return
}
- g.mat.Set(fid, tid, g.absent)
+ // fid and tid are not greater than maximum int by this point.
+ g.mat.Set(int(fid), int(tid), g.absent)
}
// Degree returns the in+out degree of n in g.
func (g *DirectedMatrix) Degree(n graph.Node) int {
id := n.ID()
+ if !g.has(id) {
+ return 0
+ }
var deg int
r, c := g.mat.Dims()
for i := 0; i < r; i++ {
- if i == id {
+ if int64(i) == id {
continue
}
- if !isSame(g.mat.At(id, i), g.absent) {
+ // id is not greater than maximum int by this point.
+ if !isSame(g.mat.At(int(id), i), g.absent) {
deg++
}
}
for i := 0; i < c; i++ {
- if i == id {
+ if int64(i) == id {
continue
}
- if !isSame(g.mat.At(i, id), g.absent) {
+ // id is not greater than maximum int by this point.
+ if !isSame(g.mat.At(i, int(id)), g.absent) {
deg++
}
}

MODIFY
graph/simple/dense_undirected_matrix.go
graph/simple/dense_undirected_matrix.go
@@ -54,7 +54,7 @@ func NewUndirectedMatrix(n int, init, self, absent float64) *UndirectedMatrix {
func NewUndirectedMatrixFrom(nodes []graph.Node, init, self, absent float64) *UndirectedMatrix {
sort.Sort(ordered.ByID(nodes))
for i, n := range nodes {
- if i != n.ID() {
+ if int64(i) != n.ID() {
panic("simple: non-contiguous node IDs")
}
}
@@ -64,7 +64,7 @@ func NewUndirectedMatrixFrom(nodes []graph.Node, init, self, absent float64) *Un
}
// Node returns the node in the graph with the given ID.
-func (g *UndirectedMatrix) Node(id int) graph.Node {
+func (g *UndirectedMatrix) Node(id int64) graph.Node {
if !g.has(id) {
return nil
}
@@ -79,9 +79,9 @@ func (g *UndirectedMatrix) Has(n graph.Node) bool {
return g.has(n.ID())
}
-func (g *UndirectedMatrix) has(id int) bool {
+func (g *UndirectedMatrix) has(id int64) bool {
r := g.mat.Symmetric()
- return 0 <= id && id < r
+ return 0 <= id && id < int64(r)
}
// Nodes returns all the nodes in the graph.
@@ -106,7 +106,7 @@ func (g *UndirectedMatrix) Edges() []graph.Edge {
for i := 0; i < r; i++ {
for j := i + 1; j < r; j++ {
if w := g.mat.At(i, j); !isSame(w, g.absent) {
- edges = append(edges, Edge{F: g.Node(i), T: g.Node(j), W: w})
+ edges = append(edges, Edge{F: g.Node(int64(i)), T: g.Node(int64(j)), W: w})
}
}
}
@@ -122,11 +122,12 @@ func (g *UndirectedMatrix) From(n graph.Node) []graph.Node {
var neighbors []graph.Node
r := g.mat.Symmetric()
for i := 0; i < r; i++ {
- if i == id {
+ if int64(i) == id {
continue
}
- if !isSame(g.mat.At(id, i), g.absent) {
- neighbors = append(neighbors, g.Node(i))
+ // id is not greater than maximum int by this point.
+ if !isSame(g.mat.At(int(id), i), g.absent) {
+ neighbors = append(neighbors, g.Node(int64(i)))
}
}
return neighbors
@@ -142,7 +143,8 @@ func (g *UndirectedMatrix) HasEdgeBetween(u, v graph.Node) bool {
if !g.has(vid) {
return false
}
- return uid != vid && !isSame(g.mat.At(uid, vid), g.absent)
+ // uid and vid are not greater than maximum int by this point.
+ return uid != vid && !isSame(g.mat.At(int(uid), int(vid)), g.absent)
}
// Edge returns the edge from u to v if such an edge exists and nil otherwise.
@@ -154,7 +156,8 @@ func (g *UndirectedMatrix) Edge(u, v graph.Node) graph.Edge {
// EdgeBetween returns the edge between nodes x and y.
func (g *UndirectedMatrix) EdgeBetween(u, v graph.Node) graph.Edge {
if g.HasEdgeBetween(u, v) {
- return Edge{F: g.Node(u.ID()), T: g.Node(v.ID()), W: g.mat.At(u.ID(), v.ID())}
+ // u.ID() and v.ID() are not greater than maximum int by this point.
+ return Edge{F: g.Node(u.ID()), T: g.Node(v.ID()), W: g.mat.At(int(u.ID()), int(v.ID()))}
}
return nil
}
@@ -170,7 +173,8 @@ func (g *UndirectedMatrix) Weight(x, y graph.Node) (w float64, ok bool) {
return g.self, true
}
if g.has(xid) && g.has(yid) {
- return g.mat.At(xid, yid), true
+ // xid and yid are not greater than maximum int by this point.
+ return g.mat.At(int(xid), int(yid)), true
}
return g.absent, false
}
@@ -183,7 +187,14 @@ func (g *UndirectedMatrix) SetEdge(e graph.Edge) {
if fid == tid {
panic("simple: set illegal edge")
}
- g.mat.SetSym(fid, tid, e.Weight())
+ if int64(int(fid)) != fid {
+ panic("simple: unavailable from node ID for dense graph")
+ }
+ if int64(int(tid)) != tid {
+ panic("simple: unavailable to node ID for dense graph")
+ }
+ // fid and tid are not greater than maximum int by this point.
+ g.mat.SetSym(int(fid), int(tid), e.Weight())
}
// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
@@ -197,19 +208,24 @@ func (g *UndirectedMatrix) RemoveEdge(e graph.Edge) {
if !g.has(tid) {
return
}
- g.mat.SetSym(fid, tid, g.absent)
+ // fid and tid are not greater than maximum int by this point.
+ g.mat.SetSym(int(fid), int(tid), g.absent)
}
// Degree returns the degree of n in g.
func (g *UndirectedMatrix) Degree(n graph.Node) int {
id := n.ID()
+ if !g.has(id) {
+ return 0
+ }
var deg int
r := g.mat.Symmetric()
for i := 0; i < r; i++ {
- if i == id {
+ if int64(i) == id {
continue
}
- if !isSame(g.mat.At(id, i), g.absent) {
+ // id is not greater than maximum int by this point.
+ if !isSame(g.mat.At(int(id), i), g.absent) {
deg++
}
}

MODIFY
graph/simple/densegraph_test.go
graph/simple/densegraph_test.go
@@ -122,7 +122,7 @@ func TestDenseLists(t *testing.T) {
sort.Sort(ordered.ByID(nodes))
for i, node := range dg.Nodes() {
- if i != node.ID() {
+ if int64(i) != node.ID() {
t.Errorf("Node list doesn't return properly id'd nodes")
}
}

MODIFY
graph/simple/directed.go
graph/simple/directed.go
@@ -12,9 +12,9 @@ import (
// DirectedGraph implements a generalized directed graph.
type DirectedGraph struct {
- nodes map[int]graph.Node
- from map[int]map[int]graph.Edge
- to map[int]map[int]graph.Edge
+ nodes map[int64]graph.Node
+ from map[int64]map[int64]graph.Edge
+ to map[int64]map[int64]graph.Edge
self, absent float64
@@ -25,9 +25,9 @@ type DirectedGraph struct {
// edge weight values.
func NewDirectedGraph(self, absent float64) *DirectedGraph {
return &DirectedGraph{
- nodes: make(map[int]graph.Node),
- from: make(map[int]map[int]graph.Edge),
- to: make(map[int]map[int]graph.Edge),
+ nodes: make(map[int64]graph.Node),
+ from: make(map[int64]map[int64]graph.Edge),
+ to: make(map[int64]map[int64]graph.Edge),
self: self,
absent: absent,
@@ -38,11 +38,11 @@ func NewDirectedGraph(self, absent float64) *DirectedGraph {
// NewNodeID returns a new unique ID for a node to be added to g. The returned ID does
// not become a valid ID in g until it is added to g.
-func (g *DirectedGraph) NewNodeID() int {
+func (g *DirectedGraph) NewNodeID() int64 {
if len(g.nodes) == 0 {
return 0
}
- if len(g.nodes) == maxInt {
+ if int64(len(g.nodes)) == maxInt {
panic("simple: cannot allocate node: no slot")
}
return g.nodeIDs.newID()
@@ -54,8 +54,8 @@ func (g *DirectedGraph) AddNode(n graph.Node) {
panic(fmt.Sprintf("simple: node ID collision: %d", n.ID()))
}
g.nodes[n.ID()] = n
- g.from[n.ID()] = make(map[int]graph.Edge)
- g.to[n.ID()] = make(map[int]graph.Edge)
+ g.from[n.ID()] = make(map[int64]graph.Edge)
+ g.to[n.ID()] = make(map[int64]graph.Edge)
g.nodeIDs.use(n.ID())
}
@@ -121,7 +121,7 @@ func (g *DirectedGraph) RemoveEdge(e graph.Edge) {
}
// Node returns the node in the graph with the given ID.
-func (g *DirectedGraph) Node(id int) graph.Node {
+func (g *DirectedGraph) Node(id int64) graph.Node {
return g.nodes[id]
}

MODIFY
graph/simple/simple.go
graph/simple/simple.go
@@ -14,11 +14,11 @@ import (
)
// Node is a simple graph node.
-type Node int
+type Node int64
// ID returns the ID number of the node.
-func (n Node) ID() int {
- return int(n)
+func (n Node) ID() int64 {
+ return int64(n)
}
// Edge is a simple graph edge.
@@ -42,31 +42,31 @@ func isSame(a, b float64) bool {
return a == b || (math.IsNaN(a) && math.IsNaN(b))
}
-// maxInt is the maximum value of the machine-dependent int type.
-const maxInt int = int(^uint(0) >> 1)
+// maxInt is the maximum value of int64.
+const maxInt = int64(^uint64(0) >> 1)
// idSet implements available ID storage.
type idSet struct {
- maxID int
- used, free set.Ints
+ 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.Ints), free: make(set.Ints)}
+ 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() int {
+func (s *idSet) newID() int64 {
for id := range s.free {
return id
}
if s.maxID != maxInt {
return s.maxID + 1
}
- for id := 0; id <= s.maxID+1; id++ {
+ for id := int64(0); id <= s.maxID+1; id++ {
if !s.used.Has(id) {
return id
}
@@ -75,7 +75,7 @@ func (s *idSet) newID() int {
}
// use adds the id to the used IDs in the idSet.
-func (s *idSet) use(id int) {
+func (s *idSet) use(id int64) {
s.used.Add(id)
s.free.Remove(id)
if id > s.maxID {
@@ -84,7 +84,7 @@ func (s *idSet) use(id int) {
}
// free frees the id for reuse.
-func (s *idSet) release(id int) {
+func (s *idSet) release(id int64) {
s.free.Add(id)
s.used.Remove(id)
}

MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -12,8 +12,8 @@ import (
// UndirectedGraph implements a generalized undirected graph.
type UndirectedGraph struct {
- nodes map[int]graph.Node
- edges map[int]map[int]graph.Edge
+ nodes map[int64]graph.Node
+ edges map[int64]map[int64]graph.Edge
self, absent float64
@@ -24,8 +24,8 @@ type UndirectedGraph struct {
// edge weight values.
func NewUndirectedGraph(self, absent float64) *UndirectedGraph {
return &UndirectedGraph{
- nodes: make(map[int]graph.Node),
- edges: make(map[int]map[int]graph.Edge),
+ nodes: make(map[int64]graph.Node),
+ edges: make(map[int64]map[int64]graph.Edge),
self: self,
absent: absent,
@@ -36,11 +36,11 @@ func NewUndirectedGraph(self, absent float64) *UndirectedGraph {
// NewNodeID returns a new unique ID for a node to be added to g. The returned ID does
// not become a valid ID in g until it is added to g.
-func (g *UndirectedGraph) NewNodeID() int {
+func (g *UndirectedGraph) NewNodeID() int64 {
if len(g.nodes) == 0 {
return 0
}
- if len(g.nodes) == maxInt {
+ if int64(len(g.nodes)) == maxInt {
panic("simple: cannot allocate node: no slot")
}
return g.nodeIDs.newID()
@@ -52,7 +52,7 @@ func (g *UndirectedGraph) AddNode(n graph.Node) {
panic(fmt.Sprintf("simple: node ID collision: %d", n.ID()))
}
g.nodes[n.ID()] = n
- g.edges[n.ID()] = make(map[int]graph.Edge)
+ g.edges[n.ID()] = make(map[int64]graph.Edge)
g.nodeIDs.use(n.ID())
}
@@ -113,7 +113,7 @@ func (g *UndirectedGraph) RemoveEdge(e graph.Edge) {
}
// Node returns the node in the graph with the given ID.
-func (g *UndirectedGraph) Node(id int) graph.Node {
+func (g *UndirectedGraph) Node(id int64) graph.Node {
return g.nodes[id]
}
@@ -139,16 +139,16 @@ func (g *UndirectedGraph) Nodes() []graph.Node {
func (g *UndirectedGraph) Edges() []graph.Edge {
var edges []graph.Edge
- seen := make(map[[2]int]struct{})
+ seen := make(map[[2]int64]struct{})
for _, u := range g.edges {
for _, e := range u {
uid := e.From().ID()
vid := e.To().ID()
- if _, ok := seen[[2]int{uid, vid}]; ok {
+ if _, ok := seen[[2]int64{uid, vid}]; ok {
continue
}
- seen[[2]int{uid, vid}] = struct{}{}
- seen[[2]int{vid, uid}] = struct{}{}
+ seen[[2]int64{uid, vid}] = struct{}{}
+ seen[[2]int64{vid, uid}] = struct{}{}
edges = append(edges, e)
}
}

graph/simple: update for int64 IDs