# Module DGraphModel.DotG

    module DotG: Sig.G
      with type V.label = XDot.node_layout and type E.label = XDot.edge_layout

## Graph structure

    type t

Abstract type of graphs

    module V: Sig.VERTEX

Vertices have type `V.t` and are labeled with type `V.label` (note that an implementation may identify the vertex with its label)

    type vertex = V.t

    module E: Sig.EDGE  with type vertex = vertex

Edges have type `E.t` and are labeled with type `E.label`.

    type edge = E.t

    val is_directed : bool

Is this an implementation of directed graphs?

## Size functions

    val is_empty : t -> bool

    val nb_vertex : t -> int

    val nb_edges : t -> int

Degree of a vertex

    val out_degree : t -> vertex -> int

`out_degree g v` returns the out-degree of `v` in `g`.
Raises `Invalid_argument` if `v` is not in `g`.

    val in_degree : t -> vertex -> int

`in_degree g v` returns the in-degree of `v` in `g`.
Raises `Invalid_argument` if `v` is not in `g`.

## Membership functions

    val mem_vertex : t -> vertex -> bool

    val mem_edge : t -> vertex -> vertex -> bool

    val mem_edge_e : t -> edge -> bool

    val find_edge : t -> vertex -> vertex -> edge

`find_edge g v1 v2` returns the edge from `v1` to `v2` if it exists. Unspecified behaviour if `g` has several edges from `v1` to `v2`.
Raises `Not_found` if no such edge exists.

    val find_all_edges : t -> vertex -> vertex -> edge list

`find_all_edges g v1 v2` returns all the edges from `v1` to `v2`.
Since ocamlgraph 1.8

## Successors and predecessors

You should better use iterators on successors/predecessors (see Section "Vertex iterators").

    val succ : t -> vertex -> vertex list

`succ g v` returns the successors of `v` in `g`.
Raises `Invalid_argument` if `v` is not in `g`.

    val pred : t -> vertex -> vertex list

`pred g v` returns the predecessors of `v` in `g`.
Raises `Invalid_argument` if `v` is not in `g`.
Labeled edges going from/to a vertex

    val succ_e : t -> vertex -> edge list

`succ_e g v` returns the edges going from `v` in `g`.
Raises `Invalid_argument` if `v` is not in `g`.

    val pred_e : t -> vertex -> edge list

`pred_e g v` returns the edges going to `v` in `g`.
Raises `Invalid_argument` if `v` is not in `g`.

## Graph iterators

    val iter_vertex : (vertex -> unit) -> t -> unit

Iter on all vertices of a graph.

    val fold_vertex : (vertex -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all vertices of a graph.

    val iter_edges : (vertex -> vertex -> unit) -> t -> unit

Iter on all edges of a graph. Edge label is ignored.

    val fold_edges : (vertex -> vertex -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all edges of a graph. Edge label is ignored.

    val iter_edges_e : (edge -> unit) -> t -> unit

Iter on all edges of a graph.

    val fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> 'a

Fold on all edges of a graph.

    val map_vertex : (vertex -> vertex) -> t -> t

Map on all vertices of a graph.

## Vertex iterators

Each iterator `iterator f v g` iters `f` to the successors/predecessors of `v` in the graph `g` and raises `Invalid_argument` if `v` is not in `g`. It is the same for functions `fold_*` which use an additional accumulator.

Time complexity for ocamlgraph implementations: operations on successors are in O(1) amortized for imperative graphs and in O(ln(|V|)) for persistent graphs while operations on predecessors are in O(max(|V|,|E|)) for imperative graphs and in O(max(|V|,|E|)*ln|V|) for persistent graphs.
iter/fold on all successors/predecessors of a vertex.

    val iter_succ : (vertex -> unit) -> t -> vertex -> unit

    val iter_pred : (vertex -> unit) -> t -> vertex -> unit

    val fold_succ : (vertex -> 'a -> 'a) -> t -> vertex -> 'a -> 'a

    val fold_pred : (vertex -> 'a -> 'a) -> t -> vertex -> 'a -> 'a

iter/fold on all edges going from/to a vertex.

    val iter_succ_e : (edge -> unit) -> t -> vertex -> unit

    val fold_succ_e : (edge -> 'a -> 'a) -> t -> vertex -> 'a -> 'a

    val iter_pred_e : (edge -> unit) -> t -> vertex -> unit

    val fold_pred_e : (edge -> 'a -> 'a) -> t -> vertex -> 'a -> 'a