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
    
    BiConnectivity
    
    G
    
    E
    
    V
    
    S
    
    Connectivity
    
    GB
    
    G
    
    E
    
    V
    
    S
    
    G
    
    V
    
    Make
    
    G
    
    V
    
    U
    
    V
    
    Undirected
    
    G
    
    V
  - Contraction
    
    G
    
    E
    
    V
    
    Make
    
    G
    
    E
    
    V
  - Cycles
    
    Fashwo
    
    GB
    
    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
    
    Eulerian
    
    Mark
    
    Marking
    
    PathCheck
    
    Rand
    
    Topological
    
    V
    
    Graph
    
    Bfs
    
    Classic
    
    Coloring
    
    Components
    
    Dfs
    
    E
    
    Eulerian
    
    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
    
    Eulerian
    
    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
    
    Memo
    
    X
    
    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

Parameters

module G : G

Signature

type t = G.t

type of graphs

type vertex = G.V.t

type of vertices

module S : Set.S with type elt = vertex

type idom = vertex -> vertex

function from n to n's immediate dominator

type idoms = vertex -> vertex -> bool

idoms x y is true when x is y's immediate dominator

type dom_tree = vertex -> vertex list

function from x to a list of nodes immediately dominated by x

type dominators = vertex -> vertex list

function from node to a list of nodes that dominate it.

type dom = vertex -> vertex -> bool

dom x y returns true iff x dominates y

type sdom = vertex -> vertex -> bool

sdom x y returns true iff x strictly dominates y.

type dom_frontier = vertex -> vertex list

function from x to a list of nodes not dominated by x, but with predecessors which are dominated by x

val compute_idom : t -> vertex -> vertex -> vertex

Computes the dominator tree, using the Lengauer-Tarjan algorithm. compute_idom cfg s0 returns a function idom : V.t -> V.t s.t. idom x returns the immediate dominator of x.

val dominators_to_dom : ('a -> S.t) -> vertex -> 'a -> bool

Given a function from a node to it's dominators, returns a function dom : V.t -> V.t -> bool s.t. dom x y returns true when x dominates y.

val dominators_to_sdom : (vertex -> S.t) -> vertex -> vertex -> bool

Given a function from a node to it's dominators, returns a function sdom : V.t -> V.t -> bool s.t. sdom x y returns true when x strictly dominates y.

val dom_to_sdom : (vertex -> vertex -> bool) -> vertex -> vertex -> bool

val dominators_to_sdominators : (vertex -> S.t) -> vertex -> S.t

Given a a function from a node to it's dominators, returns a function from a node to it's strict dominators.

val dominators_to_idoms : (vertex -> S.t) -> vertex -> vertex -> bool

Given a function from a node to it's dominators, returns a function idoms : vertex -> vertex -> bool s.t. idoms x y returns true when x is the immediate dominator of y.

val dominators_to_dom_tree : 
  t ->
  ?pred:(t -> vertex -> vertex list) ->
  (vertex -> S.t) ->
  vertex ->
  S.t

Computes a dominator tree (function from x to a list of nodes immediately dominated by x) for the given CFG and dominator function. Note: The dominator tree is also called IDom by Muchnick. Note: If you are computing a post-dominator tree, then the optional argument pred should be G.succ.

val idom_to_dom_tree : t -> (vertex -> vertex) -> vertex -> vertex list

Computes a dominator tree (function from x to a list of nodes immediately dominated by x) for the given CFG and idom function.

val idom_to_idoms : idom -> vertex -> vertex -> bool

val compute_dom_frontier : t -> dom_tree -> idom -> vertex -> vertex list

Computes the dominance frontier. As specified in section 19.1 of Modern Compiler Implementation in ML by Andrew Appel.

val idom_to_dominators : ('a -> 'a) -> 'a -> 'a list

val idom_to_dom : (vertex -> vertex) -> vertex -> vertex -> bool

val dom_tree_to_nontrivial_dom : vertex -> dom_tree -> vertex list

Returns a list of the non-trivial dominators of a flowgraph G(v) given the start vertex v and the corresponding dominator tree. E.g., dom_tree_to_nontrivial_dom v (idom_to_dom_tree g (compute_idom g v)). A vertex u is a non-trivial dominator of G(v) if it dominates some vertex w other than v and u.

val dom_tree_to_snontrivial_dom : vertex -> dom_tree -> S.t

As for dom_tree_to_nontrivial_dom but returns a set.