### Graph structure

`type t`

abstract type of graphs

`module V : sig ... end`

Vertices

`type vertex = V.t`
`module E : sig ... end`

Edges

`type edge = E.t`
`val is_directed : bool`

is this an implementation of directed graphs?

### Graph constructors and destructors

`val create : ?size:int -> unit -> t`

Return an empty graph. Optionally, a size can be given, which should be on the order of the expected number of vertices that will be in the graph (for hash tables-based implementations). The graph grows as needed, so `size` is just an initial guess.

`val clear : t -> unit`

Remove all vertices and edges from the given graph.

- since ocamlgraph 1.4

`val copy : t -> t`

`copy g` returns a copy of `g`. Vertices and edges (and eventually marks, see module `Mark`) are duplicated.

`val add_vertex : t -> V.t -> unit`

`add_vertex g v` adds the vertex `v` from the graph `g`. Do nothing if `v` is already in `g`.

`val remove_vertex : t -> V.t -> unit`

`remove g v` removes the vertex `v` from the graph `g` (and all the edges going from `v` in `g`). Do nothing if `v` is not in `g`.

`val add_edge : t -> V.t -> V.t -> unit`

`add_edge g v1 v2` adds an edge from the vertex `v1` to the vertex `v2` in the graph `g`. Add also `v1` (resp. `v2`) in `g` if `v1` (resp. `v2`) is not in `g`. Do nothing if this edge is already in `g`.

`val add_edge_e : t -> E.t -> unit`

`add_edge_e g e` adds the edge `e` in the graph `g`. Add also `E.src e` (resp. `E.dst e`) in `g` if `E.src e` (resp. `E.dst e`) is not in `g`. Do nothing if `e` is already in `g`.

`val remove_edge : t -> V.t -> V.t -> unit`

`remove_edge g v1 v2` removes the edge going from `v1` to `v2` from the graph `g`. Do nothing if this edge is not in `g`.

- raises `Invalid_argument`

  if `v1` or `v2` are not in `g`.

`val remove_edge_e : t -> E.t -> unit`

`remove_edge_e g e` removes the edge `e` from the graph `g`. Do nothing if `e` is not in `g`.

- raises `Invalid_argument`

  if `E.src e` or `E.dst e` are not in `g`.

`module Mark : sig ... end`

Vertices contains integers marks, which can be set or used by some algorithms (see for instance module `Marking` below)

### 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 -> V.t -> 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 -> V.t -> 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 -> V.t -> bool`
`val mem_edge : t -> V.t -> V.t -> bool`
`val mem_edge_e : t -> E.t -> bool`
`val find_edge : t -> V.t -> V.t -> E.t`
`val find_all_edges : t -> V.t -> V.t -> E.t list`

### Successors and predecessors of a vertex

`val succ : t -> V.t -> V.t list`

`succ g v` returns the successors of `v` in `g`.

- raises `Invalid_argument`

  if `v` is not in `g`.

`val pred : t -> V.t -> V.t 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 -> V.t -> E.t 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 -> V.t -> E.t list`

`pred_e g v` returns the edges going to `v` in `g`.

- raises `Invalid_argument`

  if `v` is not in `g`.

### Graph iterators

iter/fold on all vertices/edges of a graph

`val iter_vertex : (V.t -> unit) -> t -> unit`
`val iter_edges : (V.t -> V.t -> unit) -> t -> unit`
`val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a`
`val fold_edges : (V.t -> V.t -> 'a -> 'a) -> t -> 'a -> 'a`
`val map_vertex : (V.t -> V.t) -> t -> t`

map iterator on vertex

iter/fold on all labeled edges of a graph

`val iter_edges_e : (E.t -> unit) -> t -> unit`
`val fold_edges_e : (E.t -> 'a -> 'a) -> t -> 'a -> 'a`

### 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`.

iter/fold on all successors/predecessors of a vertex.

`val iter_succ : (V.t -> unit) -> t -> V.t -> unit`
`val iter_pred : (V.t -> unit) -> t -> V.t -> unit`
`val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a`
`val fold_pred : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a`

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

