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 -> intnumber_of_edges g returns the size of a graph g.
val number_of_nodes : t -> intnumber_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
val (>=) : t -> t -> boolval (<=) : t -> t -> boolval (<>) : t -> t -> boolval equal : t -> t -> boolval ascending : t -> t -> intval descending : t -> t -> intval between : t -> low:t -> high:t -> boolval clamp_exn : t -> min:t -> max:t -> tval clamp : t -> min:t -> max:t -> t Base__.Or_error.tval validate_lbound : min:t Base__.Maybe_bound.t -> t Base__.Validate.checkval validate_ubound : max:t Base__.Maybe_bound.t -> t Base__.Validate.checkval validate_bound :
min:t Base__.Maybe_bound.t ->
max:t Base__.Maybe_bound.t ->
t Base__.Validate.checkmodule Replace_polymorphic_compare : sig ... endinclude Core_kernel.Hashable.S with type t := t
include Core_kernel.Hashable.Common with type t := t
val compare : t -> t -> Base.Int.tval hash_fold_t :
Ppx_hash_lib.Std.Hash.state ->
t ->
Ppx_hash_lib.Std.Hash.stateval hash : t -> Ppx_hash_lib.Std.Hash.hash_valueval hashable : t Core_kernel__.Hashtbl.Hashable.tAll graphs are printable.
include Regular.Std.Printable.S with type t := t
val to_string : t -> stringto_string x returns a human-readable representation of x
val str : unit -> t -> stringstr () 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 -> stringval ppo : Core_kernel.Out_channel.t -> t -> unitwill 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.Pretty_printer.S with type t := t
val pp : Base__.Formatter.t -> t -> unit