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
type 'a sequence_once = 'a sequenceSequence that should be used only once
module Seq : sig ... endDirected graph with vertices of type 'v and edges of type e'
type ('v, 'e) graph = ('v, 'e) tMutable tags from values of type 'v to tags of type bool
type 'a set = ('a, unit) tableMutable set
val mk_table :
?eq:('k -> 'k -> bool) ->
?hash:('k -> int) ->
int ->
('k, 'a) tableval mk_map : ?cmp:('k -> 'k -> int) -> unit -> ('k, 'a) tableUse a Map.S underneath
val mk_queue : unit -> 'a bagval mk_stack : unit -> 'a bagval mk_heap : leq:('a -> 'a -> bool) -> 'a bagmk_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 ... endval topo_sort :
?eq:('v -> 'v -> bool) ->
?rev:bool ->
?tbl:'v set ->
graph:('v, 'e) t ->
'v sequence ->
'v listtopo_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
val topo_sort_tag :
?eq:('v -> 'v -> bool) ->
?rev:bool ->
tags:'v tag_set ->
graph:('v, 'e) t ->
'v sequence ->
'v listSame as topo_sort
module LazyTree : sig ... endval spanning_tree :
?tbl:'v set ->
graph:('v, 'e) t ->
'v ->
('v, 'e) LazyTree.tspanning_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.tHidden state for scc
val scc :
?tbl:('v, 'v scc_state) table ->
graph:('v, 'e) t ->
'v sequence ->
'v list sequence_onceStrongly connected components reachable from the given vertices. Each component is a list of vertices that are all mutually reachable in the graph. 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 ... endtype ('v, 'e) mut_graph =
< graph : ('v, 'e) t
; add_edge : 'e -> unit
; remove : 'v -> unit >val mk_mut_tbl :
?eq:('v -> 'v -> bool) ->
?hash:('v -> int) ->
int ->
('v, 'v * 'a * 'v) mut_graphmake 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 ... endval of_list : ?eq:('v -> 'v -> bool) -> ('v * 'v) list -> ('v, 'v * 'v) tof_list l makes a graph from a list of pairs of vertices. Each pair (a,b) is an edge from a to b.
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) tof_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) tn points to all its strict divisors