library colibrilib.negcycle — module GraphA graph of difference constraints that keeps its edges on a trail, with a potential satisfying all of them.
The caller backtracks it by giving, at each addition, the length of the trail it expects (kept in a backtracked reference): the edges added after are removed first. Removing edges keeps the potential a solution.
module Graph279280use int.Int281use list.List282use list.Mem283use list.Append284use list.Length285use map.Map286use array.Array287use ref.Ref288use NegCycle289
The edges of l out of x, in the order of l
function outs (l: list edge) (x: int) : list edge =292match l with293| Nil -> Nil294| Cons a r -> if a.src = x then Cons a (outs r x) else outs r x295end296
The number of edges of l into x
function count_in (l: list edge) (x: int) : int =299match l with300| Nil -> 0301| Cons a r -> (if a.dst = x then 1 else 0) + count_in r x302end303304function outs_map (l: list edge) : int -> list edge = fun x -> outs l x305Valid (96ms) (colibri2)306let rec ghost outs_facts (l: list edge) : unit307ensures { forall x a. mem a (outs l x) <-> mem a l /\ a.src = x }308ensures { forall x. (forall a. mem a l -> a.src <> x) -> outs l x = Nil }309ensures { forall x. 0 <= count_in l x }310ensures { forall x. count_in l x = 0 <-> forall a. mem a l -> a.dst <> x }311variant { l }312= match l with Nil -> () | Cons _ r -> outs_facts r end313314let constant mk_dummy : edge = { src = 0; dst = 0; wt = 0 }315
tc is the suffix of l of length len
predicate cut (l: list edge) (len: int) (tc: list edge) =318Length.length tc = len /\ exists p. l = p ++ tc319Valid (19ms) (colibri2)320type t = {321mutable pi: array int;322mutable adj: array (list edge);323mutable indeg: array int;324mutable trail: list edge;325mutable len: int;326} invariant { length pi = length adj = length indeg }327invariant { len = Length.length trail }328invariant { forall a. mem a trail ->3290 <= a.src < length pi /\ 0 <= a.dst < length pi }330invariant { forall x. 0 <= x < length pi -> adj[x] = outs trail x }331invariant { forall x. 0 <= x < length pi -> indeg[x] = count_in trail x }332invariant { forall a. mem a trail -> sat pi.elts a }333by { pi = make 0 0; adj = make 0 Nil; indeg = make 0 0; trail = Nil;334len = 0 }335Valid (14ms) (colibri2)336let create () : t337ensures { result.trail = Nil }338= { pi = make 0 0; adj = make 0 Nil; indeg = make 0 0; trail = Nil;339len = 0 }340Valid (9ms) (colibri2)341let function size (t: t) : int = t.len342
a extended to the length m by d
Valid (337ms) (colibri2)let extend (a: array 'a) (m: int) (d: 'a) : array 'a345requires { length a <= m }346ensures { length result = m }347ensures { forall i. 0 <= i < length a -> result[i] = a[i] }348ensures { forall i. length a <= i < m -> result[i] = d }349= let r = make m d in350for i = 0 to length a - 1 do351invariant { forall j. 0 <= j < i -> r[j] = a[j] }352invariant { forall j. length a <= j < m -> r[j] = d }353r[i] <- a[i]354done;355r356
Make room for the vertex x: the new vertices have no edges
Valid (61ms) (cvc4)let ensure (t: t) (x: int) : unit359requires { 0 <= x }360ensures { x < length t.pi }361ensures { t.trail = old t.trail }362ensures { forall i. 0 <= i < length (old t.pi) -> t.pi[i] = (old t.pi)[i] }363= let n = length t.pi in364if x >= n then begin365let m = if x + 1 > 2 * n then x + 1 else 2 * n in366outs_facts t.trail;367let pi = extend t.pi m 0 in368let adj = extend t.adj m Nil in369let indeg = extend t.indeg m 0 in370t.pi <- pi;371t.adj <- adj;372t.indeg <- indeg373end374Valid (85ms) (cvc4)375let push (t: t) (e: edge) : unit376requires { 0 <= e.src < length t.pi /\ 0 <= e.dst < length t.pi }377requires { sat t.pi.elts e }378ensures { t.trail = Cons e (old t.trail) }379ensures { t.pi.elts = old t.pi.elts }380= t.adj[e.src] <- Cons e t.adj[e.src];381t.indeg[e.dst] <- t.indeg[e.dst] + 1;382t.trail <- Cons e t.trail;383t.len <- t.len + 1384
Remove the last edge
Valid (1.4s) (cvc5)let pop (t: t) : unit387requires { t.len > 0 }388ensures { old t.trail = Cons (match old t.trail with Cons a _ -> a389| Nil -> mk_dummy end) t.trail }390ensures { t.pi.elts = old t.pi.elts }391ensures { length t.pi = length (old t.pi) }392= match t.trail with393| Nil -> absurd394| Cons a r ->395let s = a.src in396t.adj[s] <- (match t.adj[s] with Nil -> Nil | Cons _ r' -> r' end);397t.indeg[a.dst] <- t.indeg[a.dst] - 1;398t.trail <- r;399t.len <- t.len - 1400end401
Remove the edges added after the length k
Valid (32ms) (colibri2 11) (split_vc) (depth 1)let rec backtrack (t: t) (k: int) : unit404requires { 0 <= k <= t.len }405ensures { cut (old t.trail) k t.trail }406ensures { t.pi.elts = old t.pi.elts }407ensures { length t.pi = length (old t.pi) }408variant { t.len }409= if t.len > k then begin410let ghost tr = t.trail in411pop t;412backtrack t k;413assert { match tr with414| Nil -> false415| Cons a r -> forall p. r = p ++ t.trail ->416tr = Cons a p ++ t.trail417end };418()419end else assert { t.trail = Nil ++ t.trail }420Valid (15ms) (colibri2)421let rec mem_edge (e: edge) (l: list edge) : bool422ensures { result <-> mem e l }423variant { l }424= match l with425| Nil -> false426| Cons a r ->427(a.src = e.src && a.dst = e.dst && a.wt = e.wt) || mem_edge e r428end429Valid (20ms) (colibri2)430let rec ghost path_ext (g g': int -> list edge) (n: int) (e: edge)431(x: int) (p: list edge) (y: int) : unit432requires { forall i. 0 <= i < n -> g i = g' i }433requires { path g n e x p y }434ensures { path g' n e x p y }435variant { p }436= match p with Nil -> () | Cons a r -> path_ext g g' n e a.dst r y end437438exception Bad_length439exception Bad_vertex440
Add the edge e after removing the edges added after the length k.
true: e is added (or it was already there), and the potential satisfies all the edges (invariant of t).false: the remaining edges with e have a negative cycle; e is not added.If e.src has no edge into it, the potential of e.src is raised: no other edge can be broken. Otherwise the potential is lowered from e.dst (NegCycle.lower).
Valid (408ms) (colibri2 51) (cvc4) (cvc5 3) (split_vc) (depth 1)let add (t: t) (k: int) (e: edge) : bool453raises { Bad_length -> (k < 0 \/ k > old t.len) /\454t.trail = old t.trail }455raises { Bad_vertex -> 0 <= k <= old t.len /\456(e.src < 0 \/ e.dst < 0) /\ t.trail = old t.trail }457ensures { 0 <= k <= old t.len /\ 0 <= e.src /\ 0 <= e.dst }458ensures { result -> exists tc. cut (old t.trail) k tc /\459(t.trail = Cons e tc \/ (t.trail = tc /\ mem e tc)) }460ensures { not result -> cut (old t.trail) k t.trail /\461neg_cycle (outs_map t.trail) (length t.pi) e }462= if k < 0 || k > t.len then raise Bad_length;463if e.src < 0 || e.dst < 0 then raise Bad_vertex;464backtrack t k;465let u = e.src in466let v = e.dst in467ensure t (if u < v then v else u);468outs_facts t.trail;469if t.pi[v] <= t.pi[u] + e.wt then begin470if not (mem_edge e t.adj[u]) then push t e;471true472end else if u <> v && t.indeg[u] = 0 then begin473t.pi[u] <- t.pi[v] - e.wt;474push t e;475true476end else begin477let ghost n = length t.pi in478assert { forall i. 0 <= i < n -> t.adj[i] = outs_map t.trail i };479try480lower t.adj t.pi e;481push t e;482true483with NegCycle ->484let lemma cyc (x: int) (p: list edge)485requires { path t.adj.elts n e x p x }486ensures { path (outs_map t.trail) n e x p x }487= path_ext t.adj.elts (outs_map t.trail) n e x p x488in489false490end491end492493end494