Common — library colibrilib.negcycle — module Export

For extraction

497
module Export
498
499
use int.Int
500
use list.List
501
use list.Mem
502
use array.Array
503
use NegCycle
504
use Graph
505
506
let function
mk_edge
(s d w: int) : edge = { src = s; dst = d; wt = w }
507
Valid (17ms) (colibri2)
508
let
create
() : Graph.t = Graph.create ()
509
Valid (16ms) (colibri2)
510
let function
size
(t: Graph.t) : int = Graph.size t

Graph.add

  Valid (20ms) (colibri2)
513
let
add
(t: Graph.t) (k: int) (e: edge) : bool
514
raises { Graph.Bad_length -> k < 0 \/ k > old t.len }
515
raises { Graph.Bad_vertex -> 0 <= k <= old t.len /\
516
(e.src < 0 \/ e.dst < 0) }
517
ensures { result -> exists tc. cut (old t.trail) k tc /\
518
(t.trail = Cons e tc \/ (t.trail = tc /\ mem e tc)) }
519
ensures { not result -> cut (old t.trail) k t.trail /\
520
neg_cycle (outs_map t.trail) (Array.length t.pi) e }
521
= Graph.add t k e
522
523
end