## Parameters

`module G : sig ... end`

## Signature

`type path_checker`

the abstract data type of a path checker; this is a mutable data structure

`val create : G.t -> path_checker`

`create g` builds a new path checker for the graph `g`; if the graph is mutable, it must not be mutated while this path checker is in use (through the function `check_path` below).

`val check_path : path_checker -> G.V.t -> G.V.t -> bool`

`check_path pc v1 v2` checks whether there is a path from `v1` to `v2` in the graph associated to the path checker `pc`.

Complexity: The path checker contains a cache of all results computed so far. This cache is implemented with a hash table so access in this cache is usually O(1). When the result is not in the cache, a BFS is run to check for the path, and all intermediate results are cached.

Note: if checks are to be done for almost all pairs of vertices, it may be more efficient to compute the transitive closure of the graph (see module `Oper`).