graph/path: properly report negative cycles in Shortest.To
We still use the maxEdges condition to allow a better exploration of the graph
before terminating.
MODIFY
graph/path/bellman_ford_moore.go
graph/path/bellman_ford_moore.go
@@ -29,6 +29,7 @@ func BellmanFordFrom(u graph.Node, g graph.Graph) (path Shortest, ok bool) {
path = newShortestFrom(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

MODIFY
graph/path/bellman_ford_moore_test.go
graph/path/bellman_ford_moore_test.go
@@ -26,9 +26,7 @@ func TestBellmanFordFrom(t *testing.T) {
if ok {
t.Errorf("%q: expected negative cycle", test.Name)
}
- continue
- }
- if !ok {
+ } else if !ok {
t.Fatalf("%q: unexpected negative cycle", test.Name)
}
@@ -41,7 +39,7 @@ func TestBellmanFordFrom(t *testing.T) {
t.Errorf("%q: unexpected weight from To: got:%f want:%f",
test.Name, weight, test.Weight)
}
- if weight := pt.WeightTo(test.Query.To().ID()); 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)
}

MODIFY
graph/path/internal/testgraphs/shortest.go
graph/path/internal/testgraphs/shortest.go
@@ -595,6 +595,12 @@ var ShortestPathTests = []struct {
HasNegativeCycle: true,
Query: simple.Edge{F: simple.Node(0), T: simple.Node(1)},
+ Weight: math.Inf(-1),
+ WantPaths: [][]int64{
+ {0, 1}, // One loop around negative cycle and no lead-in path.
+ },
+
+ NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)},
},
{
Name: "two path directed negative cycle",
@@ -610,6 +616,12 @@ var ShortestPathTests = []struct {
HasNegativeCycle: true,
Query: simple.Edge{F: simple.Node(0), T: simple.Node(3)},
+ Weight: math.Inf(-1),
+ WantPaths: [][]int64{
+ {1, 2, 1, 3}, // One loop around negative cycle and no lead-in path.
+ },
+
+ NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(6)},
},
{
Name: "two path directed off-path negative cycle",
@@ -630,6 +642,8 @@ var ShortestPathTests = []struct {
{0, 4},
},
HasUniquePath: true,
+
+ NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(6)},
},
{
Name: "two path directed diamond negative cycle",
@@ -645,6 +659,12 @@ var ShortestPathTests = []struct {
HasNegativeCycle: true,
Query: simple.Edge{F: simple.Node(0), T: simple.Node(3)},
+ Weight: math.Inf(-1),
+ WantPaths: [][]int64{
+ {1, 2, 1, 3}, // One loop around negative cycle and no lead-in path.
+ },
+
+ NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(6)},
},
{
Name: "wp graph negative", // http://en.wikipedia.org/w/index.php?title=Johnson%27s_algorithm&oldid=564595231

MODIFY
graph/path/shortest.go
graph/path/shortest.go
@@ -54,6 +54,12 @@ type Shortest struct {
// be set by the function that
// returned the Shortest 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 newShortestFrom(u graph.Node, nodes []graph.Node) Shortest {
@@ -103,6 +109,14 @@ func (p *Shortest) add(u graph.Node) int {
func (p Shortest) set(to int, weight float64, mid int) {
p.dist[to] = weight
p.next[to] = 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)
+ }
+ }
}
// From returns the starting node of the paths held by the Shortest.
@@ -120,7 +134,8 @@ func (p Shortest) WeightTo(vid int64) float64 {
// To returns a shortest path to v and the weight of the path. If the path
// to v includes a negative cycle, one pass through the cycle will be included
-// in path and weight will be returned as -Inf.
+// in path, but any path leading into the negative cycle will be lost, and
+// weight will be returned as -Inf.
func (p Shortest) To(vid int64) (path []graph.Node, weight float64) {
to, toOK := p.indexOf[vid]
if !toOK || math.IsInf(p.dist[to], 1) {
@@ -133,13 +148,16 @@ func (p Shortest) To(vid int64) (path []graph.Node, weight float64) {
seen := make(set.Ints)
seen.Add(from)
for to != from {
- if seen.Has(to) {
+ next := p.next[to]
+ if math.IsInf(p.cycCosts[[2]int{next, to}], -1) {
weight = math.Inf(-1)
+ }
+ if seen.Has(to) {
break
}
seen.Add(to)
- to = p.next[to]
- path = append(path, p.nodes[to])
+ path = append(path, p.nodes[next])
+ to = next
}
} else {
n := len(p.nodes)

graph/path: properly report negative cycles in Shortest.To

We still use the maxEdges condition to allow a better exploration of the graph
before terminating.