graph: use iterators directly rather than copying into []graph.Node
There are still uses in test code; these can remain since they simplify
that code.
MODIFY
graph/flow/control_flow_lt.go
graph/flow/control_flow_lt.go
@@ -140,7 +140,9 @@ func (lt *lengauerTarjan) dfs(g graph.Directed, v graph.Node) {
ltv.label = ltv
lt.nodes = append(lt.nodes, ltv)
- for _, w := range graph.NodesOf(g.From(v.ID())) {
+ to := g.From(v.ID())
+ for to.Next() {
+ w := to.Node()
wid := w.ID()
idx, ok := lt.indexOf[wid]

MODIFY
graph/flow/control_flow_slt.go
graph/flow/control_flow_slt.go
@@ -162,7 +162,9 @@ func (lt *sLengauerTarjan) dfs(g graph.Directed, v graph.Node) {
ltv.label = ltv
lt.nodes = append(lt.nodes, ltv)
- for _, w := range graph.NodesOf(g.From(v.ID())) {
+ to := g.From(v.ID())
+ for to.Next() {
+ w := to.Node()
wid := w.ID()
idx, ok := lt.indexOf[wid]

MODIFY
graph/network/betweenness.go
graph/network/betweenness.go
@@ -117,7 +117,9 @@ func brandes(g graph.Graph, accumulate func(s graph.Node, stack linear.NodeStack
v := queue.Dequeue()
vid := v.ID()
stack.Push(v)
- for _, w := range graph.NodesOf(g.From(vid)) {
+ to := g.From(vid)
+ for to.Next() {
+ w := to.Node()
wid := w.ID()
// w found for the first time?
if d[wid] < 0 {

MODIFY
graph/network/hits.go
graph/network/hits.go
@@ -33,10 +33,14 @@ func HITS(g graph.Directed, tol float64) map[int64]HubAuthority {
nodesLinkedFrom := make([][]int, len(nodes))
for i, n := range nodes {
id := n.ID()
- for _, u := range graph.NodesOf(g.To(id)) {
+ from := g.To(id)
+ for from.Next() {
+ u := from.Node()
nodesLinkingTo[i] = append(nodesLinkingTo[i], indexOf[u.ID()])
}
- for _, v := range graph.NodesOf(g.From(id)) {
+ to := g.From(id)
+ for to.Next() {
+ v := to.Node()
nodesLinkedFrom[i] = append(nodesLinkedFrom[i], indexOf[v.ID()])
}
}

MODIFY
graph/path/a_star.go
graph/path/a_star.go
@@ -62,7 +62,9 @@ func AStar(s, t graph.Node, g traverse.Graph, h Heuristic) (path Shortest, expan
}
visited.Add(uid)
- for _, v := range graph.NodesOf(g.From(u.node.ID())) {
+ to := g.From(u.node.ID())
+ for to.Next() {
+ v := to.Node()
vid := v.ID()
if visited.Has(vid) {
continue

MODIFY
graph/path/bellman_ford_moore.go
graph/path/bellman_ford_moore.go
@@ -48,7 +48,9 @@ func BellmanFordFrom(u graph.Node, g graph.Graph) (path Shortest, ok bool) {
uid := u.ID()
j := path.indexOf[uid]
- for _, v := range graph.NodesOf(g.From(uid)) {
+ to := g.From(uid)
+ for to.Next() {
+ v := to.Node()
vid := v.ID()
k := path.indexOf[vid]
w, ok := weight(uid, vid)

MODIFY
graph/path/dijkstra.go
graph/path/dijkstra.go
@@ -58,7 +58,9 @@ func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
continue
}
mnid := mid.node.ID()
- for _, v := range graph.NodesOf(g.From(mnid)) {
+ to := g.From(mnid)
+ for to.Next() {
+ v := to.Node()
vid := v.ID()
j, ok := path.indexOf[vid]
if !ok {
@@ -123,7 +125,9 @@ func dijkstraAllPaths(g graph.Graph, paths AllShortest) {
paths.dist.Set(i, k, mid.dist)
}
mnid := mid.node.ID()
- for _, v := range graph.NodesOf(g.From(mnid)) {
+ to := g.From(mnid)
+ for to.Next() {
+ v := to.Node()
vid := v.ID()
j := paths.indexOf[vid]
w, ok := weight(mnid, vid)

MODIFY
graph/path/dynamic/dstarlite.go
graph/path/dynamic/dstarlite.go
@@ -87,7 +87,9 @@ func NewDStarLite(s, t graph.Node, g graph.Graph, h path.Heuristic, m WorldModel
d.queue.insert(d.t, key{d.heuristic(s, t), 0})
- for _, n := range graph.NodesOf(g.Nodes()) {
+ nodes := g.Nodes()
+ for nodes.Next() {
+ n := nodes.Node()
switch n.ID() {
case d.s.ID():
d.model.AddNode(d.s)
@@ -97,9 +99,13 @@ func NewDStarLite(s, t graph.Node, g graph.Graph, h path.Heuristic, m WorldModel
d.model.AddNode(newDStarLiteNode(n))
}
}
- for _, u := range graph.NodesOf(d.model.Nodes()) {
+ model := d.model.Nodes()
+ for model.Next() {
+ u := model.Node()
uid := u.ID()
- for _, v := range graph.NodesOf(g.From(uid)) {
+ to := g.From(uid)
+ for to.Next() {
+ v := to.Node()
vid := v.ID()
w := edgeWeight(d.weight, uid, vid)
if w < 0 {
@@ -195,8 +201,9 @@ func (d *DStarLite) findShortestPath() {
case u.g > u.rhs:
u.g = u.rhs
d.queue.remove(u)
- for _, _s := range graph.NodesOf(d.model.To(uid)) {
- s := _s.(*dStarLiteNode)
+ from := d.model.To(uid)
+ for from.Next() {
+ s := from.Node().(*dStarLiteNode)
sid := s.ID()
if sid != d.t.ID() {
s.rhs = math.Min(s.rhs, edgeWeight(d.model.Weight, sid, uid)+u.g)
@@ -212,7 +219,9 @@ func (d *DStarLite) findShortestPath() {
if s.rhs == edgeWeight(d.model.Weight, sid, uid)+gOld {
if s.ID() != d.t.ID() {
s.rhs = math.Inf(1)
- for _, t := range graph.NodesOf(d.model.From(sid)) {
+ to := d.model.From(sid)
+ for to.Next() {
+ t := to.Node()
tid := t.ID()
s.rhs = math.Min(s.rhs, edgeWeight(d.model.Weight, sid, tid)+t.(*dStarLiteNode).g)
}
@@ -249,8 +258,9 @@ func (d *DStarLite) Step() bool {
var next *dStarLiteNode
dsid := d.s.ID()
- for _, _s := range graph.NodesOf(d.model.From(dsid)) {
- s := _s.(*dStarLiteNode)
+ to := d.model.From(dsid)
+ for to.Next() {
+ s := to.Node().(*dStarLiteNode)
w := edgeWeight(d.model.Weight, dsid, s.ID()) + s.g
if w < min || (w == min && s.rhs < rhs) {
next = s
@@ -319,7 +329,9 @@ func (d *DStarLite) UpdateWorld(changes []graph.Edge) {
} else if u.rhs == cOld+v.g {
if uid != d.t.ID() {
u.rhs = math.Inf(1)
- for _, t := range graph.NodesOf(d.model.From(uid)) {
+ to := d.model.From(uid)
+ for to.Next() {
+ t := to.Node()
u.rhs = math.Min(u.rhs, edgeWeight(d.model.Weight, uid, t.ID())+t.(*dStarLiteNode).g)
}
}
@@ -364,8 +376,9 @@ func (d *DStarLite) Path() (p []graph.Node, weight float64) {
cost float64
)
uid := u.ID()
- for _, _v := range graph.NodesOf(d.model.From(uid)) {
- v := _v.(*dStarLiteNode)
+ to := d.model.From(uid)
+ for to.Next() {
+ v := to.Node().(*dStarLiteNode)
vid := v.ID()
w := edgeWeight(d.model.Weight, uid, vid)
if rhs := w + v.g; rhs < min || (rhs == min && v.rhs < rhsMin) {

MODIFY
graph/topo/johnson_cycles.go
graph/topo/johnson_cycles.go
@@ -145,7 +145,9 @@ func johnsonGraphFrom(g graph.Directed) johnsonGraph {
for i, u := range nodes {
uid := u.ID()
c.index[uid] = i
- for _, v := range graph.NodesOf(g.From(uid)) {
+ to := g.From(uid)
+ for to.Next() {
+ v := to.Node()
if c.succ[uid] == nil {
c.succ[uid] = make(set.Int64s)
c.nodes.Add(uid)

MODIFY
graph/topo/paton_cycles.go
graph/topo/paton_cycles.go
@@ -37,7 +37,9 @@ func UndirectedCyclesIn(g graph.Undirected) [][]graph.Node {
u := tree.Pop()
uid := u.ID()
adj := from[uid]
- for _, v := range graph.NodesOf(g.From(uid)) {
+ it := g.From(uid)
+ for it.Next() {
+ v := it.Node()
vid := v.ID()
switch {
case uid == vid:

graph: use iterators directly rather than copying into []graph.Node

There are still uses in test code; these can remain since they simplify
that code.