1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
// 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
}
|
