Path.Check
Check for a path.
module G : sig ... end
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
).