graph,graph/{community,path}: use weighted graph types
MODIFY
graph/community/louvain_common.go
graph/community/louvain_common.go
@@ -358,7 +358,7 @@ const (
// positiveWeightFuncFor returns a constructed weight function for the
// positively weighted g.
func positiveWeightFuncFor(g graph.Graph) func(x, y graph.Node) float64 {
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
return func(x, y graph.Node) float64 {
w, ok := wg.Weight(x, y)
if !ok {
@@ -386,7 +386,7 @@ func positiveWeightFuncFor(g graph.Graph) func(x, y graph.Node) float64 {
// negativeWeightFuncFor returns a constructed weight function for the
// negatively weighted g.
func negativeWeightFuncFor(g graph.Graph) func(x, y graph.Node) float64 {
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
return func(x, y graph.Node) float64 {
w, ok := wg.Weight(x, y)
if !ok {

MODIFY
graph/community/louvain_directed.go
graph/community/louvain_directed.go
@@ -111,9 +111,10 @@ type ReducedDirected struct {
}
var (
- _ graph.Directed = (*ReducedDirected)(nil)
- _ graph.Weighter = (*ReducedDirected)(nil)
- _ ReducedGraph = (*ReducedUndirected)(nil)
+ reducedDirected = (*ReducedDirected)(nil)
+
+ _ graph.WeightedDirected = reducedDirected
+ _ ReducedGraph = reducedDirected
)
// Communities returns the community memberships of the nodes in the
@@ -377,6 +378,12 @@ func (g *ReducedDirected) HasEdgeFromTo(u, v graph.Node) bool {
// 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 *ReducedDirected) Edge(u, v graph.Node) graph.Edge {
+ return g.WeightedEdge(u, v)
+}
+
+// WeightedEdge returns the weighted 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 *ReducedDirected) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
uid := u.ID()
vid := v.ID()
if uid == vid || !isValidID(uid) || !isValidID(vid) {

MODIFY
graph/community/louvain_directed_multiplex.go
graph/community/louvain_directed_multiplex.go
@@ -208,8 +208,7 @@ type ReducedDirectedMultiplex struct {
var (
_ DirectedMultiplex = (*ReducedDirectedMultiplex)(nil)
- _ graph.Directed = (*directedLayerHandle)(nil)
- _ graph.Weighter = (*directedLayerHandle)(nil)
+ _ graph.WeightedDirected = (*directedLayerHandle)(nil)
)
// Nodes returns all the nodes in the graph.
@@ -544,6 +543,12 @@ func (g directedLayerHandle) HasEdgeFromTo(u, v graph.Node) bool {
// 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 directedLayerHandle) Edge(u, v graph.Node) graph.Edge {
+ return g.WeightedEdge(u, v)
+}
+
+// WeightedEdge returns the weighted 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 directedLayerHandle) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
uid := u.ID()
vid := v.ID()
if uid == vid || !isValidID(uid) || !isValidID(vid) {
@@ -556,11 +561,6 @@ func (g directedLayerHandle) Edge(u, v graph.Node) graph.Edge {
return multiplexEdge{from: g.multiplex.nodes[u.ID()], to: g.multiplex.nodes[v.ID()], weight: w}
}
-// EdgeBetween returns the edge between nodes x and y.
-func (g directedLayerHandle) EdgeBetween(x, y graph.Node) graph.Edge {
- return g.Edge(x, y)
-}
-
// Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge.
// If x and y are the same node the internal node weight is returned. If there is no joining
// edge between the two nodes the weight value returned is zero. Weight returns true if an edge

MODIFY
graph/community/louvain_undirected.go
graph/community/louvain_undirected.go
@@ -111,9 +111,10 @@ type ReducedUndirected struct {
}
var (
- _ graph.Undirected = (*ReducedUndirected)(nil)
- _ graph.Weighter = (*ReducedUndirected)(nil)
- _ ReducedGraph = (*ReducedUndirected)(nil)
+ reducedUndirected = (*ReducedUndirected)(nil)
+
+ _ graph.WeightedUndirected = reducedUndirected
+ _ ReducedGraph = reducedUndirected
)
// Communities returns the community memberships of the nodes in the
@@ -324,24 +325,35 @@ func (g *ReducedUndirected) HasEdgeBetween(x, y graph.Node) bool {
// 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 *ReducedUndirected) Edge(u, v graph.Node) graph.Edge {
- uid := u.ID()
- vid := v.ID()
- if uid == vid || !isValidID(uid) || !isValidID(vid) {
+ return g.WeightedEdgeBetween(u, v)
+}
+
+// WeightedEdge returns the weighted 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 *ReducedUndirected) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
+ return g.WeightedEdgeBetween(u, v)
+}
+
+// EdgeBetween returns the edge between nodes x and y.
+func (g *ReducedUndirected) EdgeBetween(x, y graph.Node) graph.Edge {
+ return g.WeightedEdgeBetween(x, y)
+}
+
+// WeightedEdgeBetween returns the weighted edge between nodes x and y.
+func (g *ReducedUndirected) WeightedEdgeBetween(x, y graph.Node) graph.WeightedEdge {
+ xid := x.ID()
+ yid := y.ID()
+ if xid == yid || !isValidID(xid) || !isValidID(yid) {
return nil
}
- if vid < uid {
- uid, vid = vid, uid
+ if yid < xid {
+ xid, yid = yid, xid
}
- w, ok := g.weights[[2]int{int(uid), int(vid)}]
+ w, ok := g.weights[[2]int{int(xid), int(yid)}]
if !ok {
return nil
}
- return edge{from: g.nodes[u.ID()], to: g.nodes[v.ID()], weight: w}
-}
-
-// EdgeBetween returns the edge between nodes x and y.
-func (g *ReducedUndirected) EdgeBetween(x, y graph.Node) graph.Edge {
- return g.Edge(x, y)
+ return edge{from: g.nodes[x.ID()], to: g.nodes[y.ID()], weight: w}
}
// Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge.

MODIFY
graph/community/louvain_undirected_multiplex.go
graph/community/louvain_undirected_multiplex.go
@@ -207,8 +207,7 @@ type ReducedUndirectedMultiplex struct {
var (
_ UndirectedMultiplex = (*ReducedUndirectedMultiplex)(nil)
- _ graph.Undirected = (*undirectedLayerHandle)(nil)
- _ graph.Weighter = (*undirectedLayerHandle)(nil)
+ _ graph.WeightedUndirected = (*undirectedLayerHandle)(nil)
)
// Nodes returns all the nodes in the graph.
@@ -486,24 +485,35 @@ func (g undirectedLayerHandle) HasEdgeBetween(x, y graph.Node) bool {
// 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 undirectedLayerHandle) Edge(u, v graph.Node) graph.Edge {
- uid := u.ID()
- vid := v.ID()
- if uid == vid || !isValidID(uid) || !isValidID(vid) {
+ return g.WeightedEdgeBetween(u, v)
+}
+
+// WeightedEdge returns the weighted 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 undirectedLayerHandle) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
+ return g.WeightedEdgeBetween(u, v)
+}
+
+// EdgeBetween returns the edge between nodes x and y.
+func (g undirectedLayerHandle) EdgeBetween(x, y graph.Node) graph.Edge {
+ return g.WeightedEdgeBetween(x, y)
+}
+
+// WeightedEdgeBetween returns the weighted edge between nodes x and y.
+func (g undirectedLayerHandle) WeightedEdgeBetween(x, y graph.Node) graph.WeightedEdge {
+ xid := x.ID()
+ yid := y.ID()
+ if xid == yid || !isValidID(xid) || !isValidID(yid) {
return nil
}
- if vid < uid {
- uid, vid = vid, uid
+ if yid < xid {
+ xid, yid = yid, xid
}
- w, ok := g.multiplex.layers[g.layer].weights[[2]int{int(uid), int(vid)}]
+ w, ok := g.multiplex.layers[g.layer].weights[[2]int{int(xid), int(yid)}]
if !ok {
return nil
}
- return multiplexEdge{from: g.multiplex.nodes[u.ID()], to: g.multiplex.nodes[v.ID()], weight: w}
-}
-
-// EdgeBetween returns the edge between nodes x and y.
-func (g undirectedLayerHandle) EdgeBetween(x, y graph.Node) graph.Edge {
- return g.Edge(x, y)
+ return multiplexEdge{from: g.multiplex.nodes[x.ID()], to: g.multiplex.nodes[y.ID()], weight: w}
}
// Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge.

MODIFY
graph/graph.go
graph/graph.go
@@ -48,6 +48,7 @@ type Graph interface {
// WeightedGraph is a weighted graph.
type WeightedGraph interface {
Graph
+ Weighter
// WeightedEdge returns the weighted edge from u to v if
// such an edge exists and nil otherwise. The node v must

MODIFY
graph/path/spanning_tree.go
graph/path/spanning_tree.go
@@ -13,19 +13,13 @@ import (
"gonum.org/v1/gonum/graph/simple"
)
-// UndirectedWeighter is an undirected graph that returns edge weights.
-type UndirectedWeighter interface {
- graph.Undirected
- graph.Weighter
-}
-
// Prim generates a minimum spanning tree of g by greedy tree extension, placing
// the result in the destination, dst. If the edge weights of g are distinct
// it will be the unique minimum spanning tree of g. The destination is not cleared
// first. The weight of the minimum spanning tree is returned. If g is not connected,
// a minimum spanning forest will be constructed in dst and the sum of minimum
// spanning tree weights will be returned.
-func Prim(dst graph.UndirectedBuilder, g UndirectedWeighter) float64 {
+func Prim(dst graph.UndirectedBuilder, g graph.WeightedUndirected) float64 {
nodes := g.Nodes()
if len(nodes) == 0 {
return 0
@@ -135,7 +129,7 @@ func (q *primQueue) update(u, v graph.Node, key float64) {
// UndirectedWeightLister is an undirected graph that returns edge weights and
// the set of edges in the graph.
type UndirectedWeightLister interface {
- UndirectedWeighter
+ graph.WeightedUndirected
Edges() []graph.Edge
}

MODIFY
graph/path/spanning_tree_test.go
graph/path/spanning_tree_test.go
@@ -26,8 +26,8 @@ func init() {
}
type spanningGraph interface {
- graph.UndirectedBuilder
- graph.Weighter
+ graph.Builder
+ graph.WeightedUndirected
Edges() []graph.Edge
}

graph,graph/{community,path}: use weighted graph types