graph/path: fix negative cycle handling by AllShortest and FloydWarshall
Also remove unjustifiable claim in Bellman-Ford negative cycles example and add
Floyd-Warshall negative cycles example.
MODIFY
graph/path/floydwarshall.go
graph/path/floydwarshall.go
package path
-import "gonum.org/v1/gonum/graph"
+import (
+ "math"
+
+ "gonum.org/v1/gonum/graph"
+)
// FloydWarshall returns a shortest-path tree for the graph g or false indicating
-// that a negative cycle exists in the graph. If the graph does not implement
-// Weighted, UniformCost is used.
+// that a negative cycle exists in the graph. If a negative cycle exists in the graph
+// the returned paths will be valid and edge weights on the negative cycle will be
+// set to NaN. If the graph does not implement Weighted, UniformCost is used.
//
// The time complexity of FloydWarshall is O(|V|^3).
func FloydWarshall(g graph.Graph) (paths AllShortest, ok bool) {
@@ -58,5 +63,24 @@ func FloydWarshall(g graph.Graph) (paths AllShortest, ok bool) {
}
}
+ if !ok {
+ // If we have a negative cycle, mark all
+ // the edges in the cycles with NaN weight.
+ d := paths.dist
+ for i := range nodes {
+ for j := range nodes {
+ for k := range nodes {
+ if math.IsInf(d.At(i, k), 1) || math.IsInf(d.At(k, j), 1) {
+ continue
+ }
+ if d.At(k, k) < 0 || math.IsNaN(d.At(k, k)) {
+ d.Set(k, k, math.NaN())
+ d.Set(i, j, math.NaN())
+ }
+ }
+ }
+ }
+ }
+
return paths, ok
}

