Control Flow Graph with a machine basic block as a node.
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.
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