Module Algebra.Bottleneck

Bottleneck semiring: ({-∞} ∪ ℤ ∪ {+∞}, max, min, -∞, +∞).

Addition is max, multiplication is min. This models bottleneck-capacity shortest-path problems. The semiring is unbounded (only NegInf and PosInf as sentinels) so elements is not supported.

SMT encoding maps the three-constructor type to integers via sentinel values: NegInf → -2, PosInf → -1. Ordinary integer weights live in 0, +∞). Every arithmetic operation branches on the sentinel values via ITE guards. Logic is [QF_LIA].

module Log : sig ... end
module T : sig ... end
include module type of struct include T end
type t = T.t =
  1. | NegInf
  2. | PosInf
  3. | Num of Base.int
val compare : t -> t -> Base.int
val equal : t -> t -> Base.bool
val hash_fold_t : Ppx_hash_lib.Std.Hash.state -> t -> Ppx_hash_lib.Std.Hash.state
val hash : t -> Ppx_hash_lib.Std.Hash.hash_value
val sexp_of_t : t -> Sexplib0.Sexp.t
include sig ... end
type comparator_witness = Base__Comparator.Make(T).comparator_witness
val comparator : (T.t, comparator_witness) Base__Comparator.comparator
val zero : t

Additive identity: max(NegInf, x) = x for all x.

val one : t

Multiplicative identity: min(PosInf, x) = x for all x.

val rand : ?non_zero:Base__Float.t -> ?max:Base.Int.t -> unit -> t
val add : t -> t -> t

add = max: max(NegInf, x) = x; max(PosInf, _) = PosInf.

val mul : t -> t -> t

mul = min: min(PosInf, x) = x; min(NegInf, _) = NegInf.

val elements : unit -> 'a
val to_string : t -> string
module SMT : sig ... end