Common — library colibrilib.negcycle — module NegCycle

Incremental detection of negative cycles in a graph of difference constraints.

The vertices are the integers of [0, n). An edge x --w--> y stands for the constraint pi y <= pi x + w on a potential pi. The graph has a potential satisfying all its edges if and only if it has no cycle of negative weight.

The caller keeps the edges (for example in backtrackable tables) and gives them as a function g: the edges out of x are the elements e of g x with e.src = x and e.dst in [0, n); the others are ignored. The potential is an array of length n that add_edge updates. When edges are removed (backtracking), the potential still satisfies the remaining ones, so nothing needs to be undone.

add_edge adds one edge e to a graph whose other edges are satisfied by the potential. It lowers the potential from e.dst, as a label–correcting shortest path search, until all edges are satisfied again, or it finds that the source of e would be lowered: then the new edge closes a negative cycle. Only the vertices whose potential changes are visited.

22
module NegCycle
23
24
use int.Int
25
use list.List
26
use list.Mem
27
use list.Append
28
use list.Length
29
use map.Map
30
use map.MapExt
31
use array.Array
32
use ref.Ref
33
34
type
edge
= {
src
: int;
dst
: int;
wt
: int }

a is an edge of the graph g with the extra edge e, over the vertices of [0, n)

38
predicate
gedge
(g: int -> list edge) (n: int) (e a: edge) =
39
0 <= a.src < n /\ 0 <= a.dst < n /\ (mem a (g a.src) \/ a = e)

The potential pi satisfies the edge a

42
predicate
sat
(pi: int -> int) (a: edge) = pi a.dst <= pi a.src + a.wt

p is a path from x to y

45
predicate
path
(g: int -> list edge) (n: int) (e: edge) (x: int)
46
(p: list edge) (y: int) =
47
match p with
48
| Nil -> x = y
49
| Cons a r -> gedge g n e a /\ a.src = x /\ path g n e a.dst r y
50
end
51
52
function
weight
(p: list edge) : int =
53
match p with
54
| Nil -> 0
55
| Cons a r -> a.wt + weight r
56
end

The graph has a cycle of negative weight

59
predicate
neg_cycle
(g: int -> list edge) (n: int) (e: edge) =
60
exists x p. path g n e x p x /\ weight p < 0
61
62
predicate
feasible
(g: int -> list edge) (n: int) (e: edge)
63
(pi: int -> int) =
64
forall a. gedge g n e a -> sat pi a
65
Valid (29ms) (colibri2)
66
let rec ghost
path_snoc
(g: int -> list edge) (n: int) (e: edge) (x: int)
67
(p: list edge) (y: int) (a: edge) : unit
68
requires { path g n e x p y }
69
requires { gedge g n e a }
70
requires { a.src = y }
71
ensures { path g n e x (p ++ Cons a Nil) a.dst }
72
ensures { weight (p ++ Cons a Nil) = weight p + a.wt }
73
variant { p }
74
= match p with
75
| Nil -> ()
76
| Cons b r -> path_snoc g n e b.dst r y a
77
end
78
Valid (31ms) (colibri2)
79
let rec ghost
path_bound
(g: int -> list edge) (n: int) (e: edge)
80
(pi: int -> int) (x: int) (p: list edge) (y: int) : unit
81
requires { feasible g n e pi }
82
requires { path g n e x p y }
83
ensures { pi y <= pi x + weight p }
84
variant { p }
85
= match p with
86
| Nil -> ()
87
| Cons b r -> path_bound g n e pi b.dst r y
88
end

A graph with a feasible potential has no negative cycle

  Valid (27ms) (colibri2)
91
let ghost
feasible_no_cycle
(g: int -> list edge) (n: int) (e: edge)
92
(pi: int -> int) : unit
93
requires { feasible g n e pi }
94
ensures { not neg_cycle g n e }
95
= let lemma cyc (x: int) (p: list edge)
96
requires { path g n e x p x }
97
ensures { weight p >= 0 }
98
= path_bound g n e pi x p x
99
in ()

How much f is below f0 on [a, b)

  Valid (16ms) (colibri2)
