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 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
Iter Helpers
type 'a sequence_once
= 'a sequence
Iter that should be used only once
module Seq : sig ... end
Interfaces for graphs
This interface is designed for oriented graphs with labels on edges
type ('v, 'e) t
= 'v -> ('e * 'v) sequence
Directed graph with vertices of type
'v
and edges labeled withe'
type ('v, 'e) graph
= ('v, 'e) t
type 'v tag_set
=
{
get_tag : 'v -> bool;
set_tag : 'v -> unit;
Set tag for the given element
}
Tags
Mutable tags from values of type
'v
to tags of typebool
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
}
Table
Mutable table with keys
'k
and values'a
type 'a set
= ('a, unit) table
Mutable set
Bags of vertices
Traversals
module Traverse : sig ... end
Cycles
Topological Sort
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 verticesl
where each element ofl
is reachable fromseq
. The list is sorted in a way such that ifv -> v'
in the graph, thenv
comes beforev'
in the list (i.e. has a smaller index). Basicallyv -> v'
means thatv
is smaller thanv'
. See wikipedia.- parameter eq
equality predicate on vertices (default
(=)
).
- parameter rev
if true, the dependency relation is inverted (
v -> v'
meansv'
occurs beforev
).
- 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 hasv
as a root. The tabletbl
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 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.
- 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
=
{
graph : ('v, 'e) t;
add_edge : 'v -> 'e -> 'v -> unit;
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
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 froma
tob
.- 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.