graph/{internal,path,topo}: factor reverse function out into internal
MODIFY
graph/internal/ordered/sort.go
graph/internal/ordered/sort.go
@@ -67,3 +67,10 @@ type Int64s []int64
func (s Int64s) Len() int { return len(s) }
func (s Int64s) Less(i, j int) bool { return s[i] < s[j] }
func (s Int64s) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
+
+// Reverse reverses the order of nodes.
+func Reverse(nodes []graph.Node) {
+ for i, j := 0, len(nodes)-1; i < j; i, j = i+1, j-1 {
+ nodes[i], nodes[j] = nodes[j], nodes[i]
+ }
+}

MODIFY
graph/path/shortest.go
graph/path/shortest.go
@@ -9,6 +9,7 @@ import (
"math/rand"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/ordered"
"gonum.org/v1/gonum/mat"
)
@@ -101,7 +102,7 @@ func (p Shortest) To(v graph.Node) (path []graph.Node, weight float64) {
path = append(path, p.nodes[p.next[to]])
to = p.next[to]
}
- reverse(path)
+ ordered.Reverse(path)
return path, p.dist[p.indexOf[v.ID()]]
}
@@ -248,7 +249,7 @@ func (p AllShortest) Between(u, v graph.Node) (path []graph.Node, weight float64
}
}
if !p.forward {
- reverse(path)
+ ordered.Reverse(path)
}
return path, weight, unique
@@ -289,7 +290,7 @@ func (p AllShortest) allBetween(from, to int, seen []bool, path []graph.Node, pa
return paths
}
if !p.forward {
- reverse(path)
+ ordered.Reverse(path)
}
return append(paths, path)
}
@@ -311,9 +312,3 @@ func (p AllShortest) allBetween(from, to int, seen []bool, path []graph.Node, pa
}
return paths
}
-
-func reverse(p []graph.Node) {
- for i, j := 0, len(p)-1; i < j; i, j = i+1, j-1 {
- p[i], p[j] = p[j], p[i]
- }
-}

MODIFY
graph/topo/paton_cycles_test.go
graph/topo/paton_cycles_test.go
@@ -134,10 +134,7 @@ func canonicalise(c []graph.Node) []graph.Node {
c = append(c[idx:], c[:idx]...)
}
if c[len(c)-1].ID() < c[1].ID() {
- s := c[1:]
- for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
- s[i], s[j] = s[j], s[i]
- }
+ ordered.Reverse(c[1:])
}
return c
}

MODIFY
graph/topo/tarjan.go
graph/topo/tarjan.go
@@ -76,16 +76,10 @@ func sortedFrom(sccs [][]graph.Node, order func([]graph.Node)) ([]graph.Node, er
}
err = sc
}
- reverse(sorted)
+ ordered.Reverse(sorted)
return sorted, err
}
-func reverse(p []graph.Node) {
- for i, j := 0, len(p)-1; i < j; i, j = i+1, j-1 {
- p[i], p[j] = p[j], p[i]
- }
-}
-
// TarjanSCC returns the strongly connected components of the graph g using Tarjan's algorithm.
//
// A strongly connected component of a graph is a set of vertices where it's possible to reach any
@@ -106,12 +100,12 @@ func tarjanSCCstabilized(g graph.Directed, order func([]graph.Node)) [][]graph.N
succ = g.From
} else {
order(nodes)
- reverse(nodes)
+ ordered.Reverse(nodes)
succ = func(n graph.Node) []graph.Node {
to := g.From(n)
order(to)
- reverse(to)
+ ordered.Reverse(to)
return to
}
}

graph/{internal,path,topo}: factor reverse function out into internal