graph,graph/simple: add weighted graph interfaces and implementations
MODIFY
graph/graph.go
graph/graph.go
@@ -18,6 +18,11 @@ type Edge interface {
Weight() float64
}
+// WeightedEdge is a graph edge. In directed graphs, the direction
+// of the edge is given from -> to, otherwise the edge is semantically
+// unordered.
+type WeightedEdge Edge
+
// Graph is a generalized graph.
type Graph interface {
// Has returns whether the node exists within the graph.
@@ -40,6 +45,17 @@ type Graph interface {
Edge(u, v Node) Edge
}
+// WeightedGraph is a weighted graph.
+type WeightedGraph interface {
+ Graph
+
+ // 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
+}
+
// Undirected is an undirected graph.
type Undirected interface {
Graph
@@ -48,6 +64,15 @@ type Undirected interface {
EdgeBetween(x, y Node) Edge
}
+// WeightedUndirected is a weighted undirected graph.
+type WeightedUndirected interface {
+ WeightedGraph
+
+ // WeightedEdgeBetween returns the edge between nodes
+ // x and y.
+ WeightedEdgeBetween(x, y Node) WeightedEdge
+}
+
// Directed is a directed graph.
type Directed interface {
Graph
@@ -61,6 +86,19 @@ type Directed interface {
To(Node) []Node
}
+// WeightedDirected is a weighted directed graph.
+type WeightedDirected interface {
+ WeightedGraph
+
+ // HasEdgeFromTo returns whether an edge exists
+ // in the graph from u to v.
+ HasEdgeFromTo(u, v Node) bool
+
+ // To returns all nodes that can reach directly
+ // to the given node.
+ To(Node) []Node
+}
+
// Weighter defines graphs that can report edge weights.
type Weighter interface {
// Weight returns the weight for the edge between

MODIFY
graph/simple/dense_directed_matrix.go
graph/simple/dense_directed_matrix.go
@@ -174,6 +174,12 @@ func (g *DirectedMatrix) 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 *DirectedMatrix) 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 *DirectedMatrix) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
if g.HasEdgeFromTo(u, v) {
// 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()))}

MODIFY
graph/simple/dense_undirected_matrix.go
graph/simple/dense_undirected_matrix.go
@@ -150,11 +150,22 @@ func (g *UndirectedMatrix) HasEdgeBetween(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 *UndirectedMatrix) Edge(u, v graph.Node) graph.Edge {
- return g.EdgeBetween(u, v)
+ 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 *UndirectedMatrix) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
+ return g.WeightedEdgeBetween(u, v)
}
// EdgeBetween returns the edge between nodes x and y.
func (g *UndirectedMatrix) EdgeBetween(u, v graph.Node) graph.Edge {
+ return g.WeightedEdgeBetween(u, v)
+}
+
+// WeightedEdgeBetween returns the weighted edge between nodes x and y.
+func (g *UndirectedMatrix) WeightedEdgeBetween(u, v graph.Node) graph.WeightedEdge {
if g.HasEdgeBetween(u, v) {
// 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()))}

MODIFY
graph/simple/densegraph_test.go
graph/simple/densegraph_test.go
@@ -14,8 +14,17 @@ import (
)
var (
- _ graph.Graph = (*UndirectedMatrix)(nil)
- _ graph.Directed = (*DirectedMatrix)(nil)
+ directedMatrix = (*DirectedMatrix)(nil)
+
+ _ graph.Graph = directedMatrix
+ _ graph.Directed = directedMatrix
+ _ graph.WeightedDirected = directedMatrix
+
+ undirectedMatrix = (*UndirectedMatrix)(nil)
+
+ _ graph.Graph = undirectedMatrix
+ _ graph.Undirected = undirectedMatrix
+ _ graph.WeightedUndirected = undirectedMatrix
)
func TestBasicDenseImpassable(t *testing.T) {

MODIFY
graph/simple/directed.go
graph/simple/directed.go
@@ -213,6 +213,12 @@ func (g *DirectedGraph) 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 *DirectedGraph) 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 *DirectedGraph) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
if _, ok := g.nodes[u.ID()]; !ok {
return nil
}

MODIFY
graph/simple/directed_test.go
graph/simple/directed_test.go
@@ -11,9 +11,13 @@ import (
"gonum.org/v1/gonum/graph"
)
-var _ graph.Graph = &DirectedGraph{}
-var _ graph.Directed = &DirectedGraph{}
-var _ graph.Directed = &DirectedGraph{}
+var (
+ directedGraph = (*DirectedGraph)(nil)
+
+ _ graph.Graph = directedGraph
+ _ graph.Directed = directedGraph
+ _ graph.WeightedDirected = directedGraph
+)
// Tests Issue #27
func TestEdgeOvercounting(t *testing.T) {

MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -186,11 +186,22 @@ func (g *UndirectedGraph) 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 *UndirectedGraph) Edge(u, v graph.Node) graph.Edge {
- return g.EdgeBetween(u, v)
+ 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 *UndirectedGraph) WeightedEdge(u, v graph.Node) graph.WeightedEdge {
+ return g.WeightedEdgeBetween(u, v)
}
// EdgeBetween returns the edge between nodes x and y.
func (g *UndirectedGraph) EdgeBetween(x, y graph.Node) graph.Edge {
+ return g.WeightedEdgeBetween(x, y)
+}
+
+// WeightedEdgeBetween returns the weighted edge between nodes x and y.
+func (g *UndirectedGraph) WeightedEdgeBetween(x, y graph.Node) graph.WeightedEdge {
// We don't need to check if neigh exists because
// it's implicit in the edges access.
if !g.Has(x) {

MODIFY
graph/simple/undirected_test.go
graph/simple/undirected_test.go
@@ -11,7 +11,13 @@ import (
"gonum.org/v1/gonum/graph"
)
-var _ graph.Graph = (*UndirectedGraph)(nil)
+var (
+ undirectedGraph = (*UndirectedGraph)(nil)
+
+ _ graph.Graph = undirectedGraph
+ _ graph.Undirected = undirectedGraph
+ _ graph.WeightedUndirected = undirectedGraph
+)
func TestAssertMutableNotDirected(t *testing.T) {
var g graph.UndirectedBuilder = NewUndirectedGraph(0, math.Inf(1))

MODIFY
graph/undirect.go
graph/undirect.go
@@ -32,6 +32,7 @@ type Undirect struct {
var (
_ Undirected = Undirect{}
+ _ WeightedUndirected = Undirect{}
_ Weighter = Undirect{}
)
@@ -68,12 +69,26 @@ func (g Undirect) HasEdgeBetween(x, y Node) bool { return g.G.HasEdgeBetween(x,
// If an edge exists, the Edge returned is an EdgePair. The weight of
// the edge is determined by applying the Merge func to the weights of the
// edges between u and v.
-func (g Undirect) Edge(u, v Node) Edge { return g.EdgeBetween(u, v) }
+func (g Undirect) Edge(u, v Node) Edge { 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.
+// If an edge exists, the Edge returned is an EdgePair. The weight of
+// the edge is determined by applying the Merge func to the weights of the
+// edges between u and v.
+func (g Undirect) WeightedEdge(u, v Node) WeightedEdge { return g.WeightedEdgeBetween(u, v) }
// EdgeBetween returns the edge between nodes x and y. If an edge exists, the
// Edge returned is an EdgePair. The weight of the edge is determined by
// applying the Merge func to the weights of edges between x and y.
func (g Undirect) EdgeBetween(x, y Node) Edge {
+ return g.WeightedEdgeBetween(x, y)
+}
+
+// WeightedEdgeBetween returns the weighted edge between nodes x and y. If an edge exists, the
+// Edge returned is an EdgePair. The weight of the edge is determined by
+// applying the Merge func to the weights of edges between x and y.
+func (g Undirect) WeightedEdgeBetween(x, y Node) WeightedEdge {
fe := g.G.Edge(x, y)
re := g.G.Edge(y, x)
if fe == nil && re == nil {

graph,graph/simple: add weighted graph interfaces and implementations