package ocamlgraph

  1. Overview
  2. Docs
package ocamlgraph
Legend:
Library
Module
Module type
Parameter
Class
Class type

Check for a path.

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).