package containers

  1. Overview
  2. Docs
package containers
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module CCGraphSource

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

Sourcetype 'a iter = ('a -> unit) -> unit

A sequence of items of type 'a, possibly infinite

  • since 2.8
Sourcetype 'a iter_once = 'a iter

Iter that should be used only once

  • since 2.8
Sourcetype 'a sequence = ('a -> unit) -> unit
  • deprecated see iter
Sourcetype 'a sequence_once = 'a iter
  • deprecated see iter_once
Sourceexception Iter_once

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

Sourcemodule Iter : sig ... end
Sourcemodule Seq = Iter

Interfaces for graphs

This interface is designed for oriented graphs with labels on edges

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

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

Sourcetype ('v, 'e) graph = ('v, 'e) t
Sourceval make : ('v -> ('e * 'v) iter) -> ('v, 'e) t

Make a graph by providing the children function.

Sourcetype '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

Sourcetype ('k, 'a) table = {
  1. mem : 'k -> bool;
  2. find : 'k -> 'a;
    (**)
  3. add : 'k -> 'a -> unit;
    (*

    Erases previous binding

    *)
}

Table

Mutable table with keys 'k and values 'a

Sourcetype 'a set = ('a, unit) table

Mutable set

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

Default implementation for Table: a Hashtbl.t.

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

Use a Map.S underneath.

Bags of vertices

Sourcetype '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

Sourceval mk_queue : unit -> 'a bag
Sourceval mk_stack : unit -> 'a bag
Sourceval 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

Sourcemodule Traverse : sig ... end

Cycles

Sourceval 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

Sourceexception Has_cycle
Sourceval 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).

Sourceval 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.

Lazy Spanning Tree

Sourcemodule Lazy_tree : sig ... end
Sourceval 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.

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

Strongly Connected Components

Sourcetype 'v scc_state

Hidden state for scc.

Sourceval 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
    )
Sourcemodule Dot : sig ... end

Mutable Graph

Sourcetype ('v, 'e) mut_graph = {
  1. graph : ('v, 'e) t;
  2. add_edge : 'v -> 'e -> 'v -> unit;
  3. remove : 'v -> unit;
}
Sourceval 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.

Sourcemodule type MAP = sig ... end
Sourcemodule Map (O : Map.OrderedType) : MAP with type vertex = O.t

Misc

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval divisors_graph : (int, unit) t

n points to all its strict divisors.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct