graph/simple: use lazy edge-based node iterator for From, To and Nodes methods
MODIFY
graph/path/negative_cycles_example_test.go
graph/path/negative_cycles_example_test.go
@@ -8,6 +8,7 @@ import (
"fmt"
"math"
+ "gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/path"
"gonum.org/v1/gonum/graph/simple"
)
@@ -33,9 +34,11 @@ func ExampleBellmanFordFrom_negativecycles() {
}
// Add a zero-cost path to all nodes from a new node Q.
- nodes := g.Nodes()
- for nodes.Next() {
- g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node('Q'), T: nodes.Node()})
+ // Since the graph is being mutated, we get a range over
+ // a slice of the graph's nodes rather than using the
+ // graph.Nodes iterator directly.
+ for _, n := range graph.NodesOf(g.Nodes()) {
+ g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node('Q'), T: n})
}
// Find the shortest path to each node from Q.

MODIFY
graph/simple/directed.go
graph/simple/directed.go
@@ -77,21 +77,14 @@ func (g *DirectedGraph) Edges() graph.Edges {
}
// From returns all nodes in g that can be reached directly from n.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *DirectedGraph) From(id int64) graph.Nodes {
- if _, ok := g.from[id]; !ok {
+ if len(g.from[id]) == 0 {
return graph.Empty
}
-
- from := make([]graph.Node, len(g.from[id]))
- i := 0
- for vid := range g.from[id] {
- from[i] = g.nodes[vid]
- i++
- }
- if len(from) == 0 {
- return graph.Empty
- }
- return iterator.NewOrderedNodes(from)
+ return iterator.NewNodesByEdge(g.nodes, g.from[id])
}
// HasEdgeBetween returns whether an edge exists between nodes x and y without
@@ -136,17 +129,14 @@ func (g *DirectedGraph) Node(id int64) graph.Node {
}
// Nodes returns all the nodes in the graph.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *DirectedGraph) Nodes() graph.Nodes {
if len(g.nodes) == 0 {
return graph.Empty
}
- nodes := make([]graph.Node, len(g.nodes))
- i := 0
- for _, n := range g.nodes {
- nodes[i] = n
- i++
- }
- return iterator.NewOrderedNodes(nodes)
+ return iterator.NewNodes(g.nodes)
}
// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
@@ -223,19 +213,12 @@ func (g *DirectedGraph) SetEdge(e graph.Edge) {
}
// To returns all nodes in g that can reach directly to n.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *DirectedGraph) To(id int64) graph.Nodes {
- if _, ok := g.to[id]; !ok {
- return graph.Empty
- }
-
- to := make([]graph.Node, len(g.to[id]))
- i := 0
- for uid := range g.to[id] {
- to[i] = g.nodes[uid]
- i++
- }
- if len(to) == 0 {
+ if len(g.to[id]) == 0 {
return graph.Empty
}
- return iterator.NewOrderedNodes(to)
+ return iterator.NewNodesByEdge(g.nodes, g.to[id])
}

MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -94,21 +94,14 @@ func (g *UndirectedGraph) Edges() graph.Edges {
}
// From returns all nodes in g that can be reached directly from n.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *UndirectedGraph) From(id int64) graph.Nodes {
- if _, ok := g.nodes[id]; !ok {
+ if len(g.edges[id]) == 0 {
return graph.Empty
}
-
- nodes := make([]graph.Node, len(g.edges[id]))
- i := 0
- for from := range g.edges[id] {
- nodes[i] = g.nodes[from]
- i++
- }
- if len(nodes) == 0 {
- return graph.Empty
- }
- return iterator.NewOrderedNodes(nodes)
+ return iterator.NewNodesByEdge(g.nodes, g.edges[id])
}
// HasEdgeBetween returns whether an edge exists between nodes x and y.
@@ -141,17 +134,14 @@ func (g *UndirectedGraph) Node(id int64) graph.Node {
}
// Nodes returns all the nodes in the graph.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *UndirectedGraph) Nodes() graph.Nodes {
if len(g.nodes) == 0 {
return graph.Empty
}
- nodes := make([]graph.Node, len(g.nodes))
- i := 0
- for _, n := range g.nodes {
- nodes[i] = n
- i++
- }
- return iterator.NewOrderedNodes(nodes)
+ return iterator.NewNodes(g.nodes)
}
// RemoveEdge removes the edge with the given end IDs from the graph, leaving the terminal nodes.

