package graphlib

  1. Overview
  2. Docs
package graphlib
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 type is opaque

type graph

node type is opaque

type label
type 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 incoming 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 incoming 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 incoming 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.Comparable.S with type t := t
include Base.Comparable.S with type t := t
include Base.Comparisons.S with type t := t
include Base.Comparisons.Infix 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

ascending is identical to compare. descending x y = ascending y x. These are intended to be mnemonic when used like List.sort ~compare: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

between t ~low ~high means low <= t <= high

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).

val clamp : t -> min:t -> max:t -> t Base.Or_error.t
include Base.Comparator.S with type t := t
type comparator_witness
val validate_lbound : min:t Base.Maybe_bound.t -> t Base.Validate.check
val validate_ubound : max:t Base.Maybe_bound.t -> t Base.Validate.check
val validate_bound : min:t Base.Maybe_bound.t -> max:t Base.Maybe_bound.t -> t Base.Validate.check
include Core_kernel.Hashable.S with type t := t
include Core_kernel.Hashable.Common with type t := t
val compare : t -> t -> Base.Int.t
val hash_fold_t : Base.Hash.state -> t -> Base.Hash.state
val hash : t -> Base.Hash.hash_value
val hashable : t Base.Hashable.t
module Table : Core_kernel.Hashtbl.S with type key = t
module Hash_set : Core_kernel.Hash_set.S with type elt = t
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct