graph,graph/{network,path}: remove Weighter interface
MODIFY
graph/graph.go
graph/graph.go
@@ -48,13 +48,22 @@ 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
// be directly reachable from u as defined by the
// From method.
WeightedEdge(u, v Node) WeightedEdge
+
+ // 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 or there is no
+ // joining edge between the two nodes the weight
+ // value returned is implementation dependent.
+ // Weight returns true if an edge exists between
+ // x and y or if x and y have the same ID, false
+ // otherwise.
+ Weight(x, y Node) (w float64, ok bool)
}
// Undirected is an undirected graph.
@@ -100,19 +109,6 @@ type WeightedDirected interface {
To(Node) []Node
}
-// Weighter defines graphs that can report edge weights.
-type Weighter interface {
- // 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 or there is no
- // joining edge between the two nodes the weight
- // value returned is implementation dependent.
- // Weight returns true if an edge exists between
- // x and y or if x and y have the same ID, false
- // otherwise.
- Weight(x, y Node) (w float64, ok bool)
-}
-
// NodeAdder is an interface for adding arbitrary nodes to a graph.
type NodeAdder interface {
// NewNode returns a new Node with a unique

MODIFY
graph/network/betweenness.go
graph/network/betweenness.go
@@ -139,12 +139,6 @@ func brandes(g graph.Graph, accumulate func(s graph.Node, stack linear.NodeStack
}
}
-// WeightedGraph is a graph with edge weights.
-type WeightedGraph interface {
- graph.Graph
- graph.Weighter
-}
-
// BetweennessWeighted returns the non-zero betweenness centrality for nodes in the weighted
// graph g used to construct the given shortest paths.
//
@@ -152,7 +146,7 @@ type WeightedGraph interface {
//
// where \sigma_{st} and \sigma_{st}(v) are the number of shortest paths from s to t,
// and the subset of those paths containing v respectively.
-func BetweennessWeighted(g WeightedGraph, p path.AllShortest) map[int64]float64 {
+func BetweennessWeighted(g graph.WeightedGraph, p path.AllShortest) map[int64]float64 {
cb := make(map[int64]float64)
nodes := g.Nodes()
@@ -203,7 +197,7 @@ func BetweennessWeighted(g WeightedGraph, p path.AllShortest) map[int64]float64
//
// If g is undirected, edges are retained such that u.ID < v.ID where u and v are
// the nodes of e.
-func EdgeBetweennessWeighted(g WeightedGraph, p path.AllShortest) map[[2]int64]float64 {
+func EdgeBetweennessWeighted(g graph.WeightedGraph, p path.AllShortest) map[[2]int64]float64 {
cb := make(map[[2]int64]float64)
_, isUndirected := g.(graph.Undirected)

MODIFY
graph/path/a_star.go
graph/path/a_star.go
@@ -28,7 +28,7 @@ func AStar(s, t graph.Node, g graph.Graph, h Heuristic) (path Shortest, expanded
return Shortest{from: s}, 0
}
var weight Weighting
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
weight = wg.Weight
} else {
weight = UniformCost(g)

MODIFY
graph/path/bellman_ford_moore.go
graph/path/bellman_ford_moore.go
@@ -16,7 +16,7 @@ func BellmanFordFrom(u graph.Node, g graph.Graph) (path Shortest, ok bool) {
return Shortest{from: u}, true
}
var weight Weighting
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
weight = wg.Weight
} else {
weight = UniformCost(g)

MODIFY
graph/path/dijkstra.go
graph/path/dijkstra.go
@@ -20,7 +20,7 @@ func DijkstraFrom(u graph.Node, g graph.Graph) Shortest {
return Shortest{from: u}
}
var weight Weighting
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
weight = wg.Weight
} else {
weight = UniformCost(g)
@@ -83,7 +83,7 @@ func DijkstraAllPaths(g graph.Graph) (paths AllShortest) {
// result of the work in the paths parameter which is a reference type.
func dijkstraAllPaths(g graph.Graph, paths AllShortest) {
var weight Weighting
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
weight = wg.Weight
} else {
weight = UniformCost(g)

MODIFY
graph/path/dynamic/dstarlite.go
graph/path/dynamic/dstarlite.go
@@ -33,8 +33,8 @@ type DStarLite struct {
// WorldModel is a mutable weighted directed graph that returns nodes identified
// by id number.
type WorldModel interface {
- graph.DirectedBuilder
- graph.Weighter
+ graph.Builder
+ graph.WeightedDirected
Node(id int64) graph.Node
}
@@ -73,7 +73,7 @@ func NewDStarLite(s, t graph.Node, g graph.Graph, h path.Heuristic, m WorldModel
*/
d.last = d.s
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
d.weight = wg.Weight
} else {
d.weight = path.UniformCost(g)

MODIFY
graph/path/dynamic/dstarlite_test.go
graph/path/dynamic/dstarlite_test.go
@@ -652,13 +652,8 @@ func samePath(a, b []graph.Node) bool {
return true
}
-type weightedGraph interface {
- graph.Graph
- graph.Weighter
-}
-
// weightOf return the weight of the path in g.
-func weightOf(path []graph.Node, g weightedGraph) float64 {
+func weightOf(path []graph.Node, g graph.WeightedGraph) float64 {
var w float64
if len(path) > 1 {
for p, n := range path[1:] {
@@ -673,7 +668,7 @@ func weightOf(path []graph.Node, g weightedGraph) float64 {
}
// simpleEdgesOf returns the weighted edges in g corresponding to the given edges.
-func simpleEdgesOf(g weightedGraph, edges []graph.Edge) []simple.Edge {
+func simpleEdgesOf(g graph.WeightedGraph, edges []graph.Edge) []simple.Edge {
w := make([]simple.Edge, len(edges))
for i, e := range edges {
w[i].F = e.From()

MODIFY
graph/path/floydwarshall.go
graph/path/floydwarshall.go
@@ -13,7 +13,7 @@ import "gonum.org/v1/gonum/graph"
// The time complexity of FloydWarshall is O(|V|^3).
func FloydWarshall(g graph.Graph) (paths AllShortest, ok bool) {
var weight Weighting
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
weight = wg.Weight
} else {
weight = UniformCost(g)

MODIFY
graph/path/internal/grid.go
graph/path/internal/grid.go
@@ -201,11 +201,21 @@ func abs(i int) int {
// Edge returns the edge between u and v.
func (g *Grid) Edge(u, v graph.Node) graph.Edge {
- return g.EdgeBetween(u, v)
+ return g.WeightedEdgeBetween(u, v)
+}
+
+// WeightedEdge returns the weighted edge between u and v.
+func (g *Grid) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
+ return g.WeightedEdgeBetween(u, v)
}
// EdgeBetween returns the edge between u and v.
func (g *Grid) EdgeBetween(u, v graph.Node) graph.Edge {
+ return g.WeightedEdgeBetween(u, v)
+}
+
+// WeightedEdgeBetween returns the weighted edge between u and v.
+func (g *Grid) WeightedEdgeBetween(u, v graph.Node) graph.WeightedEdge {
if g.HasEdgeBetween(u, v) {
if !g.AllowDiagonal || g.UnitEdgeWeight {
return simple.Edge{F: u, T: v, W: 1}

MODIFY
graph/path/internal/limited.go
graph/path/internal/limited.go
@@ -217,11 +217,21 @@ func (l *LimitedVisionGrid) HasEdgeBetween(u, v graph.Node) bool {
// Edge optimistically returns the edge from u to v.
func (l *LimitedVisionGrid) Edge(u, v graph.Node) graph.Edge {
- return l.EdgeBetween(u, v)
+ return l.WeightedEdgeBetween(u, v)
}
-// EdgeBetween optimistically returns the edge between u and v.
+// Edge optimistically returns the weighted edge from u to v.
+func (l *LimitedVisionGrid) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
+ return l.WeightedEdgeBetween(u, v)
+}
+
+// WeightedEdgeBetween optimistically returns the edge between u and v.
func (l *LimitedVisionGrid) EdgeBetween(u, v graph.Node) graph.Edge {
+ return l.WeightedEdgeBetween(u, v)
+}
+
+// WeightedEdgeBetween optimistically returns the weighted edge between u and v.
+func (l *LimitedVisionGrid) WeightedEdgeBetween(u, v graph.Node) graph.WeightedEdge {
if l.HasEdgeBetween(u, v) {
if !l.Grid.AllowDiagonal || l.Grid.UnitEdgeWeight {
return simple.Edge{F: u, T: v, W: 1}

MODIFY
graph/path/internal/limited_test.go
graph/path/internal/limited_test.go
@@ -1197,7 +1197,7 @@ func TestLimitedVisionGrid(t *testing.T) {
}
}
-func asConcreteEdges(changes []graph.Edge, in graph.Weighter) []simple.Edge {
+func asConcreteEdges(changes []graph.Edge, in graph.WeightedGraph) []simple.Edge {
if changes == nil {
return nil
}

MODIFY
graph/path/johnson_apsp.go
graph/path/johnson_apsp.go
@@ -22,7 +22,7 @@ func JohnsonAllPaths(g graph.Graph) (paths AllShortest, ok bool) {
from: g.From,
edgeTo: g.Edge,
}
- if wg, ok := g.(graph.Weighter); ok {
+ if wg, ok := g.(graph.WeightedGraph); ok {
jg.weight = wg.Weight
} else {
jg.weight = UniformCost(g)
@@ -82,7 +82,7 @@ var (
// to be explicit with the type since it
// is not exported.
_ graph.Graph = johnsonWeightAdjuster{}
- _ graph.Weighter = johnsonWeightAdjuster{}
+ _ graph.WeightedGraph = johnsonWeightAdjuster{}
)
func (g johnsonWeightAdjuster) Has(n graph.Node) bool {
@@ -107,6 +107,10 @@ func (g johnsonWeightAdjuster) From(n graph.Node) []graph.Node {
return g.from(n)
}
+func (g johnsonWeightAdjuster) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
+ panic("path: unintended use of johnsonWeightAdjuster")
+}
+
func (g johnsonWeightAdjuster) Edge(u, v graph.Node) graph.Edge {
if g.bellmanFord && u.ID() == g.q && g.g.Has(v) {
return simple.Edge{F: johnsonGraphNode(g.q), T: v}

MODIFY
graph/undirect.go
graph/undirect.go
@@ -33,7 +33,6 @@ type Undirect struct {
var (
_ Undirected = Undirect{}
_ WeightedUndirected = Undirect{}
- _ Weighter = Undirect{}
)
// Has returns whether the node exists within the graph.
@@ -96,7 +95,7 @@ func (g Undirect) WeightedEdgeBetween(x, y Node) WeightedEdge {
}
var f, r float64
- if wg, ok := g.G.(Weighter); ok {
+ if wg, ok := g.G.(WeightedDirected); ok {
f, ok = wg.Weight(x, y)
if !ok {
f = g.Absent
@@ -134,7 +133,7 @@ func (g Undirect) Weight(x, y Node) (w float64, ok bool) {
re := g.G.Edge(y, x)
var f, r float64
- if wg, wOk := g.G.(Weighter); wOk {
+ if wg, wOk := g.G.(WeightedDirected); wOk {
var fOk, rOK bool
f, fOk = wg.Weight(x, y)
if !fOk {

graph,graph/{network,path}: remove Weighter interface