package ocamlgraph

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Bidirectional graphs

package ocamlgraph

ocamlgraph
- CHANGES
- README
- Library ocamlgraph
  - Graph
    
    Sig
    
    ANY_TYPE
    
    ORDERED_TYPE
    
    ORDERED_TYPE_DFT
    
    HASHABLE
    
    COMPARABLE
    
    VERTEX
    
    EDGE
    
    G
    
    V
    
    E
    
    P
    
    V
    
    E
    
    I
    
    V
    
    E
    
    WEIGHT
    
    MARK
    
    IM
    
    V
    
    E
    
    Mark
    
    Sig_pack
    
    S
    
    V
    
    E
    
    Mark
    
    Dfs
    
    Bfs
    
    Marking
    
    Coloring
    
    Classic
    
    Rand
    
    Components
    
    PathCheck
    
    Topological
    
    Dot_ast
    
    Util
    
    OTProduct
    
    HTProduct
    
    CMPProduct
    
    DataV
    
    Blocks
    
    HM
    
    TBL_BUILDER
    
    Make_Hashtbl
    
    Make_Map
    
    Minimal
    
    Pred
    
    Unlabeled
    
    S
    
    E
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    Labeled
    
    VE
    
    S
    
    E
    
    C
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    ConcreteVertex
    
    V
    
    HM
    
    Make_Abstract
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    V
    
    E
    
    HM
    
    S
    
    BidirectionalMinimal
    
    BidirectionalUnlabeled
    
    S
    
    E
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    BidirectionalLabeled
    
    VE
    
    S
    
    E
    
    C
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    Make
    
    Digraph
    
    Concrete
    
    V
    
    HM
    
    S
    
    E
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    ConcreteBidirectional
    
    V
    
    HM
    
    S
    
    E
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    ConcreteLabeled
    
    V
    
    HM
    
    VE
    
    S
    
    E
    
    C
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    ConcreteBidirectionalLabeled
    
    V
    
    HM
    
    VE
    
    S
    
    E
    
    C
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    Abstract
    
    G
    
    V
    
    HM
    
    S
    
    E
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    V
    
    E
    
    HM
    
    S
    
    AbstractLabeled
    
    G
    
    V
    
    HM
    
    VE
    
    S
    
    E
    
    C
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    I
    
    PV
    
    PE
    
    PV
    
    PE
    
    V
    
    E
    
    HM
    
    S
    
    Graph
    
    V
    
    E
    
    Persistent
    
    S
    
    Concrete
    
    V
    
    E
    
    Abstract
    
    V
    
    E
    
    ConcreteLabeled
    
    V
    
    E
    
    AbstractLabeled
    
    V
    
    E
    
    Digraph
    
    Concrete
    
    V
    
    E
    
    Abstract
    
    V
    
    E
    
    ConcreteLabeled
    
    V
    
    E
    
    AbstractLabeled
    
    V
    
    E
    
    ConcreteBidirectional
    
    V
    
    E
    
    ConcreteBidirectionalLabeled
    
    V
    
    E
    
    Graph
    
    Concrete
    
    V
    
    E
    
    Abstract
    
    V
    
    E
    
    ConcreteLabeled
    
    V
    
    E
    
    AbstractLabeled
    
    V
    
    E
    
    Imperative
    
    S
    
    Concrete
    
    V
    
    E
    
    Abstract
    
    V
    
    E
    
    Mark
    
    ConcreteLabeled
    
    V
    
    E
    
    AbstractLabeled
    
    V
    
    E
    
    Mark
    
    Digraph
    
    Concrete
    
    V
    
    E
    
    Abstract
    
    V
    
    E
    
    Mark
    
    ConcreteLabeled
    
    V
    
    E
    
    AbstractLabeled
    
    V
    
    E
    
    Mark
    
    ConcreteBidirectional
    
    V
    
    E
    
    ConcreteBidirectionalLabeled
    
    V
    
    E
    
    Graph
    
    Concrete
    
    V
    
    E
    
    Abstract
    
    V
    
    E
    
    Mark
    
    ConcreteLabeled
    
    V
    
    E
    
    AbstractLabeled
    
    V
    
    E
    
    Mark
    
    Matrix
    
    S
    
    V
    
    E
    
    Digraph
    
    V
    
    E
    
    Graph
    
    V
    
    E
    
    Delaunay
    
    CCC
    
    Triangulation
    
    S
    
    Make
    
    S
    
    IntPoints
    
    Int
    
    S
    
    FloatPoints
    
    Float
    
    S
    
    Builder
    
    S
    
    G
    
    V
    
    E
    
    INT
    
    G
    
    V
    
    E
    
    P
    
    G
    
    I
    
    G
    
    Classic
    
    S
    
    P
    
    I
    
    Rand
    
    S
    
    Make
    
    P
    
    I
    
    Planar
    
    S
    
    Make
    
    P
    
    I
    
    Oper
    
    S
    
    Make
    
    P
    
    I
    
    Choose
    
    Neighbourhood
    
    Vertex_Set
    
    Components
    
    G
    
    V
    
    Make
    
    U
    
    V
    
    Undirected
    
    Path
    
    G
    
    V
    
    E
    
    Dijkstra
    
    BellmanFord
    
    H
    
    WJ
    
    Johnson
    
    HVV
    
    Check
    
    Nonnegative
    
    Imperative
    
    V
    
    E
    
    Mark
    
    Persistent
    
    V
    
    E
    
    Traverse
    
    G
    
    V
    
    Dfs
    
    Bfs
    
    GM
    
    V
    
    Mark
    
    Mark
    
    Coloring
    
    GM
    
    V
    
    Mark
    
    Mark
    
    G
    
    V
    
    Make
    
    H
    
    Topological
    
    G
    
    V
    
    Make
    
    Make_stable
    
    Kruskal
    
    G
    
    V
    
    E
    
    Make
    
    UNIONFIND
    
    Generic
    
    Flow
    
    FLOW
    
    G_GOLDBERG_TARJAN
    
    V
    
    E
    
    Goldberg_Tarjan
    
    G_FORD_FULKERSON
    
    V
    
    E
    
    FLOWMIN
    
    Ford_Fulkerson
    
    Prim
    
    G
    
    V
    
    E
    
    Make
    
    Dominator
    
    G
    
    V
    
    S
    
    S
    
    Make
    
    S
    
    I
    
    V
    
    Make_graph
    
    S
    
    Graphviz
    
    ATTRIBUTES
    
    CommonAttributes
    
    DotAttributes
    
    GraphWithDotAttrs
    
    V
    
    E
    
    Dot
    
    NeatoAttributes
    
    Neato
    
    Gml
    
    Parse
    
    G
    
    V
    
    E
    
    Print
    
    Dot
    
    Parse
    
    Pack
    
    Digraph
    
    V
    
    E
    
    Mark
    
    Dfs
    
    Bfs
    
    Marking
    
    Coloring
    
    Classic
    
    Rand
    
    Components
    
    PathCheck
    
    Topological
    
    Graph
    
    V
    
    E
    
    Mark
    
    Dfs
    
    Bfs
    
    Marking
    
    Coloring
    
    Classic
    
    Rand
    
    Components
    
    PathCheck
    
    Topological
    
    Gmap
    
    V_SRC
    
    V
    
    V_DST
    
    Vertex
    
    E_SRC
    
    E
    
    E_DST
    
    Edge
    
    Minsep
    
    G
    
    V
    
    MINSEP
    
    G
    
    V
    
    Vertex_Set
    
    VSetset
    
    P
    
    G
    
    Vertex_Set
    
    VSetset
    
    I
    
    G
    
    Vertex_Set
    
    VSetset
    
    Cliquetree
    
    CliqueTree
    
    CliqueV
    
    CVS
    
    CliqueTreeV
    
    CliqueTreeE
    
    CliqueTree
    
    V
    
    E
    
    Mcs_m
    
    MaximalCardinalitySearch
    
    P
    
    I
    
    Md
    
    P
    
    I
    
    Strat
    
    G
    
    V
    
    PLAYER
    
    STRAT
    
    Algo
    
    Fixpoint
    
    G
    
    V
    
    E
    
    Analysis
    
    Make
    
    Leaderlist
    
    G
    
    V
    
    Make
    
    Contraction
    
    G
    
    V
    
    E
    
    Make
    
    Graphml
    
    G
    
    E
    
    Print
    
    Merge
    
    S
    
    B
    
    P
    
    I
    
    Mincut
    
    G
    
    V
    
    Make
    
    Clique
    
    G
    
    V
    
    Bron_Kerbosch
    
    WeakTopological
    
    G
    
    V
    
    Make
    
    ChaoticIteration
    
    G
    
    V
    
    E
    
    Data
    
    Make
    
    M
    
    XDotDraw
    
    XDot
    
    Make
    
    HV
    
    HE
    
    DGraphModel
    
    abstract_model
    
    Make
    
    model
    
    DotG
    
    V
    
    E
    
    DGraphTreeLayout
    
    Make
    
    MakeFromDotModel
    
    Tree
    
    V
    
    E
    
    DGraphSubTree
    
    G
    
    V
    
    E
    
    Tree
    
    V
    
    E
    
    S
    
    Tree
    
    V
    
    E
    
    Make
    
    Tree
    
    Make_from_dot_model
    
    Tree
    
    DGraphTreeModel
    
    S
    
    Tree
    
    V
    
    E
    
    TreeManipulation
    
    tree_model
    
    SubTreeMake
    
    Tree
    
    V
    
    E
    
    TreeManipulation
    
    tree_model
    
    SubTreeDotModelMake
    
    Tree
    
    V
    
    E
    
    TreeManipulation
    
    tree_model
    
    DGraphRandModel
    
    G
    
    V
    
    E
    
    GraphAttrs
    
    V
    
    E
