library colibrilib.negcycle — module NegCycleIncremental 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.
module NegCycle2223use int.Int24use list.List25use list.Mem26use list.Append27use list.Length28use map.Map29use map.MapExt30use array.Array31use ref.Ref3233type edge = { src: int; dst: int; wt: int }34
a is an edge of the graph g with the extra edge e, over the vertices of [0, n)
predicate gedge (g: int -> list edge) (n: int) (e a: edge) =380 <= a.src < n /\ 0 <= a.dst < n /\ (mem a (g a.src) \/ a = e)39
The potential pi satisfies the edge a
predicate sat (pi: int -> int) (a: edge) = pi a.dst <= pi a.src + a.wt42
p is a path from x to y
predicate path (g: int -> list edge) (n: int) (e: edge) (x: int)45(p: list edge) (y: int) =46match p with47| Nil -> x = y48| Cons a r -> gedge g n e a /\ a.src = x /\ path g n e a.dst r y49end5051function weight (p: list edge) : int =52match p with53| Nil -> 054| Cons a r -> a.wt + weight r55end56
The graph has a cycle of negative weight
predicate neg_cycle (g: int -> list edge) (n: int) (e: edge) =59exists x p. path g n e x p x /\ weight p < 06061predicate feasible (g: int -> list edge) (n: int) (e: edge)62(pi: int -> int) =63forall a. gedge g n e a -> sat pi a64Valid (29ms) (colibri2)65let rec ghost path_snoc (g: int -> list edge) (n: int) (e: edge) (x: int)66(p: list edge) (y: int) (a: edge) : unit67requires { path g n e x p y }68requires { gedge g n e a }69requires { a.src = y }70ensures { path g n e x (p ++ Cons a Nil) a.dst }71ensures { weight (p ++ Cons a Nil) = weight p + a.wt }72variant { p }73= match p with74| Nil -> ()75| Cons b r -> path_snoc g n e b.dst r y a76end77Valid (31ms) (colibri2)78let rec ghost path_bound (g: int -> list edge) (n: int) (e: edge)79(pi: int -> int) (x: int) (p: list edge) (y: int) : unit80requires { feasible g n e pi }81requires { path g n e x p y }82ensures { pi y <= pi x + weight p }83variant { p }84= match p with85| Nil -> ()86| Cons b r -> path_bound g n e pi b.dst r y87end88
A graph with a feasible potential has no negative cycle
Valid (27ms) (colibri2)let ghost feasible_no_cycle (g: int -> list edge) (n: int) (e: edge)91(pi: int -> int) : unit92requires { feasible g n e pi }93ensures { not neg_cycle g n e }94= let lemma cyc (x: int) (p: list edge)95requires { path g n e x p x }96ensures { weight p >= 0 }97= path_bound g n e pi x p x98in ()99
How much f is below f0 on [a, b)
Valid (16ms) (colibri2)let rec ghost function drop (f0 f: int -> int) (a b: int) : int102variant { b - a }103= if b <= a then 0 else drop f0 f a (b - 1) + (f0 (b - 1) - f (b - 1))104Valid (31ms) (colibri2)105let rec ghost drop_eq (f0 f f': int -> int) (a b: int) : unit106requires { forall j. a <= j < b -> f j = f' j }107ensures { drop f0 f a b = drop f0 f' a b }108variant { b - a }109= if a < b then drop_eq f0 f f' a (b - 1)110Valid (26ms) (colibri2)111let rec ghost drop_zero (f0: int -> int) (a b: int) : unit112ensures { drop f0 f0 a b = 0 }113variant { b - a }114= if a < b then drop_zero f0 a (b - 1)115Valid (35ms) (colibri2)116let rec ghost drop_set (f0 f: int -> int) (a b i c: int) : unit117requires { a <= i < b }118ensures { drop f0 (Map.set f i c) a b = drop f0 f a b + (f i - c) }119variant { b - a }120= if i < b - 1 then drop_set f0 f a (b - 1) i c121else drop_eq f0 f (Map.set f i c) a (b - 1)122Valid (32ms) (colibri2)123let rec ghost drop_bound (f0 f: int -> int) (a b k: int) : unit124requires { a <= b }125ensures { (forall j. a <= j < b -> f0 j - f j <= k) ->126drop f0 f a b <= (b - a) * k }127variant { b - a }128= if a < b then begin129drop_bound f0 f a (b - 1) k;130assert { (b - a) * k = (b - 1 - a) * k + k }131end132
Undoing the changes l (the most recent first) on f
function restore (l: list (int, int)) (f: int -> int) : int -> int =135match l with136| Nil -> f137| Cons (y, v) r -> restore r (Map.set f y v)138end139Valid (60ms) (cvc5)140let rec undo (pi: array int) (l: list (int, int)) (ghost pi0: int -> int)141: unit142requires { restore l pi.elts = pi0 }143requires { forall y v. mem (y, v) l -> 0 <= y < length pi }144ensures { pi.elts = pi0 }145variant { l }146= match l with147| Nil -> ()148| Cons (y, v) r -> pi[y] <- v; undo pi r pi0149end150151exception NegCycle152
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)let lower (adj: array (list edge)) (pi: array int) (e: edge) : unit159requires { length adj = length pi }160requires { forall a. gedge adj.elts (length pi) e a -> a <> e ->161sat pi.elts a }162ensures { feasible adj.elts (length pi) e pi.elts }163raises { NegCycle -> neg_cycle adj.elts (length pi) e /\164pi.elts = old pi.elts }165= let n = length pi in166let u = e.src in167let v = e.dst in168if 0 <= u < n && 0 <= v < n then begin169let c0 = pi[u] + e.wt in170if c0 < pi[v] then begin171if u = v then begin172assert { path adj.elts n e u (Cons e Nil) u };173raise NegCycle174end;175let ghost pi0 = pure { pi.elts } in176let delta = c0 - pi[v] in177drop_zero pi0 0 n;178drop_set pi0 pi.elts 0 n v c0;179let ghost fuel = ref (n * (- delta) + delta) in180let l = ref (Cons (v, pi[v]) Nil) in181assert { Map.set (Map.set pi.elts v c0) v (pi[v]) == pi.elts };182pi[v] <- c0;183let ghost paths = ref (Map.set (pure { fun (_: int) -> (Nil: list edge) })184v (Cons e Nil)) in185assert { path adj.elts n e u (Cons e Nil) v };186let wl = ref (Cons v Nil) in187try188while (match !wl with Nil -> false | Cons _ _ -> true end) do189invariant { forall i. pi[i] <= pi0 i }190invariant { pi[u] = pi0 u }191invariant { forall i. pi[i] < pi0 i -> 0 <= i < n /\192path adj.elts n e u (!paths i) i /\193pi[i] = pi0 u + weight (!paths i) }194invariant { forall z. mem z !wl -> 0 <= z < n /\ z <> u /\195pi[z] < pi0 z }196invariant { forall a. gedge adj.elts n e a -> (sat pi0 a \/ a = e) ->197sat pi.elts a \/ mem a.src !wl }198invariant { 0 <= !fuel = n * (- delta) - drop pi0 pi.elts 0 n }199invariant { forall i. 0 <= i < n -> pi[i] >= pi0 i + delta }200invariant { restore !l pi.elts = pi0 }201invariant { forall y v. mem (y, v) !l -> 0 <= y < n }202variant { !fuel, Length.length !wl }203match !wl with204| Nil -> absurd205| Cons x r ->206assert { mem x !wl };207assert { 0 <= x < n };208wl := r;209let ghost fuel0 = !fuel in210let es = ref adj[x] in211while (match !es with Nil -> false | Cons _ _ -> true end) do212invariant { forall i. pi[i] <= pi0 i }213invariant { pi[u] = pi0 u }214invariant { forall i. pi[i] < pi0 i -> 0 <= i < n /\215path adj.elts n e u (!paths i) i /\216pi[i] = pi0 u + weight (!paths i) }217invariant { forall z. mem z !wl -> 0 <= z < n /\ z <> u /\218pi[z] < pi0 z }219invariant { pi[x] < pi0 x }220invariant { forall a. mem a !es -> mem a adj[x] }221invariant { forall a. gedge adj.elts n e a -> (sat pi0 a \/ a = e) ->222sat pi.elts a \/ mem a.src !wl \/223(a.src = x /\ mem a !es) }224invariant { 0 <= !fuel = n * (- delta) - drop pi0 pi.elts 0 n }225invariant { !fuel < fuel0 \/ (!fuel = fuel0 /\ !wl = r) }226invariant { forall i. 0 <= i < n ->227pi[i] >= pi0 i + delta }228invariant { restore !l pi.elts = pi0 }229invariant { forall y v. mem (y, v) !l -> 0 <= y < n }230variant { Length.length !es }231match !es with232| Nil -> absurd233| Cons a r' ->234es := r';235if a.src = x && 0 <= a.dst < n then begin236let y = a.dst in237let c = pi[x] + a.wt in238if c < pi[y] then begin239assert { gedge adj.elts n e a };240if y = u then begin241path_snoc adj.elts n e u (!paths x) x a;242raise NegCycle243end;244let d = pi[y] - c in245drop_set pi0 pi.elts 0 n y c;246drop_bound pi0 (Map.set pi.elts y c) 0 n (- delta);247assert { a <> e };248assert { d <= !fuel };249fuel := !fuel - d;250assert { Map.set (Map.set pi.elts y c) y (pi[y])251== pi.elts };252l := Cons (y, pi[y]) !l;253pi[y] <- c;254path_snoc adj.elts n e u (!paths x) x a;255paths := Map.set !paths y (!paths x ++ Cons a Nil);256wl := Cons y !wl257end258end259end260done261end262done263with264| NegCycle -> undo pi !l pi0; raise NegCycle265end266end267end268269end270