Functor Path.Check

module Check: 
functor (G : sig
type t 
module V: Sig.COMPARABLE 
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
end) -> sig .. end
Check for a path.
G : sig type t module V : Sig.COMPARABLE val iter_succ : (V.t -> unit) -> t -> V.t -> unit end

type path_checker 
the abstract data type of a path checker; this is a mutable data structure
val create : Path.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, Dijkstra's algorithm 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).