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.
nodes g
returns all nodes of graph g
in an unspecified order
edges g
returns all edges of graph g
in an unspecified order
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
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)
.
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
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 : Base__.Import.Caml.Format.formatter -> t -> unit