Module CongruenceClosure.MRMap

Minimal representatives map. It maps each representative term of an equivalence class to the minimal term of this representative class. rep -> (t, z) means that t = rep + z

type t = (T.t * Z.t) TMap.t
val equal : t -> t -> Ppx_deriving_runtime.bool
val compare : t -> t -> Ppx_deriving_runtime.int
val hash : t -> int
val bindings : 'a TMap.t -> (TMap.key * 'a) list
val find : TMap.key -> 'a TMap.t -> 'a
val find_opt : TMap.key -> 'a TMap.t -> 'a option
val add : TMap.key -> 'a -> 'a TMap.t -> 'a TMap.t
val remove : TMap.key -> 'a TMap.t -> 'a TMap.t
val mem : TMap.key -> 'a TMap.t -> bool
val empty : 'a TMap.t
val show_min_rep : (T.t * Z.t) TMap.t -> string
val update_min_repr : (((Goblint_lib__UnionFind.term * Z.t) * 'a) TUF.ValMap.t * TSet.t * LMap.t) -> (term * Z.t) TMap.t -> TUF.ValMap.key list -> (term * Z.t) TMap.t

Uses dijkstra algorithm to update the minimal representatives of the successor nodes of all edges in the queue and if necessary it recursively updates the minimal representatives of the successor nodes. The states in the queue must already have an updated min_repr. This function visits only the successor nodes of the nodes in queue, not the nodes themselves. Before visiting the nodes, it sorts the queue by the size of the current mininmal representative.

parameters:

  • `(uf, set, map)` represent the union find data structure and the corresponding term set and lookup map.
  • `min_representatives` maps each representative of the union find data structure to the minimal representative of the equivalence class.
  • `queue` contains the states that need to be processed. The states of the automata are the equivalence classes and each state of the automata is represented by the representative term. Therefore the queue is a list of representative terms.

Returns:

  • The updated `min_representatives` map with the minimal representatives
val compute_minimal_representatives : (((Goblint_lib__UnionFind.term * Z.t) * 'a) TUF.ValMap.t * TSet.t * LMap.t) -> (term * Z.t) TMap.t
val initial_minimal_representatives : TSet.t -> (TMap.key * Z.t) TMap.t

Computes the initial map of minimal representatives. It maps each element `e` in the set to `(e, 0)`.