Module CCGraph

module CCGraph: sig .. end

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 a sequence of vertices as input. If the user only has a single vertex (e.g., for a topological sort from a given vertex), she can use Seq.return x to build a sequence of one element.

status: unstable
Since 0.12

type 'a sequence = ('a -> unit) -> unit

A sequence of items of type 'a, possibly infinite

type 'a sequence_once = 'a sequence

Sequence that should be used only once

exception Sequence_once

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

module Seq: sig .. end

Interfaces for graphs

type ('v, 'e) t = {

	`children : 'v -> 'e sequence;`
	`origin : 'e -> 'v;`
	`dest : 'e -> 'v;`

}

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

type ('v, 'e) graph = ('v, 'e) t

val make : origin:('e -> 'v) ->
       dest:('e -> 'v) -> ('v -> 'e sequence) -> ('v, 'e) t

Make a graph by providing its fields
Since 0.16

val make_labelled_tuple : ('v -> ('a * 'v) sequence) -> ('v, 'v * 'a * 'v) t

Make a graph with edges being triples (origin,label,dest)
Since 0.16

val make_tuple : ('v -> 'v sequence) -> ('v, 'v * 'v) t

Make a graph with edges being pairs (origin,dest)
Since 0.16

type 'v tag_set = {

	`get_tag : 'v -> bool;`
	`set_tag : 'v -> unit;`	`(*`	Set tag for the given element	`*)`

}

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

type ('k, 'a) table = {

`mem : 'k -> bool;`
`find : 'k -> 'a;`	`(*`	Raises `Not_found` if element not added before	`*)`
`add : 'k -> 'a -> unit;`	`(*`	Erases previous binding	`*)`

}

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 CCGraph.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 = {

`push : 'a -> unit;`
`is_empty : unit -> bool;`
`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 ->
       graph:('v, 'a) t -> 'v sequence -> 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 sequence -> '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
Raises Has_cycle if the graph is not a DAG

eq : equality predicate on vertices (default (=))

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

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

Same as CCGraph.topo_sort but uses an explicit tag set

Lazy Spanning Tree

module LazyTree: sig .. end

val spanning_tree : ?tbl:'v set ->
       graph:('v, 'e) t -> 'v -> ('v, 'e) LazyTree.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) LazyTree.t

Strongly Connected Components

type 'v scc_state

Hidden state for CCGraph.scc

val scc : ?tbl:('v, 'v scc_state) table ->
       graph:('v, 'e) t ->
       'v sequence -> 'v list sequence_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
Raises Sequence_once if the result is iterated on more than once.

tbl : table used to map nodes to some hidden state

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 = <

	`add_edge : 'e -> unit;`
	`graph : ('v, 'e) t;`
	`remove : 'v -> unit;`

val mk_mut_tbl : ?eq:('v -> 'v -> bool) ->
       ?hash:('v -> int) -> int -> ('v, 'v * 'a * 'v) 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 : Map.OrderedType) : MAP  with type vertex = O.t

Misc

val of_list : ?eq:('v -> 'v -> bool) -> ('v * 'v) list -> ('v, 'v * 'v) 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.

eq : equality used to compare vertices

val of_hashtbl : ('v, 'v list) Hashtbl.t -> ('v, 'v * 'v) t

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

val of_fun : ('v -> 'v list) -> ('v, 'v * 'v) 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, int * int) t

n points to all its strict divisors