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[@@warning "-D"] 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.

A graph is a set of relations between objects, defined as a pair of two sets

G = (V,E).

where $V$ is a set of vertices and E is a set of vertices, which is a subset of V x V, therefore a more precise definition is a 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.

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