`val iter_succ_e : (E.t -> unit) -> t -> V.t -> unit`
`val fold_succ_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a`
`val iter_pred_e : (E.t -> unit) -> t -> V.t -> unit`
`val fold_pred_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a`

### Basic operations

`val find_vertex : t -> int -> V.t`

`vertex g i` returns a vertex of label `i` in `g`. The behaviour is unspecified if `g` has several vertices with label `i`. Note: this function is inefficient (linear in the number of vertices); you should better keep the vertices as long as you create them.

`val transitive_closure : ?reflexive:bool -> t -> t`

`transitive_closure ?reflexive g` returns the transitive closure of `g` (as a new graph). Loops (i.e. edges from a vertex to itself) are added only if `reflexive` is `true` (default is `false`).

`val add_transitive_closure : ?reflexive:bool -> t -> t`

`add_transitive_closure ?reflexive g` replaces `g` by its transitive closure. Meaningless for persistent implementations (then acts as `transitive_closure`).

`val transitive_reduction : ?reflexive:bool -> t -> t`

`transitive_reduction ?reflexive g` returns the transitive reduction of `g` (as a new graph). Loops (i.e. edges from a vertex to itself) are removed only if `reflexive` is `true` (default is `false`).

`val replace_by_transitive_reduction : ?reflexive:bool -> t -> t`

`replace_by_transitive_reduction ?reflexive g` replaces `g` by its transitive reduction. Meaningless for persistent implementations (then acts as `transitive_reduction`).

`val mirror : t -> t`

`mirror g` returns a new graph which is the mirror image of `g`: each edge from `u` to `v` has been replaced by an edge from `v` to `u`. For undirected graphs, it simply returns a copy of `g`.

`val complement : t -> t`

`complement g` builds a new graph which is the complement of `g`: each edge present in `g` is not present in the resulting graph and vice-versa. Edges of the returned graph are unlabeled.

`val intersect : t -> t -> t`

`intersect g1 g2` returns a new graph which is the intersection of `g1` and `g2`: each vertex and edge present in `g1` *and* `g2` is present in the resulting graph.

`val union : t -> t -> t`

`union g1 g2` returns a new graph which is the union of `g1` and `g2`: each vertex and edge present in `g1` *or* `g2` is present in the resulting graph.

### Traversal

`module Dfs : sig ... end`

Depth-first search

`module Bfs : sig ... end`

Breadth-first search

`module Marking : sig ... end`

Graph traversal with marking

`module Coloring : sig ... end`

Coloring

### Graph generators

`module Classic : sig ... end`

Classic graphs

`module Rand : sig ... end`

Random graphs

`module Components : sig ... end`

Strongly connected components

### Classical algorithms

`val shortest_path : t -> V.t -> V.t -> E.t list * int`

Dijkstra's shortest path algorithm. Weights are the labels.

`val ford_fulkerson : t -> V.t -> V.t -> (E.t -> int) * int`

Ford Fulkerson maximum flow algorithm

`val goldberg_tarjan : t -> V.t -> V.t -> (E.t -> int) * int`

Goldberg-Tarjan maximum flow algorithm

`val bellman_ford : t -> V.t -> E.t list`

`bellman_ford g v` finds a negative cycle from `v`, and returns it, or raises `Not_found` if there is no such cycle

`val bfs_0_1 : (V.t -> int -> unit) -> t -> zero:(E.t -> bool) -> V.t -> unit`

0-1 BFS from a given source. Function `zero` indicates 0-edges.

`module PathCheck : sig ... end`

Path checking

`module Topological : sig ... end`

Topological order

`module Eulerian : sig ... end`

Eulerian path

`val spanningtree : t -> E.t list`

Kruskal algorithm

### Input / Output

`val dot_output : t -> string -> unit`

DOT output in a file

`val display_with_gv : t -> unit`

Displays the given graph using the external tools "dot" and "gv" and returns when gv's window is closed

`val parse_gml_file : string -> t`
`val parse_dot_file : string -> t`
`val print_gml : Stdlib.Format.formatter -> t -> unit`
`val print_gml_file : t -> string -> unit`