package graphlib

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

Graph signature.

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.

type t

type of graph

type node

type of nodes

type edge

type of edges

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

Graph nodes.

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

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.Comparable.S with type t := t
include Base.Comparable.S with type t := t
include Base.Comparisons.S with type t := t
include Base.Comparisons.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 ~compare: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

between t ~low ~high means low <= t <= high

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
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.Hashable.S with type t := t
include Core_kernel.Hashable.Common with type t := t
val compare : t -> t -> Base.Int.t
val hash_fold_t : Base.Hash.state -> t -> Base.Hash.state
val hash : t -> Base.Hash.hash_value
val hashable : t Base.Hashable.t
module Table : Core_kernel.Hashtbl.S with type key = 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, surprisingly 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.Out_channel.t -> t -> unit

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

val pp_seq : Format.formatter -> t Core_kernel.Sequence.t -> unit

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.Pretty_printer.S with type t := t
val pp : Base.Formatter.t -> t -> unit
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