graph/path: add option to retain all paths from single-source path finding routines
MODIFY
graph/path/bellman_ford_moore.go
graph/path/bellman_ford_moore.go
@@ -81,6 +81,78 @@ func BellmanFordFrom(u graph.Node, g graph.Graph) (path Shortest, ok bool) {
return path, true
}
+// BellmanFordAllFrom returns a shortest-path tree for shortest paths from u to all nodes in
+// the graph g, or false indicating that a negative cycle exists in the graph. If the graph
+// does not implement Weighted, UniformCost is used.
+//
+// The time complexity of BellmanFordAllFrom is O(|V|.|E|).
+func BellmanFordAllFrom(u graph.Node, g graph.Graph) (path ShortestAlts, ok bool) {
+ if g.Node(u.ID()) == nil {
+ return ShortestAlts{from: u}, true
+ }
+ var weight Weighting
+ if wg, ok := g.(Weighted); ok {
+ weight = wg.Weight
+ } else {
+ weight = UniformCost(g)
+ }
+
+ nodes := graph.NodesOf(g.Nodes())
+
+ path = newShortestAltsFrom(u, nodes)
+ path.dist[path.indexOf[u.ID()]] = 0
+ path.cycCosts = make(map[[2]int]float64)
+
+ // Queue to keep track which nodes need to be relaxed.
+ // Only nodes whose vertex distance changed in the previous iterations
+ // need to be relaxed again.
+ queue := newBellmanFordQueue(path.indexOf)
+ queue.enqueue(u)
+
+ // The maximum number of edges in a graph is |V| * (|V|-1) which is also
+ // the worst case complexity.
+ // If the queue-loop has more iterations than the amount of maximum edges
+ // it indicates that we have a negative cycle.
+ maxEdges := len(nodes) * (len(nodes) - 1)
+ var loops int
+
+ // TODO(kortschak): Consider adding further optimisations
+ // from http://arxiv.org/abs/1111.5414.
+ for queue.len() != 0 {
+ u := queue.dequeue()
+ uid := u.ID()
+ j := path.indexOf[uid]
+
+ for _, v := range graph.NodesOf(g.From(uid)) {
+ vid := v.ID()
+ k := path.indexOf[vid]
+ w, ok := weight(uid, vid)
+ if !ok {
+ panic("bellman-ford: unexpected invalid weight")
+ }
+
+ joint := path.dist[j] + w
+ if joint < path.dist[k] {
+ path.set(k, joint, j)
+
+ if !queue.has(vid) {
+ queue.enqueue(v)
+ }
+ } else if joint == path.dist[k] {
+ path.addPath(k, j)
+ }
+ }
+
+ if loops > maxEdges {
+ path.hasNegativeCycle = true
+ return path, false
+ }
+ loops++
+ }
+
+ return path, true
+}
+
// bellmanFordQueue is a queue for the Queue-based Bellman-Ford algorithm.
type bellmanFordQueue struct {
// queue holds the nodes which need to be relaxed.

MODIFY
graph/path/bellman_ford_moore_test.go
graph/path/bellman_ford_moore_test.go
@@ -7,9 +7,11 @@ package path
import (
"math"
"reflect"
+ "sort"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/ordered"
"gonum.org/v1/gonum/graph/path/internal/testgraphs"
)
@@ -67,3 +69,97 @@ func TestBellmanFordFrom(t *testing.T) {
}
}
}
+
+func TestBellmanFordAllFrom(t *testing.T) {
+ t.Parallel()
+ for _, test := range testgraphs.ShortestPathTests {
+ g := test.Graph()
+ for _, e := range test.Edges {
+ g.SetWeightedEdge(e)
+ }
+
+ pt, ok := BellmanFordAllFrom(test.Query.From(), g.(graph.Graph))
+ if test.HasNegativeCycle {
+ if ok {
+ t.Errorf("%q: expected negative cycle", test.Name)
+ }
+ } else if !ok {
+ t.Fatalf("%q: unexpected negative cycle", test.Name)
+ }
+
+ if pt.From().ID() != test.Query.From().ID() {
+ t.Fatalf("%q: unexpected from node ID: got:%d want:%d", test.Name, pt.From().ID(), test.Query.From().ID())
+ }
+
+ // Test single path results.
+ p, weight, unique := pt.To(test.Query.To().ID())
+ if weight != test.Weight {
+ t.Errorf("%q: unexpected weight from To: got:%f want:%f",
+ test.Name, weight, test.Weight)
+ }
+ if weight := pt.WeightTo(test.Query.To().ID()); !math.IsInf(test.Weight, -1) && weight != test.Weight {
+ t.Errorf("%q: unexpected weight from Weight: got:%f want:%f",
+ test.Name, weight, test.Weight)
+ }
+
+ var gotPath []int64
+ for _, n := range p {
+ gotPath = append(gotPath, n.ID())
+ }
+ ok = len(gotPath) == 0 && len(test.WantPaths) == 0
+ for _, sp := range test.WantPaths {
+ if reflect.DeepEqual(gotPath, sp) {
+ ok = true
+ break
+ }
+ }
+ if !ok {
+ t.Errorf("%q: unexpected shortest path:\ngot: %v\nwant from:%v",
+ test.Name, p, test.WantPaths)
+ }
+ if unique != test.HasUniquePath {
+ t.Errorf("%q: unexpected uniqueness from To: got:%t want:%t (%d paths)",
+ test.Name, unique, test.HasUniquePath, len(test.WantPaths))
+ }
+
+ // Test multiple path results.
+ paths, weight := pt.AllTo(test.Query.To().ID())
+ if weight != test.Weight {
+ t.Errorf("%q: unexpected weight from AllTo: got:%f want:%f",
+ test.Name, weight, test.Weight)
+ }
+ if weight := pt.WeightTo(test.Query.To().ID()); !math.IsInf(test.Weight, -1) && weight != test.Weight {
+ t.Errorf("%q: unexpected weight from Weight: got:%f want:%f",
+ test.Name, weight, test.Weight)
+ }
+
+ var gotPaths [][]int64
+ if len(paths) != 0 {
+ gotPaths = make([][]int64, len(paths))
+ }
+ for i, p := range paths {
+ for _, v := range p {
+ gotPaths[i] = append(gotPaths[i], v.ID())
+ }
+ }
+ if test.HasNegativeCycleInPath {
+ if gotPaths != nil {
+ t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant: []",
+ test.Name, gotPaths)
+ }
+ } else {
+ sort.Sort(ordered.BySliceValues(gotPaths))
+ if !reflect.DeepEqual(gotPaths, test.WantPaths) {
+ t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
+ test.Name, gotPaths, test.WantPaths)
+ }
+ }
+
+ // Test absent paths.
+ np, weight, unique := pt.To(test.NoPathFor.To().ID())
+ if pt.From().ID() == test.NoPathFor.From().ID() && !(np == nil && math.IsInf(weight, 1) && !unique) {
+ t.Errorf("%q: unexpected path:\ngot: path=%v weight=%f unique=%t\nwant:path=<nil> weight=+Inf unique=false",
+ test.Name, np, weight, unique)
+ }
+ }
+}

