Common — library colibrilib.negcycle — module Graph

A 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.

279
module Graph
280
281
use int.Int
282
use list.List
283
use list.Mem
284
use list.Append
285
use list.Length
286
use map.Map
287
use array.Array
288
use ref.Ref
289
use NegCycle

The edges of l out of x, in the order of l

292
function
outs
(l: list edge) (x: int) : list edge =
293
match l with
294
| Nil -> Nil
295
| Cons a r -> if a.src = x then Cons a (outs r x) else outs r x
296
end

The number of edges of l into x

299
function
count_in
(l: list edge) (x: int) : int =
300
match l with
301
| Nil -> 0
302
| Cons a r -> (if a.dst = x then 1 else 0) + count_in r x
303
end
304
305
function
outs_map
(l: list edge) : int -> list edge = fun x -> outs l x
306
Valid (96ms) (colibri2)
307
let rec ghost
outs_facts
(l: list edge) : unit
308
ensures { forall x a. mem a (outs l x) <-> mem a l /\ a.src = x }
309
ensures { forall x. (forall a. mem a l -> a.src <> x) -> outs l x = Nil }
310
ensures { forall x. 0 <= count_in l x }
311
ensures { forall x. count_in l x = 0 <-> forall a. mem a l -> a.dst <> x }
312
variant { l }
313
= match l with Nil -> () | Cons _ r -> outs_facts r end
314
315
let constant
mk_dummy
: edge = { src = 0; dst = 0; wt = 0 }

tc is the suffix of l of length len

318
predicate
cut
(l: list edge) (len: int) (tc: list edge) =
319
Length.length tc = len /\ exists p. l = p ++ tc
320
Valid (19ms) (colibri2)
321
type
t
= {
322
mutable
pi
: array int;
323
mutable
adj
: array (list edge);
324
mutable
indeg
: array int;
325
mutable
trail
: list edge;
326
mutable
len
: int;
327
} invariant { length pi = length adj = length indeg }
328
invariant { len = Length.length trail }
329
invariant { forall a. mem a trail ->
330
0 <= a.src < length pi /\ 0 <= a.dst < length pi }
331
invariant { forall x. 0 <= x < length pi -> adj[x] = outs trail x }
332
invariant { forall x. 0 <= x < length pi -> indeg[x] = count_in trail x }
333
invariant { forall a. mem a trail -> sat pi.elts a }
334
by { pi = make 0 0; adj = make 0 Nil; indeg = make 0 0; trail = Nil;
335
len = 0 }
336
Valid (14ms) (colibri2)
337
let
create
() : t
338
ensures { result.trail = Nil }
339
= { pi = make 0 0; adj = make 0 Nil; indeg = make 0 0; trail = Nil;
340
len = 0 }
341
Valid (9ms) (colibri2)
342
let function
size
(t: t) : int = t.len

a extended to the length m by d

  Valid (337ms) (colibri2)
345
let
extend
(a: array 'a) (m: int) (d: 'a) : array 'a
346
requires { length a <= m }
347
ensures { length result = m }
348
ensures { forall i. 0 <= i < length a -> result[i] = a[i] }
349
ensures { forall i. length a <= i < m -> result[i] = d }
350
= let r = make m d in
351
for i = 0 to length a - 1 do
352
invariant { forall j. 0 <= j < i -> r[j] = a[j] }
353
invariant { forall j. length a <= j < m -> r[j] = d }
354
r[i] <- a[i]
355
done;
356
r

Make room for the vertex x: the new vertices have no edges

  Valid (61ms) (cvc4)
359
let
ensure
(t: t) (x: int) : unit
360
requires { 0 <= x }
361
ensures { x < length t.pi }
362
ensures { t.trail = old t.trail }
363
ensures { forall i. 0 <= i < length (old t.pi) -> t.pi[i] = (old t.pi)[i] }
364
= let n = length t.pi in
365
if x >= n then begin
366
let m = if x + 1 > 2 * n then x + 1 else 2 * n in
367
outs_facts t.trail;
368
let pi = extend t.pi m 0 in
369
let adj = extend t.adj m Nil in
370
let indeg = extend t.indeg m 0 in
371
t.pi <- pi;
372
t.adj <- adj;
373
t.indeg <- indeg
374
end
375
Valid (85ms) (cvc4)
376
let
push
(t: t) (e: edge) : unit
377
requires { 0 <= e.src < length t.pi /\ 0 <= e.dst < length t.pi }
378
requires { sat t.pi.elts e }
379
ensures { t.trail = Cons e (old t.trail) }
380
ensures { t.pi.elts = old t.pi.elts }
381
= t.adj[e.src] <- Cons e t.adj[e.src];
382
t.indeg[e.dst] <- t.indeg[e.dst] + 1;
383
t.trail <- Cons e t.trail;
384
t.len <- t.len + 1