- Sources
  - ocamlgraph
    
    blocks.ml
    
    builder.ml
    
    chaoticIteration.ml
    
    classic.ml
    
    clique.ml
    
    cliquetree.ml
    
    coloring.ml
    
    components.ml
    
    contraction.ml
    
    dGraphModel.ml
    
    dGraphRandModel.ml
    
    dGraphSubTree.ml
    
    dGraphTreeLayout.ml
    
    dGraphTreeModel.ml
    
    delaunay.ml
    
    dominator.ml
    
    dot.ml
    
    dot_lexer.ml
    
    dot_parser.ml
    
    fixpoint.ml
    
    flow.ml
    
    gmap.ml
    
    gml.ml
    
    graph.ml
    
    graph__.ml
    
    graphml.ml
    
    graphviz.ml
    
    imperative.ml
    
    kruskal.ml
    
    leaderlist.ml
    
    mcs_m.ml
    
    md.ml
    
    merge.ml
    
    mincut.ml
    
    minsep.ml
    
    nonnegative.ml
    
    oper.ml
    
    pack.ml
    
    path.ml
    
    persistent.ml
    
    prim.ml
    
    rand.ml
    
    strat.ml
    
    topological.ml
    
    traverse.ml
    
    util.ml
    
    weakTopological.ml
    
    xDot.ml
    
    xDotDraw.ml

Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module `Imperative.Digraph`Source

