package graphlib

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type

Make(Node)(Edge) creates a module that implements Graph interface and has unlabeled nodes of type Node.t and edges labeled with Edge.t

In Core_kernel basically any type that is reasonable to be used as a graph node, satisfies the Opaque.S interface. So, a new graph structure can be implemented directly, e.g.,

module G = Graphlib.Make(Int64)(Unit)

If a type doesn't satisfy the Opaque interface, then it can be easily derived with Opaque.Make if compare and hash functions are provided.

Graph is mathematical data structure that is used to represent relations between elements of a set. Usually, graph is defined as an ordered pair of two sets - a set of vertices and a set of edges that is a 2-subset of the set of nodes,

G = (V,E).

In Graphlib vertices (called nodes in our parlance) and edges are labeled. That means that we can associate data with edges and nodes. Thus graph should be considered as an associative data structure. And from mathematics perspective graph is represented as an ordered 6-tuple, consisting of a set of nodes, edges, node labels, edge labels, and two functions that maps nodes and edges to their corresponding labels:

G = (N, E, N', E', ν : N -> N', ε : E -> E'),

where set E is a subset of N × N .

With this general framework an unlabeled graph can be represented as:

G = (N, E, N, E, ν = λx.x, ε = λx.x)

Another possible representation of an unlabeled graph would be:

G = (N, E, {u}, {v}, ν = λx.u, ε = λx.v).

Implementations are free to choose any suitable representation of graph data structure, if it conforms to the graph signature and all operations follows the described semantics and properties of a graph structure are preserved.

The axiomatic semantics of operations on a graph is described by a set of postconditions. To describe the semantics of an operation in terms of input and output arguments, we project graphs to its fields with the following notation <field>(<graph>), e.g., N(g) is a set of nodes of graph g.

Only the strongest postcondition is specified, e.g., if it is specified that νn = l, then it also means that

n ∈ N ∧ ∃u((u,v) ∈ E ∨ (v,u) ∈ E) ∧ l ∈ N' ∧ ...

In other words the structure G of the graph G is an invariant that is always preserved.

Parameters

Signature

type t

type of graph

type node = Node.t

type of nodes

type edge

type of edges

module Node : Node with type graph = t and type t = node and type edge = edge with type label = Node.t

Graph nodes.

module Edge : Edge with type graph = t and type t = edge and type node = node with type label = Edge.t

Graph edges

val empty : t

empty is an empty graph

val nodes : t -> node Regular.Std.seq

nodes g returns all nodes of graph g in an unspecified order

val edges : t -> edge Regular.Std.seq

edges g returns all edges of graph g in an unspecified order

val is_directed : bool

is_directed is true if graph is a directed graph.

val number_of_edges : t -> int

number_of_edges g returns the size of a graph g.

val number_of_nodes : t -> int

number_of_nodes g returns the order of a graph g

All graphs provides a common interface for any opaque data structure

include Regular.Std.Opaque.S with type t := t
include Core_kernel.Std.Comparable.S with type t := t
include Base.Comparable_intf.S with type t := t
include Base.Comparable_intf.Polymorphic_compare with type t := t
include Base.Polymorphic_compare_intf.Infix with type t := t
val (>=) : t -> t -> bool
val (<=) : t -> t -> bool
val (=) : t -> t -> bool
val (>) : t -> t -> bool
val (<) : t -> t -> bool
val (<>) : t -> t -> bool
val equal : t -> t -> bool
val min : t -> t -> t
val max : t -> t -> t
val ascending : t -> t -> int

ascending is identical to compare. descending x y = ascending y x. These are intended to be mnemonic when used like List.sort ~cmp:ascending and List.sort ~cmp:descending, since they cause the list to be sorted in ascending or descending order, respectively.

val descending : t -> t -> int
val between : t -> low:t -> high:t -> bool
val clamp_exn : t -> min:t -> max:t -> t

clamp_exn t ~min ~max returns t', the closest value to t such that between t' ~low:min ~high:max is true.

Raises if not (min <= max).

val clamp : t -> min:t -> max:t -> t Base.Or_error.t
include Base.Comparator.S with type t := t
type comparator_witness
include Base.Comparable_intf.Validate with type t := t
val validate_lbound : min:t Base.Maybe_bound.t -> t Base.Validate.check
val validate_ubound : max:t Base.Maybe_bound.t -> t Base.Validate.check
val validate_bound : min:t Base.Maybe_bound.t -> max:t Base.Maybe_bound.t -> t Base.Validate.check
include Core_kernel.Std.Hashable.S with type t := t
include Core_kernel.Hashable.Common with type t := t
val hash : t -> Base.Int.t
val compare : t -> t -> Base.Int.t
module Hash_set : Core_kernel.Hash_set.S with type elt = t

All graphs are printable.

include Regular.Std.Printable.S with type t := t
val to_string : t -> string

to_string x returns a human-readable representation of x

val str : unit -> t -> string

str () t is formatted output function that matches "%a" conversion format specifier in functions, that prints to string, e.g., sprintf, failwithf, errorf and, suprisingly all Lwt printing function, including Lwt_io.printf and logging (or any other function with type ('a,unit,string,...) formatN`. Example:

Or_error.errorf "type %a is not valid for %a"
Type.str ty Exp.str exp
val pps : unit -> t -> string

synonym for str

val ppo : Core_kernel.Std.Out_channel.t -> t -> unit

will print to a standard output_channel, useful for using in printf, fprintf, etc.

prints a sequence of values of type t

this will include pp function from Core that has type t printer, and can be used in Format.printf family of functions

include Core_kernel.Std.Pretty_printer.S with type t := t
val pp : Caml.Format.formatter -> t -> unit