102
let rec ghost function
drop
(f0 f: int -> int) (a b: int) : int
103
variant { b - a }
104
= if b <= a then 0 else drop f0 f a (b - 1) + (f0 (b - 1) - f (b - 1))
105
Valid (31ms) (colibri2)
106
let rec ghost
drop_eq
(f0 f f': int -> int) (a b: int) : unit
107
requires { forall j. a <= j < b -> f j = f' j }
108
ensures { drop f0 f a b = drop f0 f' a b }
109
variant { b - a }
110
= if a < b then drop_eq f0 f f' a (b - 1)
111
Valid (26ms) (colibri2)
112
let rec ghost
drop_zero
(f0: int -> int) (a b: int) : unit
113
ensures { drop f0 f0 a b = 0 }
114
variant { b - a }
115
= if a < b then drop_zero f0 a (b - 1)
116
Valid (35ms) (colibri2)
117
let rec ghost
drop_set
(f0 f: int -> int) (a b i c: int) : unit
118
requires { a <= i < b }
119
ensures { drop f0 (Map.set f i c) a b = drop f0 f a b + (f i - c) }
120
variant { b - a }
121
= if i < b - 1 then drop_set f0 f a (b - 1) i c
122
else drop_eq f0 f (Map.set f i c) a (b - 1)
123
Valid (32ms) (colibri2)
124
let rec ghost
drop_bound
(f0 f: int -> int) (a b k: int) : unit
125
requires { a <= b }
126
ensures { (forall j. a <= j < b -> f0 j - f j <= k) ->
127
drop f0 f a b <= (b - a) * k }
128
variant { b - a }
129
= if a < b then begin
130
drop_bound f0 f a (b - 1) k;
131
assert { (b - a) * k = (b - 1 - a) * k + k }
132
end

Undoing the changes l (the most recent first) on f

135
function
restore
(l: list (int, int)) (f: int -> int) : int -> int =
136
match l with
137
| Nil -> f
138
| Cons (y, v) r -> restore r (Map.set f y v)
139
end
140
Valid (60ms) (cvc5)
141
let rec
undo
(pi: array int) (l: list (int, int)) (ghost pi0: int -> int)
142
: unit
143
requires { restore l pi.elts = pi0 }
144
requires { forall y v. mem (y, v) l -> 0 <= y < length pi }
145
ensures { pi.elts = pi0 }
146
variant { l }
147
= match l with
148
| Nil -> ()
149
| Cons (y, v) r -> pi[y] <- v; undo pi r pi0
150
end
151
152
exception
NegCycle

Add the edge e to the graph of the out–edges adj over [0, length pi), whose other edges are satisfied by pi: lower the potential from e.dst until all the edges are satisfied. NegCycle: the graph with e has a negative cycle; the potential is unchanged.

  Valid (1.9s) (colibri2 106) (cvc4 4) (cvc5 3) (split_vc 6) (depth 4)
159
let
lower
(adj: array (list edge)) (pi: array int) (e: edge) : unit
160
requires { length adj = length pi }
161
requires { forall a. gedge adj.elts (length pi) e a -> a <> e ->
162
sat pi.elts a }
163
ensures { feasible adj.elts (length pi) e pi.elts }
164
raises { NegCycle -> neg_cycle adj.elts (length pi) e /\
165
pi.elts = old pi.elts }
166
= let n = length pi in
167
let u = e.src in
168
let v = e.dst in
169
if 0 <= u < n && 0 <= v < n then begin
170
let c0 = pi[u] + e.wt in
171
if c0 < pi[v] then begin
172
if u = v then begin
173
assert { path adj.elts n e u (Cons e Nil) u };
174
raise NegCycle
175
end;
176
let ghost pi0 = pure { pi.elts } in
177
let delta = c0 - pi[v] in
178
drop_zero pi0 0 n;
179
drop_set pi0 pi.elts 0 n v c0;
180
let ghost fuel = ref (n * (- delta) + delta) in
181
let l = ref (Cons (v, pi[v]) Nil) in
182
assert { Map.set (Map.set pi.elts v c0) v (pi[v]) == pi.elts };
183
pi[v] <- c0;
184
let ghost paths = ref (Map.set (pure { fun (_: int) -> (Nil: list edge) })
185
v (Cons e Nil)) in
186
assert { path adj.elts n e u (Cons e Nil) v };
187
let wl = ref (Cons v Nil) in
188
try
189
while (match !wl with Nil -> false | Cons _ _ -> true end) do
190
invariant { forall i. pi[i] <= pi0 i }
191
invariant { pi[u] = pi0 u }
192
invariant { forall i. pi[i] < pi0 i -> 0 <= i < n /\
193
path adj.elts n e u (!paths i) i /\
194
pi[i] = pi0 u + weight (!paths i) }
195
invariant { forall z. mem z !wl -> 0 <= z < n /\ z <> u /\
196
pi[z] < pi0 z }
197
invariant { forall a. gedge adj.elts n e a -> (sat pi0 a \/ a = e) ->
198
sat pi.elts a \/ mem a.src !wl }
199
invariant { 0 <= !fuel = n * (- delta) - drop pi0 pi.elts 0 n }
200
invariant { forall i. 0 <= i < n -> pi[i] >= pi0 i + delta }
201
invariant { restore !l pi.elts = pi0 }
202
invariant { forall y v. mem (y, v) !l -> 0 <= y < n }
203
variant { !fuel, Length.length !wl }
204
match !wl with
205
| Nil -> absurd
206
| Cons x r ->
207
assert { mem x !wl };
208
assert { 0 <= x < n };
209
wl := r;
210
let ghost fuel0 = !fuel in
211
let es = ref adj[x] in
212
while (match !es with Nil -> false | Cons _ _ -> true end) do
213
invariant { forall i. pi[i] <= pi0 i }
214
invariant { pi[u] = pi0 u }
215
invariant { forall i. pi[i] < pi0 i -> 0 <= i < n /\
216
path adj.elts n e u (!paths i) i /\
217
pi[i] = pi0 u + weight (!paths i) }
218
invariant { forall z. mem z !wl -> 0 <= z < n /\ z <> u /\
219
pi[z] < pi0 z }
220
invariant { pi[x] < pi0 x }
221
invariant { forall a. mem a !es -> mem a adj[x] }
222
invariant { forall a. gedge adj.elts n e a -> (sat pi0 a \/ a = e) ->
223
sat pi.elts a \/ mem a.src !wl \/
224
(a.src = x /\ mem a !es) }
225
invariant { 0 <= !fuel = n * (- delta) - drop pi0 pi.elts 0 n }
226
invariant { !fuel < fuel0 \/ (!fuel = fuel0 /\ !wl = r) }
227
invariant { forall i. 0 <= i < n ->
228
pi[i] >= pi0 i + delta }
229
invariant { restore !l pi.elts = pi0 }
230
invariant { forall y v. mem (y, v) !l -> 0 <= y < n }
231
variant { Length.length !es }
232
match !es with
233
| Nil -> absurd
234
| Cons a r' ->
235
es := r';
236
if a.src = x && 0 <= a.dst < n then begin
237
let y = a.dst in
238
let c = pi[x] + a.wt in
239
if c < pi[y] then begin
240
assert { gedge adj.elts n e a };
241
if y = u then begin
242
path_snoc adj.elts n e u (!paths x) x a;
243
raise NegCycle
244
end;
245
let d = pi[y] - c in
246
drop_set pi0 pi.elts 0 n y c;
247
drop_bound pi0 (Map.set pi.elts y c) 0 n (- delta);
248
assert { a <> e };
249
assert { d <= !fuel };
250
fuel := !fuel - d;
251
assert { Map.set (Map.set pi.elts y c) y (pi[y])
252
== pi.elts };
253
l := Cons (y, pi[y]) !l;
254
pi[y] <- c;
255
path_snoc adj.elts n e u (!paths x) x a;
256
paths := Map.set !paths y (!paths x ++ Cons a Nil);
257
wl := Cons y !wl
258
end
259
end
260
end
261
done
262
end
263
done
264
with
265
| NegCycle -> undo pi !l pi0; raise NegCycle
266
end
267
end
268
end
269
270
end