package graphlib

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

Graph nodes.

Semantics of operations is denoted using mathematical model, described in Graph interface.

type t = node

node type is opaque

type graph = t

node type is opaque

type label
type edge = edge
val create : label -> t

create label creates a new node, and associates it with a a given label.

val label : t -> label

label n returns a value associated with a node n.

val mem : t -> graph -> bool

mem n g is true if n is a member of nodes N of graph g.

val succs : t -> graph -> t Regular.Std.seq

succs node graph returns a sequence of successors of a node in a a given graph

val preds : t -> graph -> t Regular.Std.seq

preds node graph returns a sequence of predecessors of a node in a a given graph

val inputs : t -> graph -> edge Regular.Std.seq

inputs node graph is incomming edges of a node in graph

val outputs : t -> graph -> edge Regular.Std.seq

outputs node graph is outcomming edges of a node in graph

val degree : ?dir:[ `In | `Out ] -> t -> graph -> int

degree ?dir n when in_or_out is `In then returns the amount of incomming edges, otherwise returns the amount of outcomming edges. If parameter dir is left absent, then return the amount of adjacent nodes (i.e., a sum of incomming and outcomming edges).

val insert : t -> graph -> graph

insert n g returns new graph g' that has a set of nodes N extended with node n. If N was contained n, then the g == g'. Use update to change existing nodes.

Postconditions:

          - N(g') = N(g) ∪ {n}.
val update : t -> label -> graph -> graph

update n l g if node n is not in N(g) then return g, else return graph g where node n is labeled with l.

Postconditions:

          - n ∉ N(g) -> n ∉ N(g').
          - n ∈ N(g) → ν(g')n = l.
val remove : t -> graph -> graph

remove n g returns graph g', with a node n removed from a set of nodes N.

Postconditions:

          - E(g) ⊆ E(g')
          - N(g) ⊆ N(g')
          - N(g') = N(g) \ {n}.
val has_edge : t -> t -> graph -> bool

has_edge x y g is true iff (x,y) ∈ E.

val edge : t -> t -> graph -> edge option

edge x y g if graph g has an edge between nodes x and y then it is returned.

node provides common data structures, like Table, Map, Set, Hash_set, etc.

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