graph/multi: use lazy edge-based node iterator for From, To and Nodes methods
MODIFY
graph/multi/directed.go
graph/multi/directed.go
@@ -96,21 +96,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.NewNodesByLines(g.nodes, g.from[id])
}
// HasEdgeBetween returns whether an edge exists between nodes x and y without
@@ -169,17 +162,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)
}
// RemoveLine removes the line with the given end point and line IDs from the graph, leaving
@@ -267,19 +257,12 @@ func (g *DirectedGraph) SetLine(l graph.Line) {
}
// 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.NewNodesByLines(g.nodes, g.to[id])
}

MODIFY
graph/multi/undirected.go
graph/multi/undirected.go
@@ -105,21 +105,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.lines[id]) == 0 {
return graph.Empty
}
-
- nodes := make([]graph.Node, len(g.lines[id]))
- i := 0
- for from := range g.lines[id] {
- nodes[i] = g.nodes[from]
- i++
- }
- if len(nodes) == 0 {
- return graph.Empty
- }
- return iterator.NewOrderedNodes(nodes)
+ return iterator.NewNodesByLines(g.nodes, g.lines[id])
}
// HasEdgeBetween returns whether an edge exists between nodes x and y.
@@ -175,17 +168,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)
}
// RemoveLine removes the line with the given end point and line Ids from the graph, leaving

MODIFY
graph/multi/weighted_directed.go
graph/multi/weighted_directed.go
@@ -102,21 +102,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.NewNodesByWeightedLines(g.nodes, g.from[id])
}
// HasEdgeBetween returns whether an edge exists between nodes x and y without
@@ -177,18 +170,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)
}
// RemoveLine removes the line with the given end point and line IDs from the graph,
@@ -276,21 +265,14 @@ func (g *WeightedDirectedGraph) SetWeightedLine(l graph.WeightedLine) {
}
// 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.NewNodesByWeightedLines(g.nodes, g.to[id])
}
// Weight returns the weight for the lines between x and y summarised by the receiver's

MODIFY
graph/multi/weighted_undirected.go
graph/multi/weighted_undirected.go
@@ -111,21 +111,14 @@ func (g *WeightedUndirectedGraph) 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 *WeightedUndirectedGraph) From(id int64) graph.Nodes {
- if _, ok := g.nodes[id]; !ok {
+ if len(g.lines[id]) == 0 {
return graph.Empty
}
-
- nodes := make([]graph.Node, len(g.lines[id]))
- i := 0
- for from := range g.lines[id] {
- nodes[i] = g.nodes[from]
- i++
- }
- if len(nodes) == 0 {
- return graph.Empty
- }
- return iterator.NewOrderedNodes(nodes)
+ return iterator.NewNodesByWeightedLines(g.nodes, g.lines[id])
}
// HasEdgeBetween returns whether an edge exists between nodes x and y.
@@ -185,17 +178,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)
}
// RemoveLine removes the line with the given end point and line IDs from the graph,

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