Imperative Directed Graphs.

include S

Source

module Concrete
  (V : Sig.COMPARABLE) : 
  Sig.I
    with type V.t = V.t
     and type V.label = V.t
     and type E.t = V.t * V.t
     and type E.label = unit

Imperative Unlabeled Graphs.

Source

module Abstract
  (V : Sig.ANY_TYPE) : 
  Sig.IM with type V.label = V.t and type E.label = unit

Abstract Imperative Unlabeled Graphs.

Source

module ConcreteLabeled
  (V : Sig.COMPARABLE)
  (E : Sig.ORDERED_TYPE_DFT) : 
  Sig.I
    with type V.t = V.t
     and type V.label = V.t
     and type E.t = V.t * E.t * V.t
     and type E.label = E.t

Imperative Labeled Graphs.

Source

module AbstractLabeled
  (V : Sig.ANY_TYPE)
  (E : Sig.ORDERED_TYPE_DFT) : 
  Sig.IM with type V.label = V.t and type E.label = E.t

Abstract Imperative Labeled Graphs.

Bidirectional graphs

Bidirectional graphs use more memory space (at worse the double) that standard concrete directional graphs. But accessing predecessors is in O(1) amortized instead of O(max(|V|,|E|)) and removing a vertex is in O(D*ln(D)) instead of O(|V|*ln(D)). D is the maximal degree of the graph.

Source

module ConcreteBidirectional
  (V : Sig.COMPARABLE) : 
  Sig.I
    with type V.t = V.t
     and type V.label = V.t
     and type E.t = V.t * V.t
     and type E.label = unit

Imperative Unlabeled, bidirectional graph.

Source

module ConcreteBidirectionalLabeled
  (V : Sig.COMPARABLE)
  (E : Sig.ORDERED_TYPE_DFT) : 
  Sig.I
    with type V.t = V.t
     and type V.label = V.t
     and type E.t = V.t * E.t * V.t
     and type E.label = E.t

Imperative Labeled and bidirectional graph.

package ocamlgraph

Module Imperative.DigraphSource

Bidirectional graphs

Module `Imperative.Digraph`Source