MODIFY
graph/path/dijkstra.go
graph/path/dijkstra.go
@@ -84,6 +84,79 @@ func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
return path
}
+// DijkstraAllFrom returns a shortest-path tree for shortest paths from u to all nodes in
+// the graph g. If the graph does not implement Weighted, UniformCost is used.
+// DijkstraAllFrom will panic if g has a u-reachable negative edge weight.
+//
+// If g is a graph.Graph, all nodes of the graph will be stored in the shortest-path
+// tree, otherwise only nodes reachable from u will be stored.
+//
+// The time complexity of DijkstrAllFrom is O(|E|.log|V|).
+func DijkstraAllFrom(u graph.Node, g traverse.Graph) ShortestAlts {
+ var path ShortestAlts
+ if h, ok := g.(graph.Graph); ok {
+ if h.Node(u.ID()) == nil {
+ return ShortestAlts{from: u}
+ }
+ path = newShortestAltsFrom(u, graph.NodesOf(h.Nodes()))
+ } else {
+ if g.From(u.ID()) == nil {
+ return ShortestAlts{from: u}
+ }
+ path = newShortestAltsFrom(u, []graph.Node{u})
+ }
+
+ var weight Weighting
+ if wg, ok := g.(Weighted); ok {
+ weight = wg.Weight
+ } else {
+ weight = UniformCost(g)
+ }
+
+ // Dijkstra's algorithm here is implemented essentially as
+ // described in Function B.2 in figure 6 of UTCS Technical
+ // Report TR-07-54.
+ //
+ // This implementation deviates from the report as follows:
+ // - the value of path.dist for the start vertex u is initialized to 0;
+ // - outdated elements from the priority queue (i.e. with respect to the dist value)
+ // are skipped.
+ //
+ // http://www.cs.utexas.edu/ftp/techreports/tr07-54.pdf
+ Q := priorityQueue{{node: u, dist: 0}}
+ for Q.Len() != 0 {
+ mid := heap.Pop(&Q).(distanceNode)
+ k := path.indexOf[mid.node.ID()]
+ if mid.dist > path.dist[k] {
+ continue
+ }
+ mnid := mid.node.ID()
+ for _, v := range graph.NodesOf(g.From(mnid)) {
+ vid := v.ID()
+ j, ok := path.indexOf[vid]
+ if !ok {
+ j = path.add(v)
+ }
+ w, ok := weight(mnid, vid)
+ if !ok {
+ panic("dijkstra: unexpected invalid weight")
+ }
+ if w < 0 {
+ panic("dijkstra: negative edge weight")
+ }
+ joint := path.dist[k] + w
+ if joint < path.dist[j] {
+ heap.Push(&Q, distanceNode{node: v, dist: joint})
+ path.set(j, joint, k)
+ } else if joint == path.dist[j] {
+ path.addPath(j, k)
+ }
+ }
+ }
+
+ return path
+}
+
// DijkstraAllPaths returns a shortest-path tree for shortest paths in the graph g.
// If the graph does not implement graph.Weighter, UniformCost is used.
// DijkstraAllPaths will panic if g has a negative edge weight.

