# Module `CCGraph`

Simple Graph Interface

A collections of algorithms on (mostly read-only) graph structures. The user provides her own graph structure as a `('v, 'e) CCGraph.t`, where `'v` is the type of vertices and `'e` the type of edges (for instance, `'e = ('v * 'v)` is perfectly fine in many cases).

Such a `('v, 'e) CCGraph.t` structure is a record containing three functions: two relate edges to their origin and destination, and one maps vertices to their outgoing edges. This abstract notion of graph makes it possible to run the algorithms on any user-specific type that happens to have a graph structure.

Many graph algorithms here take an iterator of vertices as input. The helper module `Iter` contains basic functions for that, as does the `iter` library on opam. If the user only has a single vertex (e.g., for a topological sort from a given vertex), they can use `Iter.return x` to build a iter of one element.

status: unstable

• since 0.12

### Iter Helpers

`type 'a iter = ('a -> unit) -> unit`

A sequence of items of type `'a`, possibly infinite

• since 2.8
`type 'a iter_once = 'a iter`

Iter that should be used only once

• since 2.8
`exception Iter_once`

Raised when a sequence meant to be used once is used several times.

`module Iter : sig ... end`

### Interfaces for graphs

This interface is designed for oriented graphs with labels on edges

`type ('v, 'e) t = 'v -> ('e * 'v) iter`

Directed graph with vertices of type `'v` and edges labeled with `e'`

`type ('v, 'e) graph = ('v, 'e) t`
`val make : ('v -> ('e * 'v) iter) -> ('v, 'e) t`

Make a graph by providing the children function.

`type 'v tag_set = {`
1. `get_tag : 'v -> bool;`
2. `set_tag : 'v -> unit;`
(*

Set tag for the given element

*)
`}`

Tags

Mutable tags from values of type `'v` to tags of type `bool`

`type ('k, 'a) table = {`
1. `mem : 'k -> bool;`
2. `find : 'k -> 'a;`
(*
• raises Not_found

*)
3. `add : 'k -> 'a -> unit;`
(*

Erases previous binding

*)
`}`

Table

Mutable table with keys `'k` and values `'a`

`type 'a set = ('a, unit) table`

Mutable set

```val mk_table : eq:('k -> 'k -> bool) -> ?hash:('k -> int) -> int -> ('k, 'a) table```

Default implementation for Table: a `Hashtbl`.t.

`val mk_map : cmp:('k -> 'k -> int) -> unit -> ('k, 'a) table`

Use a `Map`.S underneath.

### Bags of vertices

`type 'a bag = {`
1. `push : 'a -> unit;`
2. `is_empty : unit -> bool;`
3. `pop : unit -> 'a;`
(*

raises some exception is empty

*)
`}`

Bag of elements of type `'a`

`val mk_queue : unit -> 'a bag`
`val mk_stack : unit -> 'a bag`
`val mk_heap : leq:('a -> 'a -> bool) -> 'a bag`

`mk_heap ~leq` makes a priority queue where `leq x y = true` means that `x` is smaller than `y` and should be prioritary.

### Traversals

`module Traverse : sig ... end`

### Cycles

```val is_dag : tbl:'v set -> eq:('v -> 'v -> bool) -> graph:('v, _) t -> 'v iter -> bool```

`is_dag ~graph vs` returns `true` if the subset of `graph` reachable from `vs` is acyclic.

• since 0.18

### Topological Sort

`exception Has_cycle`
```val topo_sort : eq:('v -> 'v -> bool) -> ?rev:bool -> tbl:'v set -> graph:('v, 'e) t -> 'v iter -> 'v list```

`topo_sort ~graph seq` returns a list of vertices `l` where each element of `l` is reachable from `seq`. The list is sorted in a way such that if `v -> v'` in the graph, then `v` comes before `v'` in the list (i.e. has a smaller index). Basically `v -> v'` means that `v` is smaller than `v'`. See wikipedia.

• parameter eq

equality predicate on vertices (default `(=)`).

• parameter rev

if true, the dependency relation is inverted (`v -> v'` means `v'` occurs before `v`).

• raises Has_cycle

if the graph is not a DAG.

```val topo_sort_tag : eq:('v -> 'v -> bool) -> ?rev:bool -> tags:'v tag_set -> graph:('v, 'e) t -> 'v iter -> 'v list```

Same as `topo_sort` but uses an explicit tag set.

• raises Has_cycle

if the graph is not a DAG.

### Lazy Spanning Tree

`module Lazy_tree : sig ... end`
```val spanning_tree : tbl:'v set -> graph:('v, 'e) t -> 'v -> ('v, 'e) Lazy_tree.t```

`spanning_tree ~graph v` computes a lazy spanning tree that has `v` as a root. The table `tbl` is used for the memoization part.

```val spanning_tree_tag : tags:'v tag_set -> graph:('v, 'e) t -> 'v -> ('v, 'e) Lazy_tree.t```

### Strongly Connected Components

`type 'v scc_state`

Hidden state for `scc`.

```val scc : tbl:('v, 'v scc_state) table -> graph:('v, 'e) t -> 'v iter -> 'v list iter_once```

Strongly connected components reachable from the given vertices. Each component is a list of vertices that are all mutually reachable in the graph. The components are explored in a topological order (if C1 and C2 are components, and C1 points to C2, then C2 will be yielded before C1). Uses Tarjan's algorithm.

• parameter tbl

table used to map nodes to some hidden state.

• raises Iter_once

if the result is iterated on more than once.

### Pretty printing in the DOT (graphviz) format

Example (print divisors from `42`):

``````let open CCGraph in
let open Dot in
with_out "/tmp/truc.dot"
(fun out ->
pp ~attrs_v:(fun i -> [`Label (string_of_int i)]) ~graph:divisors_graph out 42
)``````
`module Dot : sig ... end`

### Mutable Graph

`type ('v, 'e) mut_graph = {`
1. `graph : ('v, 'e) t;`
2. `add_edge : 'v -> 'e -> 'v -> unit;`
3. `remove : 'v -> unit;`
`}`
```val mk_mut_tbl : eq:('v -> 'v -> bool) -> ?hash:('v -> int) -> int -> ('v, 'a) mut_graph```

Make a new mutable graph from a Hashtbl. Edges are labelled with type `'a`.

### Immutable Graph

A classic implementation of a graph structure on totally ordered vertices, with unlabelled edges. The graph allows to add and remove edges and vertices, and to iterate on edges and vertices.

`module type MAP = sig ... end`
`module Map (O : Stdlib.Map.OrderedType) : MAP with type vertex = O.t`

### Misc

`val of_list : eq:('v -> 'v -> bool) -> ('v * 'v) list -> ('v, unit) t`

`of_list l` makes a graph from a list of pairs of vertices. Each pair `(a,b)` is an edge from `a` to `b`.

• parameter eq

equality used to compare vertices.

`val of_hashtbl : ('v, 'v list) Stdlib.Hashtbl.t -> ('v, unit) t`

`of_hashtbl tbl` makes a graph from a hashtable that maps vertices to lists of children.

`val of_fun : ('v -> 'v list) -> ('v, unit) t`

`of_fun f` makes a graph out of a function that maps a vertex to the list of its children. The function is assumed to be deterministic.

`val divisors_graph : (int, unit) t`

`n` points to all its strict divisors.