blob: 31ba10d3af31ab4cc564b313172bdc568bf6000c [file] [log] [blame] [edit]
// Copyright ©2017 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package path_test
import (
"fmt"
"math"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/path"
"gonum.org/v1/gonum/graph/simple"
)
func ExampleBellmanFordFrom_negativecycles() {
// BellmanFordFrom can be used to find a non-exhaustive
// set of negative cycles in a graph.
// Construct a graph with a negative cycle.
edges := []simple.WeightedEdge{
{F: simple.Node('a'), T: simple.Node('b'), W: -2},
{F: simple.Node('a'), T: simple.Node('f'), W: 2},
{F: simple.Node('b'), T: simple.Node('c'), W: 6},
{F: simple.Node('c'), T: simple.Node('a'), W: -5},
{F: simple.Node('d'), T: simple.Node('c'), W: -3},
{F: simple.Node('d'), T: simple.Node('e'), W: 8},
{F: simple.Node('e'), T: simple.Node('b'), W: 9},
{F: simple.Node('e'), T: simple.Node('c'), W: 2},
}
g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
for _, e := range edges {
g.SetWeightedEdge(e)
}
// Add a zero-cost path to all nodes from a new node Q.
// Since the graph is being mutated, we get a range over
// a slice of the graph's nodes rather than using the
// graph.Nodes iterator directly.
for _, n := range graph.NodesOf(g.Nodes()) {
g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node('Q'), T: n})
}
// Find the shortest path to each node from Q.
pt, ok := path.BellmanFordFrom(simple.Node('Q'), g)
if ok {
fmt.Println("no negative cycle present")
return
}
for _, id := range []int64{'a', 'b', 'c', 'd', 'e', 'f'} {
p, w := pt.To(id)
if math.IsInf(w, -1) {
fmt.Printf("negative cycle in path to %c path:%c\n", id, p)
}
}
// Output:
// negative cycle in path to a path:[a b c a]
// negative cycle in path to b path:[b c a b]
// 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.IsInf(pt.Weight(id, id), -1) {
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.IsInf(w, -1) {
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
}