MODIFY
graph/path/dijkstra_test.go
graph/path/dijkstra_test.go
@@ -92,6 +92,113 @@ func TestDijkstraFrom(t *testing.T) {
}
}
+func TestDijkstraAllFrom(t *testing.T) {
+ t.Parallel()
+ for _, test := range testgraphs.ShortestPathTests {
+ g := test.Graph()
+ for _, e := range test.Edges {
+ g.SetWeightedEdge(e)
+ }
+
+ for _, tg := range []struct {
+ typ string
+ g traverse.Graph
+ }{
+ {"complete", g.(graph.Graph)},
+ {"incremental", incremental{g.(graph.Weighted)}},
+ } {
+ var (
+ pt ShortestAlts
+
+ panicked bool
+ )
+ func() {
+ defer func() {
+ panicked = recover() != nil
+ }()
+ pt = DijkstraAllFrom(test.Query.From(), tg.g)
+ }()
+ if panicked || test.HasNegativeWeight {
+ if !test.HasNegativeWeight {
+ t.Errorf("%q %s: unexpected panic", test.Name, tg.typ)
+ }
+ if !panicked {
+ t.Errorf("%q %s: expected panic for negative edge weight", test.Name, tg.typ)
+ }
+ continue
+ }
+
+ if pt.From().ID() != test.Query.From().ID() {
+ t.Fatalf("%q %s: unexpected from node ID: got:%d want:%d", test.Name, tg.typ, pt.From().ID(), test.Query.From().ID())
+ }
+
+ // Test single path results.
+ p, weight, unique := pt.To(test.Query.To().ID())
+ if weight != test.Weight {
+ t.Errorf("%q %s: unexpected weight from To: got:%f want:%f",
+ test.Name, tg.typ, weight, test.Weight)
+ }
+ if weight := pt.WeightTo(test.Query.To().ID()); weight != test.Weight {
+ t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
+ test.Name, tg.typ, weight, test.Weight)
+ }
+
+ var gotPath []int64
+ for _, n := range p {
+ gotPath = append(gotPath, n.ID())
+ }
+ ok := len(gotPath) == 0 && len(test.WantPaths) == 0
+ for _, sp := range test.WantPaths {
+ if reflect.DeepEqual(gotPath, sp) {
+ ok = true
+ break
+ }
+ }
+ if !ok {
+ t.Errorf("%q: unexpected shortest path:\ngot: %v\nwant from:%v",
+ test.Name, p, test.WantPaths)
+ }
+ if unique != test.HasUniquePath {
+ t.Errorf("%q: unexpected uniqueness from To: got:%t want:%t (%d paths)",
+ test.Name, unique, test.HasUniquePath, len(test.WantPaths))
+ }
+
+ // Test multiple path results.
+ paths, weight := pt.AllTo(test.Query.To().ID())
+ if weight != test.Weight {
+ t.Errorf("%q: unexpected weight from AllTo: got:%f want:%f",
+ test.Name, weight, test.Weight)
+ }
+ if weight := pt.WeightTo(test.Query.To().ID()); weight != test.Weight {
+ t.Errorf("%q: unexpected weight from Weight: got:%f want:%f",
+ test.Name, weight, test.Weight)
+ }
+
+ var gotPaths [][]int64
+ if len(paths) != 0 {
+ gotPaths = make([][]int64, len(paths))
+ }
+ for i, p := range paths {
+ for _, v := range p {
+ gotPaths[i] = append(gotPaths[i], v.ID())
+ }
+ }
+ sort.Sort(ordered.BySliceValues(gotPaths))
+ if !reflect.DeepEqual(gotPaths, test.WantPaths) {
+ t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
+ test.Name, gotPaths, test.WantPaths)
+ }
+
+ // Test absent paths.
+ np, weight, unique := pt.To(test.NoPathFor.To().ID())
+ if pt.From().ID() == test.NoPathFor.From().ID() && !(np == nil && math.IsInf(weight, 1) && !unique) {
+ t.Errorf("%q: unexpected path:\ngot: path=%v weight=%f unique=%t\nwant:path=<nil> weight=+Inf unique=false",
+ test.Name, np, weight, unique)
+ }
+ }
+ }
+}
+
type weightedTraverseGraph interface {
traverse.Graph
Weighted

MODIFY
graph/path/internal/testgraphs/shortest.go
graph/path/internal/testgraphs/shortest.go
@@ -20,6 +20,7 @@ var ShortestPathTests = []struct {
Edges []simple.WeightedEdge
HasNegativeWeight bool
HasNegativeCycle bool
+ HasNegativeCycleInPath bool
Query simple.Edge
Weight float64
@@ -595,6 +596,7 @@ var ShortestPathTests = []struct {
HasNegativeCycle: true,
Query: simple.Edge{F: simple.Node(0), T: simple.Node(1)},
+ HasNegativeCycleInPath: true,
Weight: math.Inf(-1),
WantPaths: [][]int64{
{0, 1}, // One loop around negative cycle and no lead-in path.
@@ -616,6 +618,7 @@ var ShortestPathTests = []struct {
HasNegativeCycle: true,
Query: simple.Edge{F: simple.Node(0), T: simple.Node(3)},
+ HasNegativeCycleInPath: true,
Weight: math.Inf(-1),
WantPaths: [][]int64{
{1, 2, 1, 3}, // One loop around negative cycle and no lead-in path.
@@ -637,6 +640,7 @@ var ShortestPathTests = []struct {
HasNegativeCycle: true,
Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)},
+ HasNegativeCycleInPath: false,
Weight: 10,
WantPaths: [][]int64{
{0, 4},
@@ -659,6 +663,7 @@ var ShortestPathTests = []struct {
HasNegativeCycle: true,
Query: simple.Edge{F: simple.Node(0), T: simple.Node(3)},
+ HasNegativeCycleInPath: true,
Weight: math.Inf(-1),
WantPaths: [][]int64{
{1, 2, 1, 3}, // One loop around negative cycle and no lead-in path.

MODIFY
graph/path/shortest.go
graph/path/shortest.go
@@ -174,6 +174,250 @@ func (p Shortest) To(vid int64) (path []graph.Node, weight float64) {
return path, math.Min(weight, p.dist[p.indexOf[vid]])
}
+// ShortestAlts is a shortest-path tree created by the BellmanFordAllFrom or DijkstraAllFrom
+// single-source shortest path functions.
+type ShortestAlts struct {
+ // from holds the source node given to
+ // the function that returned the
+ // ShortestAlts value.
+ from graph.Node
+
+ // nodes hold the nodes of the analysed
+ // graph.
+ nodes []graph.Node
+ // indexOf contains a mapping between
+ // the id-dense representation of the
+ // graph and the potentially id-sparse
+ // nodes held in nodes.
+ indexOf map[int64]int
+
+ // dist and next represent the shortest
+ // paths between nodes.
+ //
+ // Indices into dist and next are
+ // mapped through indexOf.
+ //
+ // dist contains the distances
+ // from the from node for each
+ // node in the graph.
+ dist []float64
+ // next contains the shortest-path
+ // tree of the graph. The index is a
+ // linear mapping of to-dense-id.
+ next [][]int
+
+ // hasNegativeCycle indicates
+ // whether the ShortestAlts includes
+ // a negative cycle. This should
+ // be set by the function that
+ // returned the ShortestAlts value.
+ hasNegativeCycle bool
+
+ // cycCosts holds costs between
+ // pairs of nodes to report negative
+ // cycles. cycCosts is only used
+ // if it is non-nil.
+ cycCosts map[[2]int]float64
+}
+
+func newShortestAltsFrom(u graph.Node, nodes []graph.Node) ShortestAlts {
+ indexOf := make(map[int64]int, len(nodes))
+ uid := u.ID()
+ for i, n := range nodes {
+ indexOf[n.ID()] = i
+ if n.ID() == uid {
+ u = n
+ }
+ }
+
+ p := ShortestAlts{
+ from: u,
+
+ nodes: nodes,
+ indexOf: indexOf,
+
+ dist: make([]float64, len(nodes)),
+ next: make([][]int, len(nodes)),
+ }
+ for i := range nodes {
+ p.dist[i] = math.Inf(1)
+ p.next[i] = nil
+ }
+ p.dist[indexOf[uid]] = 0
+
+ return p
+}
+
+// add adds a node to the ShortestAlts, initialising its stored index and returning, and
+// setting the distance and position as unconnected. add will panic if the node is
+// already present.
+func (p *ShortestAlts) add(u graph.Node) int {
+ uid := u.ID()
+ if _, exists := p.indexOf[uid]; exists {
+ panic("shortest: adding existing node")
+ }
+ idx := len(p.nodes)
+ p.indexOf[uid] = idx
+ p.nodes = append(p.nodes, u)
+ p.dist = append(p.dist, math.Inf(1))
+ p.next = append(p.next, nil)
+ return idx
+}
+
+func (p ShortestAlts) set(to int, weight float64, mid int) {
+ p.dist[to] = weight
+ p.next[to] = []int{mid}
+ if weight < 0 {
+ c, ok := p.cycCosts[[2]int{mid, to}]
+ if !ok {
+ p.cycCosts[[2]int{mid, to}] = weight
+ } else if weight < c {
+ p.cycCosts[[2]int{mid, to}] = math.Inf(-1)
+ }
+ }
+}
+
+func (p ShortestAlts) addPath(to, mid int) {
+ // These are likely to be rare, so just loop over collisions.
+ for _, v := range p.next[to] {
+ if mid == v {
+ return
+ }
+ }
+ p.next[to] = append(p.next[to], mid)
+}
+
+// From returns the starting node of the paths held by the ShortestAlts.
+func (p ShortestAlts) From() graph.Node { return p.from }
+
+// WeightTo returns the weight of the minimum path to v. If the path to v includes
+// a negative cycle, the returned weight will not reflect the true path weight.
+func (p ShortestAlts) WeightTo(vid int64) float64 {
+ to, toOK := p.indexOf[vid]
+ if !toOK {
+ return math.Inf(1)
+ }
+ return p.dist[to]
+}
+
+// To returns a shortest path to v and the weight of the path. If more than
+// one shortest path exists between u and v, a randomly chosen path will be
+// returned and unique is returned false. If a cycle with zero weight exists
+// in the path, it will not be included, but unique will be returned false.
+// If the path to v includes a negative cycle, one pass through the cycle will
+// be included in path, but any path leading into the negative cycle will be
+// lost, and weight will be returned as -Inf.
+func (p ShortestAlts) To(vid int64) (path []graph.Node, weight float64, unique bool) {
+ to, toOK := p.indexOf[vid]
+ if !toOK || math.IsInf(p.dist[to], 1) {
+ return nil, math.Inf(1), false
+ }
+ from := p.indexOf[p.from.ID()]
+ unique = true
+ path = []graph.Node{p.nodes[to]}
+ if p.hasNegativeCycle {
+ weight = math.Inf(1)
+ seen := make(set.Ints)
+ seen.Add(from)
+ for to != from {
+ c := p.next[to]
+ var next int
+ if len(c) != 1 {
+ unique = false
+ next = c[rand.Intn(len(c))]
+ } else {
+ next = c[0]
+ }
+ if math.IsInf(p.cycCosts[[2]int{next, to}], -1) {
+ weight = math.Inf(-1)
+ unique = false
+ }
+ if seen.Has(to) {
+ break
+ }
+ seen.Add(to)
+ path = append(path, p.nodes[next])
+ to = next
+ }
+ weight = math.Min(weight, p.dist[p.indexOf[vid]])
+ } else {
+ seen := make([]int, len(p.nodes))
+ for i := range seen {
+ seen[i] = -1
+ }
+ seen[to] = 0
+
+ var next int
+ for from != to {
+ c := p.next[to]
+ if len(c) != 1 {
+ unique = false
+ next = c[rand.Intn(len(c))]
+ } else {
+ next = c[0]
+ }
+ if seen[next] >= 0 {
+ path = path[:seen[next]]
+ }
+ seen[next] = len(path)
+ path = append(path, p.nodes[next])
+ to = next
+ }
+ weight = p.dist[p.indexOf[vid]]
+ }
+
+ ordered.Reverse(path)
+ return path, weight, unique
+}
+
+// AllTo returns all shortest paths to v and the weight of the paths. Paths
+// containing zero-weight cycles are not returned. If a negative cycle exists between
+// u and v, paths is returned nil and weight is returned as -Inf.
+func (p ShortestAlts) AllTo(vid int64) (paths [][]graph.Node, weight float64) {
+ from := p.indexOf[p.from.ID()]
+ to, toOK := p.indexOf[vid]
+ if !toOK || len(p.next[to]) == 0 {
+ if p.from.ID() == vid {
+ return [][]graph.Node{{p.nodes[from]}}, 0
+ }
+ return nil, math.Inf(1)
+ }
+
+ _, weight, unique := p.To(vid)
+ if math.IsInf(weight, -1) && !unique {
+ return nil, math.Inf(-1)
+ }
+
+ seen := make([]bool, len(p.nodes))
+ paths = p.allTo(from, to, seen, []graph.Node{p.nodes[to]}, nil)
+ weight = p.dist[to]
+
+ return paths, weight
+}
+
+func (p ShortestAlts) allTo(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
+ seen[to] = true
+ if from == to {
+ if path == nil {
+ return paths
+ }
+ ordered.Reverse(path)
+ return append(paths, path)
+ }
+ first := true
+ for _, to := range p.next[to] {
+ if seen[to] {
+ continue
+ }
+ if first {
+ path = append([]graph.Node(nil), path...)
+ first = false
+ }
+ paths = p.allTo(from, to, append([]bool(nil), seen...), append(path, p.nodes[to]), paths)
+ }
+ return paths
+}
+
// AllShortest is a shortest-path tree created by the DijkstraAllPaths, FloydWarshall
// or JohnsonAllPaths all-pairs shortest paths functions.
type AllShortest struct {

graph/path: add option to retain all paths from single-source path finding routines