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
    
    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
    
    V
    
    I
    
    Make_Hashtbl
    
    X
    
    Make_Map
    
    X
    
    Minimal
    
    HM
    
    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
  - Classic
    
    I
    
    G
    
    E
    
    V
    
    P
    
    G
    
    E
    
    V
    
    S
  - Clique
    
    Bron_Kerbosch
    
    G
    
    V
    
    G
    
    V
  - Cliquetree
    
    CliqueTree
    
    CliqueTree
    
    E
    
    V
    
    CliqueTreeE
    
    CliqueTreeV
    
    CliqueV
    
    G
    
    E
    
    V
  - Coloring
    
    G
    
    V
    
    GM
    
    Mark
    
    V
    
    Make
    
    G
    
    V
    
    Mark
    
    G
    
    Mark
    
    V
  - Components
    
    BiConnectivity
    
    G
    
    E
    
    V
    
    Connectivity
    
    GB
    
    G
    
    E
    
    V
    
    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
    
    Make_graph
    
    G
    
    V
    
    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
    
    MINSEP
    
    G
    
    V
    
    P
    
    G
    
    V
  - 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
    
    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
    
    W
    
    Check
    
    G
    
    V
    
    Dijkstra
    
    G
    
    E
    
    V
    
    W
    
    G
    
    E
    
    V
    
    Johnson
    
    G
    
    E
    
    V
    
    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
  - XDotDraw

Legend:
Library
Module
Module type
Parameter
Class
Class type

Parameters

module G : I

Signature

include S with type t = G.t and type vertex = G.V.t

type t = G.t

type of graphs

type vertex = G.V.t

type of vertices

module S : Stdlib.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.

type dom_graph = unit -> t

type dom_functions = {

idom : idom;
idoms : idoms;
dom_tree : dom_tree;
dominators : dominators;
dom : dom;
sdom : sdom;
dom_frontier : dom_frontier;
dom_graph : dom_graph;

}

val compute_dom_graph : G.t -> dom_tree -> G.t

val compute_all : G.t -> vertex -> dom_functions

Computes all dominance functions.

This function computes some things eagerly and some lazily, so don't worry about it doing extra work to compute functions you don't need, but also don't call it if you aren't going to use anything it returns.

returns
a record containing all dominance functions for the given graph and entry node.