MODIFY
graph/path/johnson_apsp.go
graph/path/johnson_apsp.go
@@ -14,7 +14,8 @@ import (
)
// JohnsonAllPaths returns a shortest-path tree for shortest paths in the graph g.
-// If the graph does not implement Weighted, UniformCost is used.
+// If the graph does not implement Weighted, UniformCost is used. If a negative cycle
+// exists in g, ok will be returned false and paths will not contain valid data.
//
// The time complexity of JohnsonAllPaths is O(|V|.|E|+|V|^2.log|V|).
func JohnsonAllPaths(g graph.Graph) (paths AllShortest, ok bool) {

MODIFY
graph/path/negative_cycles_example_test.go
graph/path/negative_cycles_example_test.go
@@ -14,10 +14,7 @@ import (
func ExampleBellmanFordFrom_negativecycles() {
// BellmanFordFrom can be used to find a non-exhaustive
- // set of negative cycles in a graph. Enumerating the
- // exhaustive list requires iterations of the procedure
- // here successively omitting links from the new node
- // to already found negative cycles.
+ // set of negative cycles in a graph.
// Construct a graph with a negative cycle.
edges := []simple.WeightedEdge{
@@ -47,10 +44,10 @@ func ExampleBellmanFordFrom_negativecycles() {
fmt.Println("no negative cycle present")
return
}
- for _, n := range []simple.Node{'a', 'b', 'c', 'd', 'e', 'f'} {
- p, w := pt.To(n.ID())
+ for _, id := range []int64{'a', 'b', 'c', 'd', 'e', 'f'} {
+ p, w := pt.To(id)
if math.IsNaN(w) {
- fmt.Printf("negative cycle in path to %c path:%c\n", n, p)
+ fmt.Printf("negative cycle in path to %c path:%c\n", id, p)
}
}
@@ -60,3 +57,75 @@ func ExampleBellmanFordFrom_negativecycles() {
// negative cycle in path to c path:[c a b c]
// negative cycle in path to f path:[a b c a f]
}
+
+func ExampleFloydWarshall_negativecycles() {
+ // FloydWarshall can be used to find an exhaustive
+ // set of nodes in negative cycles in a graph.
+
+ // Construct a graph with a negative cycle.
+ edges := []simple.WeightedEdge{
+ {F: simple.Node('a'), T: simple.Node('f'), W: -1},
+ {F: simple.Node('b'), T: simple.Node('a'), W: 1},
+ {F: simple.Node('b'), T: simple.Node('c'), W: -1},
+ {F: simple.Node('b'), T: simple.Node('d'), W: 1},
+ {F: simple.Node('c'), T: simple.Node('b'), W: 0},
+ {F: simple.Node('e'), T: simple.Node('a'), W: 1},
+ {F: simple.Node('f'), T: simple.Node('e'), W: -1},
+ }
+ g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
+ for _, e := range edges {
+ g.SetWeightedEdge(e)
+ }
+
+ // Find the shortest path to each node from Q.
+ pt, ok := path.FloydWarshall(g)
+ if ok {
+ fmt.Println("no negative cycle present")
+ return
+ }
+
+ ids := []int64{'a', 'b', 'c', 'd', 'e', 'f'}
+
+ for _, id := range ids {
+ if math.IsNaN(pt.Weight(id, id)) {
+ fmt.Printf("%c is in a negative cycle\n", id)
+ }
+ }
+
+ for _, uid := range ids {
+ for _, vid := range ids {
+ _, w, unique := pt.Between(uid, vid)
+ if math.IsNaN(w) {
+ fmt.Printf("negative cycle in path from %c to %c unique=%t\n", uid, vid, unique)
+ }
+ }
+ }
+
+ // Output:
+ // a is in a negative cycle
+ // b is in a negative cycle
+ // c is in a negative cycle
+ // e is in a negative cycle
+ // f is in a negative cycle
+ // negative cycle in path from a to a unique=false
+ // negative cycle in path from a to e unique=false
+ // negative cycle in path from a to f unique=false
+ // negative cycle in path from b to a unique=false
+ // negative cycle in path from b to b unique=false
+ // negative cycle in path from b to c unique=false
+ // negative cycle in path from b to d unique=false
+ // negative cycle in path from b to e unique=false
+ // negative cycle in path from b to f unique=false
+ // negative cycle in path from c to a unique=false
+ // negative cycle in path from c to b unique=false
+ // negative cycle in path from c to c unique=false
+ // negative cycle in path from c to d unique=false
+ // negative cycle in path from c to e unique=false
+ // negative cycle in path from c to f unique=false
+ // negative cycle in path from e to a unique=false
+ // negative cycle in path from e to e unique=false
+ // negative cycle in path from e to f unique=false
+ // negative cycle in path from f to a unique=false
+ // negative cycle in path from f to e unique=false
+ // negative cycle in path from f to f unique=false
+}

MODIFY
graph/path/shortest.go
graph/path/shortest.go
@@ -252,7 +252,8 @@ func (p AllShortest) Weight(uid, vid int64) float64 {
// Between returns a shortest path from u 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.
+// be included, but unique will be returned false. If a negative cycle exists on the path
+// from u to v, path will be returned nil, weight will be NaN and unique will be false.
func (p AllShortest) Between(uid, vid int64) (path []graph.Node, weight float64, unique bool) {
from, fromOK := p.indexOf[uid]
to, toOK := p.indexOf[vid]
@@ -263,6 +264,11 @@ func (p AllShortest) Between(uid, vid int64) (path []graph.Node, weight float64,
return nil, math.Inf(1), false
}
+ weight = p.dist.At(from, to)
+ if math.IsNaN(weight) {
+ return nil, weight, false
+ }
+
seen := make([]int, len(p.nodes))
for i := range seen {
seen[i] = -1
@@ -277,7 +283,6 @@ func (p AllShortest) Between(uid, vid int64) (path []graph.Node, weight float64,
}
path = []graph.Node{n}
- weight = p.dist.At(from, to)
unique = true
var next int
@@ -308,7 +313,8 @@ func (p AllShortest) Between(uid, vid int64) (path []graph.Node, weight float64,
}
// AllBetween returns all shortest paths from u to v and the weight of the paths. Paths
-// containing zero-weight cycles are not returned.
+// 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 NaN.
func (p AllShortest) AllBetween(uid, vid int64) (paths [][]graph.Node, weight float64) {
from, fromOK := p.indexOf[uid]
to, toOK := p.indexOf[vid]
@@ -319,6 +325,11 @@ func (p AllShortest) AllBetween(uid, vid int64) (paths [][]graph.Node, weight fl
return nil, math.Inf(1)
}
+ weight = p.dist.At(from, to)
+ if math.IsNaN(weight) {
+ return nil, weight
+ }
+
var n graph.Node
if p.forward {
n = p.nodes[from]

graph/path: fix negative cycle handling by AllShortest and FloydWarshall

Also remove unjustifiable claim in Bellman-Ford negative cycles example and add
Floyd-Warshall negative cycles example.