graph/community: update for int64 IDs
The internal representation of reduced graphs remains based around int
IDs since the operations must happen in memory, and there is an initial
ID densification step to get from the target graph to the communities.
MODIFY
graph/community/louvain_common.go
graph/community/louvain_common.go
@@ -230,8 +230,18 @@ type directedEdges struct {
weights map[[2]int]float64
}
+// isValidID returns whether id is a valid ID for a community,
+// multiplexCommunity or node. These are all graph.Node types
+// stored in []T with a mapping between their index and their ID
+// so IDs must be positive and fit within the int type.
+func isValidID(id int64) bool {
+ return id == int64(int(id)) && id >= 0
+}
+
// community is a reduced graph node describing its membership.
type community struct {
+ // community graphs are internal, in-memory
+ // with dense IDs, so id is always an int.
id int
nodes []graph.Node
@@ -239,7 +249,7 @@ type community struct {
weight float64
}
-func (n community) ID() int { return n.id }
+func (n community) ID() int64 { return int64(n.id) }
// edge is a reduced graph edge.
type edge struct {
@@ -253,6 +263,8 @@ func (e edge) Weight() float64 { return e.weight }
// multiplexCommunity is a reduced multiplex graph node describing its membership.
type multiplexCommunity struct {
+ // community graphs are internal, in-memory
+ // with dense IDs, so id is always an int.
id int
nodes []graph.Node
@@ -260,7 +272,7 @@ type multiplexCommunity struct {
weights []float64
}
-func (n multiplexCommunity) ID() int { return n.id }
+func (n multiplexCommunity) ID() int64 { return int64(n.id) }
// multiplexEdge is a reduced graph edge for a multiplex graph.
type multiplexEdge struct {
@@ -278,10 +290,11 @@ type commIdx struct {
node int
}
-// node is defined to avoid an import of .../graph/simple.
+// node is defined to avoid an import of .../graph/simple. node is
+// used in in-memory, dense ID graphs and so is always an int.
type node int
-func (n node) ID() int { return int(n) }
+func (n node) ID() int64 { return int64(n) }
// minTaker is a set iterator.
type minTaker interface {

MODIFY
graph/community/louvain_directed.go
graph/community/louvain_directed.go
@@ -29,7 +29,7 @@ func qDirected(g graph.Directed, communities [][]graph.Node, resolution float64)
// Calculate the total edge weight of the graph
// and the table of penetrating edge weight sums.
var m float64
- k := make(map[int]directedWeights, len(nodes))
+ k := make(map[int64]directedWeights, len(nodes))
for _, n := range nodes {
var wOut float64
u := n
@@ -191,7 +191,7 @@ func reduceDirected(g graph.Directed, communities [][]graph.Node) *ReducedDirect
},
communities: communities,
}
- communityOf := make(map[int]int, len(nodes))
+ communityOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
r.nodes[i] = community{id: i, nodes: []graph.Node{n}}
communityOf[n.ID()] = i
@@ -257,7 +257,7 @@ func reduceDirected(g graph.Directed, communities [][]graph.Node) *ReducedDirect
r.parent = g
}
weight := positiveWeightFuncFor(g)
- communityOf := make(map[int]int, commNodes)
+ communityOf := make(map[int64]int, commNodes)
for i, comm := range communities {
r.nodes[i] = community{id: i, nodes: comm}
for _, n := range comm {
@@ -316,7 +316,7 @@ func reduceDirected(g graph.Directed, communities [][]graph.Node) *ReducedDirect
// Has returns whether the node exists within the graph.
func (g *ReducedDirected) Has(n graph.Node) bool {
id := n.ID()
- return id >= 0 || id < len(g.nodes)
+ return 0 <= id && id < int64(len(g.nodes))
}
// Nodes returns all the nodes in the graph.
@@ -352,14 +352,14 @@ func (g *ReducedDirected) To(v graph.Node) []graph.Node {
func (g *ReducedDirected) HasEdgeBetween(x, y graph.Node) bool {
xid := x.ID()
yid := y.ID()
- if xid == yid {
+ if xid == yid || !isValidID(xid) || !isValidID(yid) {
return false
}
- _, ok := g.weights[[2]int{xid, yid}]
+ _, ok := g.weights[[2]int{int(xid), int(yid)}]
if ok {
return true
}
- _, ok = g.weights[[2]int{yid, xid}]
+ _, ok = g.weights[[2]int{int(yid), int(xid)}]
return ok
}
@@ -367,10 +367,10 @@ func (g *ReducedDirected) HasEdgeBetween(x, y graph.Node) bool {
func (g *ReducedDirected) HasEdgeFromTo(u, v graph.Node) bool {
uid := u.ID()
vid := v.ID()
- if uid == vid {
+ if uid == vid || !isValidID(uid) || !isValidID(vid) {
return false
}
- _, ok := g.weights[[2]int{uid, vid}]
+ _, ok := g.weights[[2]int{int(uid), int(vid)}]
return ok
}
@@ -379,7 +379,10 @@ func (g *ReducedDirected) HasEdgeFromTo(u, v graph.Node) bool {
func (g *ReducedDirected) Edge(u, v graph.Node) graph.Edge {
uid := u.ID()
vid := v.ID()
- w, ok := g.weights[[2]int{uid, vid}]
+ if uid == vid || !isValidID(uid) || !isValidID(vid) {
+ return nil
+ }
+ w, ok := g.weights[[2]int{int(uid), int(vid)}]
if !ok {
return nil
}
@@ -393,10 +396,13 @@ func (g *ReducedDirected) Edge(u, v graph.Node) graph.Edge {
func (g *ReducedDirected) Weight(x, y graph.Node) (w float64, ok bool) {
xid := x.ID()
yid := y.ID()
+ if !isValidID(xid) || !isValidID(yid) {
+ return 0, false
+ }
if xid == yid {
return g.nodes[xid].weight, true
}
- w, ok = g.weights[[2]int{xid, yid}]
+ w, ok = g.weights[[2]int{int(xid), int(yid)}]
return w, ok
}

MODIFY
graph/community/louvain_directed_multiplex.go
graph/community/louvain_directed_multiplex.go
@@ -72,7 +72,7 @@ func qDirectedMultiplex(g DirectedMultiplex, communities [][]graph.Node, weights
// Calculate the total edge weight of the layer
// and the table of penetrating edge weight sums.
var m float64
- k := make(map[int]directedWeights, len(nodes))
+ k := make(map[int64]directedWeights, len(nodes))
for _, n := range nodes {
var wOut float64
u := n
@@ -124,16 +124,16 @@ func NewDirectedLayers(layers ...graph.Directed) (DirectedLayers, error) {
if len(layers) == 0 {
return nil, nil
}
- base := make(set.Ints)
+ base := make(set.Int64s)
for _, n := range layers[0].Nodes() {
base.Add(n.ID())
}
for i, l := range layers[1:] {
- next := make(set.Ints)
+ next := make(set.Int64s)
for _, n := range l.Nodes() {
next.Add(n.ID())
}
- if !set.IntsEqual(base, next) {
+ if !set.Int64sEqual(base, next) {
return nil, fmt.Errorf("community: layer ID mismatch between layers: %d", i+1)
}
}
@@ -299,7 +299,7 @@ func reduceDirectedMultiplex(g DirectedMultiplex, communities [][]graph.Node, we
layers: make([]directedEdges, g.Depth()),
communities: communities,
}
- communityOf := make(map[int]int, len(nodes))
+ communityOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
r.nodes[i] = multiplexCommunity{id: i, nodes: []graph.Node{n}, weights: make([]float64, depth(weights))}
communityOf[n.ID()] = i
@@ -374,7 +374,7 @@ func reduceDirectedMultiplex(g DirectedMultiplex, communities [][]graph.Node, we
nodes: make([]multiplexCommunity, len(communities)),
layers: make([]directedEdges, g.Depth()),
}
- communityOf := make(map[int]int, commNodes)
+ communityOf := make(map[int64]int, commNodes)
for i, comm := range communities {
r.nodes[i] = multiplexCommunity{id: i, nodes: comm, weights: make([]float64, depth(weights))}
for _, n := range comm {
@@ -480,7 +480,7 @@ type directedLayerHandle struct {
// Has returns whether the node exists within the graph.
func (g directedLayerHandle) Has(n graph.Node) bool {
id := n.ID()
- return id >= 0 || id < len(g.multiplex.nodes)
+ return 0 <= id && id < int64(len(g.multiplex.nodes))
}
// Nodes returns all the nodes in the graph.
@@ -519,11 +519,14 @@ func (g directedLayerHandle) HasEdgeBetween(x, y graph.Node) bool {
if xid == yid {
return false
}
- _, ok := g.multiplex.layers[g.layer].weights[[2]int{xid, yid}]
+ if xid == yid || !isValidID(xid) || !isValidID(yid) {
+ return false
+ }
+ _, ok := g.multiplex.layers[g.layer].weights[[2]int{int(xid), int(yid)}]
if ok {
return true
}
- _, ok = g.multiplex.layers[g.layer].weights[[2]int{yid, xid}]
+ _, ok = g.multiplex.layers[g.layer].weights[[2]int{int(yid), int(xid)}]
return ok
}
@@ -531,10 +534,10 @@ func (g directedLayerHandle) HasEdgeBetween(x, y graph.Node) bool {
func (g directedLayerHandle) HasEdgeFromTo(u, v graph.Node) bool {
uid := u.ID()
vid := v.ID()
- if uid == vid {
+ if uid == vid || !isValidID(uid) || !isValidID(vid) {
return false
}
- _, ok := g.multiplex.layers[g.layer].weights[[2]int{uid, vid}]
+ _, ok := g.multiplex.layers[g.layer].weights[[2]int{int(uid), int(vid)}]
return ok
}
@@ -543,7 +546,10 @@ func (g directedLayerHandle) HasEdgeFromTo(u, v graph.Node) bool {
func (g directedLayerHandle) Edge(u, v graph.Node) graph.Edge {
uid := u.ID()
vid := v.ID()
- w, ok := g.multiplex.layers[g.layer].weights[[2]int{uid, vid}]
+ if uid == vid || !isValidID(uid) || !isValidID(vid) {
+ return nil
+ }
+ w, ok := g.multiplex.layers[g.layer].weights[[2]int{int(uid), int(vid)}]
if !ok {
return nil
}
@@ -562,10 +568,13 @@ func (g directedLayerHandle) EdgeBetween(x, y graph.Node) graph.Edge {
func (g directedLayerHandle) Weight(x, y graph.Node) (w float64, ok bool) {
xid := x.ID()
yid := y.ID()
+ if !isValidID(xid) || !isValidID(yid) {
+ return 0, false
+ }
if xid == yid {
return g.multiplex.nodes[xid].weights[g.layer], true
}
- w, ok = g.multiplex.layers[g.layer].weights[[2]int{xid, yid}]
+ w, ok = g.multiplex.layers[g.layer].weights[[2]int{int(xid), int(yid)}]
return w, ok
}

MODIFY
graph/community/louvain_directed_multiplex_test.go
graph/community/louvain_directed_multiplex_test.go
@@ -326,10 +326,11 @@ tests:
rnd := rand.New(rand.NewSource(1)).Intn
for _, structure := range test.structures {
- communityOf := make(map[int]int)
+ communityOf := make(map[int64]int)
communities := make([][]graph.Node, len(structure.memberships))
for i, c := range structure.memberships {
for n := range c {
+ n := int64(n)
communityOf[n] = i
communities[i] = append(communities[i], simple.Node(n))
}
@@ -365,6 +366,7 @@ tests:
migrated := make([][]graph.Node, len(structure.memberships))
for i, c := range structure.memberships {
for n := range c {
+ n := int64(n)
if n == target.ID() {
continue
}

MODIFY
graph/community/louvain_directed_test.go
graph/community/louvain_directed_test.go
@@ -244,10 +244,11 @@ tests:
rnd := rand.New(rand.NewSource(1)).Intn
for _, structure := range test.structures {
- communityOf := make(map[int]int)
+ communityOf := make(map[int64]int)
communities := make([][]graph.Node, len(structure.memberships))
for i, c := range structure.memberships {
for n := range c {
+ n := int64(n)
communityOf[n] = i
communities[i] = append(communities[i], simple.Node(n))
}
@@ -277,6 +278,7 @@ tests:
migrated := make([][]graph.Node, len(structure.memberships))
for i, c := range structure.memberships {
for n := range c {
+ n := int64(n)
if n == target.ID() {
continue
}

MODIFY
graph/community/louvain_undirected.go
graph/community/louvain_undirected.go
@@ -31,7 +31,7 @@ func qUndirected(g graph.Undirected, communities [][]graph.Node, resolution floa
// Calculate the total edge weight of the graph
// and the table of penetrating edge weight sums.
var m2 float64
- k := make(map[int]float64, len(nodes))
+ k := make(map[int64]float64, len(nodes))
for _, u := range nodes {
w := weight(u, u)
for _, v := range g.From(u) {
@@ -190,7 +190,7 @@ func reduceUndirected(g graph.Undirected, communities [][]graph.Node) *ReducedUn
},
communities: communities,
}
- communityOf := make(map[int]int, len(nodes))
+ communityOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
r.nodes[i] = community{id: i, nodes: []graph.Node{n}}
communityOf[n.ID()] = i
@@ -245,7 +245,7 @@ func reduceUndirected(g graph.Undirected, communities [][]graph.Node) *ReducedUn
r.parent = g
}
weight := positiveWeightFuncFor(g)
- communityOf := make(map[int]int, commNodes)
+ communityOf := make(map[int64]int, commNodes)
for i, comm := range communities {
r.nodes[i] = community{id: i, nodes: comm}
for _, n := range comm {
@@ -285,7 +285,7 @@ func reduceUndirected(g graph.Undirected, communities [][]graph.Node) *ReducedUn
// Has returns whether the node exists within the graph.
func (g *ReducedUndirected) Has(n graph.Node) bool {
id := n.ID()
- return id >= 0 || id < len(g.nodes)
+ return 0 <= id || id < int64(len(g.nodes))
}
// Nodes returns all the nodes in the graph.
@@ -311,13 +311,13 @@ func (g *ReducedUndirected) From(u graph.Node) []graph.Node {
func (g *ReducedUndirected) HasEdgeBetween(x, y graph.Node) bool {
xid := x.ID()
yid := y.ID()
- if xid == yid {
+ if xid == yid || !isValidID(xid) || !isValidID(yid) {
return false
}
if xid > yid {
xid, yid = yid, xid
}
- _, ok := g.weights[[2]int{xid, yid}]
+ _, ok := g.weights[[2]int{int(xid), int(yid)}]
return ok
}
@@ -326,10 +326,13 @@ func (g *ReducedUndirected) HasEdgeBetween(x, y graph.Node) bool {
func (g *ReducedUndirected) Edge(u, v graph.Node) graph.Edge {
uid := u.ID()
vid := v.ID()
+ if uid == vid || !isValidID(uid) || !isValidID(vid) {
+ return nil
+ }
if vid < uid {
uid, vid = vid, uid
}
- w, ok := g.weights[[2]int{uid, vid}]
+ w, ok := g.weights[[2]int{int(uid), int(vid)}]
if !ok {
return nil
}
@@ -348,13 +351,16 @@ func (g *ReducedUndirected) EdgeBetween(x, y graph.Node) graph.Edge {
func (g *ReducedUndirected) Weight(x, y graph.Node) (w float64, ok bool) {
xid := x.ID()
yid := y.ID()
+ if !isValidID(xid) || !isValidID(yid) {
+ return 0, false
+ }
if xid == yid {
return g.nodes[xid].weight, true
}
if xid > yid {
xid, yid = yid, xid
}
- w, ok = g.weights[[2]int{xid, yid}]
+ w, ok = g.weights[[2]int{int(xid), int(yid)}]
return w, ok
}

MODIFY
graph/community/louvain_undirected_multiplex.go
graph/community/louvain_undirected_multiplex.go
@@ -75,7 +75,7 @@ func qUndirectedMultiplex(g UndirectedMultiplex, communities [][]graph.Node, wei
// Calculate the total edge weight of the layer
// and the table of penetrating edge weight sums.
var m2 float64
- k := make(map[int]float64, len(nodes))
+ k := make(map[int64]float64, len(nodes))
for _, u := range nodes {
w := weight(u, u)
for _, v := range layer.From(u) {
@@ -123,16 +123,16 @@ func NewUndirectedLayers(layers ...graph.Undirected) (UndirectedLayers, error) {
if len(layers) == 0 {
return nil, nil
}
- base := make(set.Ints)
+ base := make(set.Int64s)
for _, n := range layers[0].Nodes() {
base.Add(n.ID())
}
for i, l := range layers[1:] {
- next := make(set.Ints)
+ next := make(set.Int64s)
for _, n := range l.Nodes() {
next.Add(n.ID())
}
- if !set.IntsEqual(next, base) {
+ if !set.Int64sEqual(next, base) {
return nil, fmt.Errorf("community: layer ID mismatch between layers: %d", i+1)
}
}
@@ -298,7 +298,7 @@ func reduceUndirectedMultiplex(g UndirectedMultiplex, communities [][]graph.Node
layers: make([]undirectedEdges, g.Depth()),
communities: communities,
}
- communityOf := make(map[int]int, len(nodes))
+ communityOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
r.nodes[i] = multiplexCommunity{id: i, nodes: []graph.Node{n}, weights: make([]float64, depth(weights))}
communityOf[n.ID()] = i
@@ -362,7 +362,7 @@ func reduceUndirectedMultiplex(g UndirectedMultiplex, communities [][]graph.Node
nodes: make([]multiplexCommunity, len(communities)),
layers: make([]undirectedEdges, g.Depth()),
}
- communityOf := make(map[int]int, commNodes)
+ communityOf := make(map[int64]int, commNodes)
for i, comm := range communities {
r.nodes[i] = multiplexCommunity{id: i, nodes: comm, weights: make([]float64, depth(weights))}
for _, n := range comm {
@@ -447,7 +447,7 @@ type undirectedLayerHandle struct {
// Has returns whether the node exists within the graph.
func (g undirectedLayerHandle) Has(n graph.Node) bool {
id := n.ID()
- return id >= 0 || id < len(g.multiplex.nodes)
+ return 0 <= id && id < int64(len(g.multiplex.nodes))
}
// Nodes returns all the nodes in the graph.
@@ -473,13 +473,13 @@ func (g undirectedLayerHandle) From(u graph.Node) []graph.Node {
func (g undirectedLayerHandle) HasEdgeBetween(x, y graph.Node) bool {
xid := x.ID()
yid := y.ID()
- if xid == yid {
+ if xid == yid || !isValidID(xid) || !isValidID(yid) {
return false
}
if xid > yid {
xid, yid = yid, xid
}
- _, ok := g.multiplex.layers[g.layer].weights[[2]int{xid, yid}]
+ _, ok := g.multiplex.layers[g.layer].weights[[2]int{int(xid), int(yid)}]
return ok
}
@@ -488,10 +488,13 @@ func (g undirectedLayerHandle) HasEdgeBetween(x, y graph.Node) bool {
func (g undirectedLayerHandle) Edge(u, v graph.Node) graph.Edge {
uid := u.ID()
vid := v.ID()
+ if uid == vid || !isValidID(uid) || !isValidID(vid) {
+ return nil
+ }
if vid < uid {
uid, vid = vid, uid
}
- w, ok := g.multiplex.layers[g.layer].weights[[2]int{uid, vid}]
+ w, ok := g.multiplex.layers[g.layer].weights[[2]int{int(uid), int(vid)}]
if !ok {
return nil
}
@@ -510,13 +513,16 @@ func (g undirectedLayerHandle) EdgeBetween(x, y graph.Node) graph.Edge {
func (g undirectedLayerHandle) Weight(x, y graph.Node) (w float64, ok bool) {
xid := x.ID()
yid := y.ID()
+ if !isValidID(xid) || !isValidID(yid) {
+ return 0, false
+ }
if xid == yid {
return g.multiplex.nodes[xid].weights[g.layer], true
}
if xid > yid {
xid, yid = yid, xid
}
- w, ok = g.multiplex.layers[g.layer].weights[[2]int{xid, yid}]
+ w, ok = g.multiplex.layers[g.layer].weights[[2]int{int(xid), int(yid)}]
return w, ok
}

MODIFY
graph/community/louvain_undirected_multiplex_test.go
graph/community/louvain_undirected_multiplex_test.go
@@ -295,10 +295,11 @@ tests:
rnd := rand.New(rand.NewSource(1)).Intn
for _, structure := range test.structures {
- communityOf := make(map[int]int)
+ communityOf := make(map[int64]int)
communities := make([][]graph.Node, len(structure.memberships))
for i, c := range structure.memberships {
for n := range c {
+ n := int64(n)
communityOf[n] = i
communities[i] = append(communities[i], simple.Node(n))
}
@@ -334,6 +335,7 @@ tests:
migrated := make([][]graph.Node, len(structure.memberships))
for i, c := range structure.memberships {
for n := range c {
+ n := int64(n)
if n == target.ID() {
continue
}

MODIFY
graph/community/louvain_undirected_test.go
graph/community/louvain_undirected_test.go
@@ -303,10 +303,11 @@ tests:
rnd := rand.New(rand.NewSource(1)).Intn
for _, structure := range test.structures {
- communityOf := make(map[int]int)
+ communityOf := make(map[int64]int)
communities := make([][]graph.Node, len(structure.memberships))
for i, c := range structure.memberships {
for n := range c {
+ n := int64(n)
communityOf[n] = i
communities[i] = append(communities[i], simple.Node(n))
}
@@ -336,6 +337,7 @@ tests:
migrated := make([][]graph.Node, len(structure.memberships))
for i, c := range structure.memberships {
for n := range c {
+ n := int64(n)
if n == target.ID() {
continue
}

graph/community: update for int64 IDs

The internal representation of reduced graphs remains based around int
IDs since the operations must happen in memory, and there is an initial
ID densification step to get from the target graph to the communities.