package ocamlgraph

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Parameters
Signature

package ocamlgraph

ocamlgraph
- Graph
  - Blocks
    
    BidirectionalLabeled
    
    E
    
    C
    
    HM
    
    I
    
    S
    
    V
    
    VE
    
    BidirectionalMinimal
    
    HM
    
    S
    
    BidirectionalUnlabeled
    
    E
    
    HM
    
    I
    
    S
    
    V
    
    ConcreteVertex
    
    F
    
    X
    
    HM
    
    V
    
    Graph
    
    G
    
    E
    
    V
    
    HM
    
    Labeled
    
    E
    
    C
    
    HM
    
    I
    
    S
    
    V
    
    VE
    
    Make
    
    Digraph
    
    Abstract
    
    E
    
    G
    
    E
    
    HM
    
    I
    
    PV
    
    S
    
    HM
    
    I
    
    PE
    
    PV
    
    S
    
    V
    
    AbstractLabeled
    
    E
    
    G
    
    E
    
    C
    
    HM
    
    I
    
    PV
    
    S
    
    VE
    
    HM
    
    I
    
    PE
    
    PV
    
    S
    
    V
    
    Concrete
    
    E
    
    HM
    
    I
    
    PV
    
    S
    
    V
    
    ConcreteBidirectional
    
    E
    
    HM
    
    I
    
    PV
    
    S
    
    V
    
    ConcreteBidirectionalLabeled
    
    E
    
    C
    
    Edge
    
    HM
    
    I
    
    PV
    
    S
    
    V
    
    VE
    
    ConcreteLabeled
    
    E
    
    C
    
    Edge
    
    HM
    
    I
    
    PV
    
    S
    
    V
    
    VE
    
    F
    
    X
    
    Make_Abstract
    
    G
    
    E
    
    HM
    
    S
    
    V
    
    I
    
    Make_Hashtbl
    
    X
    
    Make_Map
    
    X
    
    Minimal
    
    HM
    
    S
    
    Pred
    
    S
    
    PE
    
    PV
    
    TBL_BUILDER
    
    X
    
    Unlabeled
    
    E
    
    HM
    
    I
    
    S
    
    V
  - Builder
    
    I
    
    G
    
    E
    
    V
    
    INT
    
    G
    
    E
    
    V
    
    P
    
    G
    
    E
    
    V
    
    S
    
    G
    
    E
    
    V
  - ChaoticIteration
    
    Data
    
    G
    
    E
    
    V
    
    Make
    
    D
    
    G
    
    E
    
    V
    
    M
  - Classic
    
    I
    
    G
    
    E
    
    V
    
    P
    
    G
    
    E
    
    V
    
    S
  - Clique
    
    Bron_Kerbosch
    
    G
    
    V
    
    G
    
    V
  - Cliquetree
    
    CliqueTree
    
    CVS
    
    CliqueTree
    
    E
    
    V
    
    CliqueTreeE
    
    CliqueTreeV
    
    CliqueV
    
    G
    
    E
    
    V
  - Coloring
    
    G
    
    V
    
    GM
    
    Mark
    
    V
    
    Make
    
    G
    
    V
    
    H
    
    Mark
    
    G
    
    Mark
    
    V
  - Components
    
    G
    
    V
    
    Make
    
    G
    
    V
    
    U
    
    V
    
    Undirected
    
    G
    
    V
  - Contraction
    
    G
    
    E
    
    V
    
    Make
    
    G
    
    E
    
    V
  - DGraphModel
    
    DotG
    
    E
    
    V
    
    Make
    
    G
    
    E
    
    V
    
    model
    
    abstract_model
  - DGraphRandModel
    
    G
    
    E
    
    V
    
    GraphAttrs
    
    E
    
    V
  - DGraphSubTree
    
    G
    
    E
    
    V
    
    Make
    
    G
    
    E
    
    V
    
    Tree
    
    E
    
    V
    
    Make_from_dot_model
    
    Tree
    
    E
    
    V
    
    S
    
    Tree
    
    E
    
    V
    
    Tree
    
    E
    
    V
  - DGraphTreeLayout
    
    Make
    
    Tree
    
    E
    
    V
    
    TreeManipulation
    
    MakeFromDotModel
    
    Tree
    
    E
    
    V
    
    TreeManipulation
  - DGraphTreeModel
    
    S
    
    Tree
    
    E
    
    V
    
    TreeManipulation
    
    tree_model
    
    SubTreeDotModelMake
    
    Tree
    
    E
    
    V
    
    TreeManipulation
    
    tree_model
    
    SubTreeMake
    
    G
    
    E
    
    V
    
    Tree
    
    E
    
    V
    
    TreeManipulation
    
    tree_model
  - Delaunay
    
    CCC
    
    Float
    
    FloatPoints
    
    Int
    
    IntPoints
    
    Make
    
    S
    
    Triangulation
    
    S
  - Dominator
    
    G
    
    V
    
    I
    
    V
    
    Make
    
    G
    
    V
    
    S
    
    Make_graph
    
    G
    
    V
    
    S
    
    S
    
    S
  - Dot
    
    Parse
    
    B
    
    G
    
    E
    
    V
    
    L
  - Dot_ast
  - Fixpoint
    
    Analysis
    
    G
    
    E
    
    V
    
    Make
    
    A
    
    G
    
    E
    
    V
  - Flow
    
    FLOW
    
    FLOWMIN
    
    Ford_Fulkerson
    
    F
    
    G
    
    E
    
    V
    
    G_FORD_FULKERSON
    
    E
    
    V
    
    G_GOLDBERG_TARJAN
    
    E
    
    V
    
    Goldberg_Tarjan
    
    F
    
    G
    
    E
    
    V
  - Gmap
    
    E_DST
    
    E_SRC
    
    E
    
    Edge
    
    G_Dst
    
    G_Src
    
    E
    
    V_DST
    
    V_SRC
    
    V
    
    Vertex
    
    G_Dst
    
    G_Src
    
    V
  - Gml
    
    G
    
    E
    
    V
    
    Parse
    
    B
    
    G
    
    E
    
    V
    
    L
    
    Print
    
    G
    
    E
    
    V
    
    L
  - Graphml
    
    G
    
    E
    
    Print
    
    G
    
    E
    
    L
  - Graphviz
    
    ATTRIBUTES
    
    CommonAttributes
    
    Dot
    
    X
    
    E
    
    V
    
    DotAttributes
    
    GraphWithDotAttrs
    
    E
    
    V
    
    Neato
    
    X
    
    E
    
    V
    
    NeatoAttributes
  - Imperative
    
    Digraph
    
    Abstract
    
    E
    
    Mark
    
    V
    
    AbstractLabeled
    
    E
    
    Mark
    
    V
    
    Concrete
    
    E
    
    V
    
    ConcreteBidirectional
    
    E
    
    V
    
    ConcreteBidirectionalLabeled
    
    E
    
    V
    
    ConcreteLabeled
    
    E
    
    V
    
    Graph
    
    Abstract
    
    E
    
    Mark
    
    V
    
    AbstractLabeled
    
    E
    
    Mark
    
    V
    
    Concrete
    
    E
    
    V
    
    ConcreteLabeled
    
    E
    
    V
    
    Matrix
    
    Digraph
    
    E
    
    V
    
    Graph
    
    E
    
    V
    
    S
    
    E
    
    V
    
    S
    
    Abstract
    
    E
    
    Mark
    
    V
    
    AbstractLabeled
    
    E
    
    Mark
    
    V
    
    Concrete
    
    E
    
    V
    
    ConcreteLabeled
    
    E
    
    V
  - Kruskal
    
    G
    
    E
    
    V
    
    Generic
    
    G
    
    E
    
    V
    
    UF
    
    W
    
    Make
    
    G
    
    E
    
    V
    
    W
    
    UNIONFIND
  - Leaderlist
    
    G
    
    V
    
    Make
    
    G
    
    V
  - Mcs_m
    
    MaximalCardinalitySearch
    
    I
    
    Gr
    
    E
    
    V
    
    P
    
    G
    
    E
    
    V
  - Md
    
    I
    
    G
    
    E
    
    V
    
    P
    
    G
    
    E
    
    V
  - Merge
    
    B
    
    X
    
    G
    
    E
    
    V
    
    I
    
    G
    
    E
    
    V
    
    P
    
    G
    
    E
    
    V
    
    S
  - Mincut
    
    G
    
    V
    
    Make
    
    G
    
    V
  - Minsep
    
    G
    
    V
    
    I
    
    G
    
    Mark
    
    V
    
    VSetset
    
    Vertex_Set
    
    MINSEP
    
    G
    
    V
    
    VSetset
    
    Vertex_Set
    
    P
    
    G
    
    V
    
    VSetset
    
    Vertex_Set
  - Nonnegative
    
    Imperative
    
    G
    
    E
    
    Mark
    
    V
    
    Mark
    
    W
    
    Persistent
    
    G
    
    E
    
    V
    
    W
  - Oper
    
    Choose
    
    G
    
    I
    
    G
    
    E
    
    V
    
    Make
    
    B
    
    G
    
    E
    
    V
    
    Neighbourhood
    
    G
    
    V
    
    Vertex_Set
    
    P
    
    G
    
    E
    
    V
    
    S
  - Pack
    
    Digraph
    
    Bfs
    
    Classic
    
    Coloring
    
    Components
    
    Dfs
    
    E
    
    Mark
    
    Marking
    
    PathCheck
    
    Rand
    
    Topological
    
    V
    
    Graph
    
    Bfs
    
    Classic
    
    Coloring
    
    Components
    
    Dfs
    
    E
    
    Mark
    
    Marking
    
    PathCheck
    
    Rand
    
    Topological
    
    V
  - Path
    
    BellmanFord
    
    G
    
    E
    
    V
    
    H
    
    W
    
    Check
    
    G
    
    V
    
    Dijkstra
    
    G
    
    E
    
    V
    
    W
    
    G
    
    E
    
    V
    
    Johnson
    
    G
    
    E
    
    V
    
    HVV
    
    W
    
    WJ
  - Persistent
    
    Digraph
    
    Abstract
    
    E
    
    V
    
    AbstractLabeled
    
    E
    
    V
    
    Concrete
    
    E
    
    V
    
    ConcreteBidirectional
    
    E
    
    V
    
    ConcreteBidirectionalLabeled
    
    E
    
    V
    
    ConcreteLabeled
    
    E
    
    V
    
    Graph
    
    Abstract
    
    E
    
    V
    
    AbstractLabeled
    
    E
    
    V
    
    Concrete
    
    E
    
    V
    
    ConcreteLabeled
    
    E
    
    V
    
    S
    
    Abstract
    
    E
    
    V
    
    AbstractLabeled
    
    E
    
    V
    
    Concrete
    
    E
    
    V
    
    ConcreteLabeled
    
    E
    
    V
  - Prim
    
    G
    
    E
    
    V
    
    Make
    
    G
    
    E
    
    V
    
    W
  - Rand
    
    I
    
    G
    
    E
    
    V
    
    Make
    
    B
    
    G
    
    E
    
    V
    
    P
    
    G
    
    E
    
    V
    
    Planar
    
    I
    
    G
    
    E
    
    V
    
    Make
    
    B
    
    G
    
    E
    
    V
    
    P
    
    G
    
    E
    
    V
    
    S
    
    S
  - Sig
    
    ANY_TYPE
    
    COMPARABLE
    
    EDGE
    
    G
    
    E
    
    V
    
    HASHABLE
    
    I
    
    E
    
    V
    
    IM
    
    E
    
    Mark
    
    V
    
    MARK
    
    ORDERED_TYPE
    
    ORDERED_TYPE_DFT
    
    P
    
    E
    
    V
    
    VERTEX
    
    WEIGHT
  - Sig_pack
    
    S
    
    Bfs
    
    Classic
    
    Coloring
    
    Components
    
    Dfs
    
    E
    
    Mark
    
    Marking
    
    PathCheck
    
    Rand
    
    Topological
    
    V
  - Strat
    
    Algo
    
    G
    
    V
    
    P
    
    S
    
    G
    
    V
    
    PLAYER
    
    STRAT
  - Topological
    
    G
    
    V
    
    Make
    
    G
    
    V
    
    Make_stable
    
    G
    
    V
  - Traverse
    
    Bfs
    
    G
    
    V
    
    Dfs
    
    G
    
    V
    
    G
    
    V
    
    GM
    
    Mark
    
    V
    
    Mark
    
    G
    
    Mark
    
    V
  - Util
    
    CMPProduct
    
    X
    
    Y
    
    DataV
    
    L
    
    V
    
    HTProduct
    
    X
    
    Y
    
    OTProduct
    
    X
    
    Y
  - WeakTopological
    
    G
    
    V
    
    Make
    
    G
    
    V
  - XDot
    
    Make
    
    G
    
    E
    
    V
    
    HE
    
    HV
  - XDotDraw

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