MODIFY
graph/simple/weighted_directed.go
graph/simple/weighted_directed.go
@@ -81,21 +81,14 @@ func (g *WeightedDirectedGraph) Edges() graph.Edges {
}
// From returns all nodes in g that can be reached directly from n.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *WeightedDirectedGraph) From(id int64) graph.Nodes {
- if _, ok := g.from[id]; !ok {
+ if len(g.from[id]) == 0 {
return graph.Empty
}
-
- from := make([]graph.Node, len(g.from[id]))
- i := 0
- for vid := range g.from[id] {
- from[i] = g.nodes[vid]
- i++
- }
- if len(from) == 0 {
- return graph.Empty
- }
- return iterator.NewOrderedNodes(from)
+ return iterator.NewNodesByWeightedEdge(g.nodes, g.from[id])
}
// HasEdgeBetween returns whether an edge exists between nodes x and y without
@@ -140,17 +133,14 @@ func (g *WeightedDirectedGraph) Node(id int64) graph.Node {
}
// Nodes returns all the nodes in the graph.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *WeightedDirectedGraph) Nodes() graph.Nodes {
if len(g.nodes) == 0 {
return graph.Empty
}
- nodes := make([]graph.Node, len(g.nodes))
- i := 0
- for _, n := range g.nodes {
- nodes[i] = n
- i++
- }
- return iterator.NewOrderedNodes(nodes)
+ return iterator.NewNodes(g.nodes)
}
// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
@@ -227,21 +217,14 @@ func (g *WeightedDirectedGraph) SetWeightedEdge(e graph.WeightedEdge) {
}
// To returns all nodes in g that can reach directly to n.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *WeightedDirectedGraph) To(id int64) graph.Nodes {
- if _, ok := g.to[id]; !ok {
- return graph.Empty
- }
-
- to := make([]graph.Node, len(g.to[id]))
- i := 0
- for uid := range g.to[id] {
- to[i] = g.nodes[uid]
- i++
- }
- if len(to) == 0 {
+ if len(g.to[id]) == 0 {
return graph.Empty
}
- return iterator.NewOrderedNodes(to)
+ return iterator.NewNodesByWeightedEdge(g.nodes, g.to[id])
}
// Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge.

MODIFY
graph/simple/weighted_undirected.go
graph/simple/weighted_undirected.go
@@ -96,20 +96,10 @@ func (g *WeightedUndirectedGraph) Edges() graph.Edges {
// From returns all nodes in g that can be reached directly from n.
func (g *WeightedUndirectedGraph) From(id int64) graph.Nodes {
- if _, ok := g.nodes[id]; !ok {
+ if len(g.edges[id]) == 0 {
return graph.Empty
}
-
- nodes := make([]graph.Node, len(g.edges[id]))
- i := 0
- for from := range g.edges[id] {
- nodes[i] = g.nodes[from]
- i++
- }
- if len(nodes) == 0 {
- return graph.Empty
- }
- return iterator.NewOrderedNodes(nodes)
+ return iterator.NewNodesByWeightedEdge(g.nodes, g.edges[id])
}
// HasEdgeBetween returns whether an edge exists between nodes x and y.
@@ -142,17 +132,14 @@ func (g *WeightedUndirectedGraph) Node(id int64) graph.Node {
}
// Nodes returns all the nodes in the graph.
+//
+// The returned graph.Nodes is only valid until the next mutation of
+// the receiver.
func (g *WeightedUndirectedGraph) Nodes() graph.Nodes {
if len(g.nodes) == 0 {
return graph.Empty
}
- nodes := make([]graph.Node, len(g.nodes))
- i := 0
- for _, n := range g.nodes {
- nodes[i] = n
- i++
- }
- return iterator.NewOrderedNodes(nodes)
+ return iterator.NewNodes(g.nodes)
}
// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal

graph/simple: use lazy edge-based node iterator for From, To and Nodes methods