package graphlib

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

Of_ocamlgraph(O) creates an adapter module, that implements Graphlib interface on top of the module implementing OCamlGraph interface.

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

module G : Graph.Sig.P

Signature

type t = G.t

type of graph

type node = G.V.t

type of nodes

type edge = G.E.t

type of edges

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

Graph nodes.

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

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
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
val descending : t -> t -> int
val between : t -> low:t -> high:t -> bool
val clamp_exn : t -> min:t -> max:t -> t
val clamp : t -> min:t -> max:t -> t Core_kernel.Or_error.t
module Replace_polymorphic_compare : sig ... end
type comparator_witness
val comparator : (t, comparator_witness) Core_kernel.Comparator.comparator
val validate_lbound : min:t Core_kernel.Maybe_bound.t -> t Core_kernel.Validate.check
val validate_ubound : max:t Core_kernel.Maybe_bound.t -> t Core_kernel.Validate.check
val validate_bound : min:t Core_kernel.Maybe_bound.t -> max:t Core_kernel.Maybe_bound.t -> t Core_kernel.Validate.check
module Map : sig ... end
module Set : sig ... end
include Core_kernel.Std.Hashable.S with type t := t
val hash : t -> int
val compare : t -> t -> int
val hashable : t Core_kernel.Std.Hashable.Hashtbl.Hashable.t
module Table : sig ... end
module Hash_set : sig ... end
module Hash_queue : sig ... end

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

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

val pp_seq : Format.formatter -> t Core_kernel.Std.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.Std.Pretty_printer.S with type t := t
val pp : Format.formatter -> t -> unit