Remove the last edge

  Valid (1.4s) (cvc5)
387
let
pop
(t: t) : unit
388
requires { t.len > 0 }
389
ensures { old t.trail = Cons (match old t.trail with Cons a _ -> a
390
| Nil -> mk_dummy end) t.trail }
391
ensures { t.pi.elts = old t.pi.elts }
392
ensures { length t.pi = length (old t.pi) }
393
= match t.trail with
394
| Nil -> absurd
395
| Cons a r ->
396
let s = a.src in
397
t.adj[s] <- (match t.adj[s] with Nil -> Nil | Cons _ r' -> r' end);
398
t.indeg[a.dst] <- t.indeg[a.dst] - 1;
399
t.trail <- r;
400
t.len <- t.len - 1
401
end

Remove the edges added after the length k

  Valid (32ms) (colibri2 11) (split_vc) (depth 1)
404
let rec
backtrack
(t: t) (k: int) : unit
405
requires { 0 <= k <= t.len }
406
ensures { cut (old t.trail) k t.trail }
407
ensures { t.pi.elts = old t.pi.elts }
408
ensures { length t.pi = length (old t.pi) }
409
variant { t.len }
410
= if t.len > k then begin
411
let ghost tr = t.trail in
412
pop t;
413
backtrack t k;
414
assert { match tr with
415
| Nil -> false
416
| Cons a r -> forall p. r = p ++ t.trail ->
417
tr = Cons a p ++ t.trail
418
end };
419
()
420
end else assert { t.trail = Nil ++ t.trail }
421
Valid (15ms) (colibri2)
422
let rec
mem_edge
(e: edge) (l: list edge) : bool
423
ensures { result <-> mem e l }
424
variant { l }
425
= match l with
426
| Nil -> false
427
| Cons a r ->
428
(a.src = e.src && a.dst = e.dst && a.wt = e.wt) || mem_edge e r
429
end
430
Valid (20ms) (colibri2)
431
let rec ghost
path_ext
(g g': int -> list edge) (n: int) (e: edge)
432
(x: int) (p: list edge) (y: int) : unit
433
requires { forall i. 0 <= i < n -> g i = g' i }
434
requires { path g n e x p y }
435
ensures { path g' n e x p y }
436
variant { p }
437
= match p with Nil -> () | Cons a r -> path_ext g g' n e a.dst r y end
438
439
exception
Bad_length
440
exception
Bad_vertex

Add the edge e after removing the edges added after the length k.

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)
453
let
add
(t: t) (k: int) (e: edge) : bool
454
raises { Bad_length -> (k < 0 \/ k > old t.len) /\
455
t.trail = old t.trail }
456
raises { Bad_vertex -> 0 <= k <= old t.len /\
457
(e.src < 0 \/ e.dst < 0) /\ t.trail = old t.trail }
458
ensures { 0 <= k <= old t.len /\ 0 <= e.src /\ 0 <= e.dst }
459
ensures { result -> exists tc. cut (old t.trail) k tc /\
460
(t.trail = Cons e tc \/ (t.trail = tc /\ mem e tc)) }
461
ensures { not result -> cut (old t.trail) k t.trail /\
462
neg_cycle (outs_map t.trail) (length t.pi) e }
463
= if k < 0 || k > t.len then raise Bad_length;
464
if e.src < 0 || e.dst < 0 then raise Bad_vertex;
465
backtrack t k;
466
let u = e.src in
467
let v = e.dst in
468
ensure t (if u < v then v else u);
469
outs_facts t.trail;
470
if t.pi[v] <= t.pi[u] + e.wt then begin
471
if not (mem_edge e t.adj[u]) then push t e;
472
true
473
end else if u <> v && t.indeg[u] = 0 then begin
474
t.pi[u] <- t.pi[v] - e.wt;
475
push t e;
476
true
477
end else begin
478
let ghost n = length t.pi in
479
assert { forall i. 0 <= i < n -> t.adj[i] = outs_map t.trail i };
480
try
481
lower t.adj t.pi e;
482
push t e;
483
true
484
with NegCycle ->
485
let lemma cyc (x: int) (p: list edge)
486
requires { path t.adj.elts n e x p x }
487
ensures { path (outs_map t.trail) n e x p x }
488
= path_ext t.adj.elts (outs_map t.trail) n e x p x
489
in
490
false
491
end
492
end
493
494
end