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
module Seq : sig ... end
This interface is designed for oriented graphs with labels on edges
type ('k, 'a) table
=
{
mem : 'k ‑> bool; | |
find : 'k ‑> 'a; | (**
*) |
add : 'k ‑> 'a ‑> unit; | (** Erases previous binding *) |
}
Mutable table with keys 'k
and values 'a
val mk_table : eq:('k ‑> 'k ‑> bool) ‑> ?hash:('k ‑> int) ‑> int ‑> ('k, 'a) table
Default implementation for table: a Hashtbl.t.
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.
module Traverse : sig ... end
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.
(=)
).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 topo_sort but uses an explicit tag set.
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
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.
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
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
.
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
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
.
val of_hashtbl : ('v, 'v list) 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.