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.

The node and label types are almost always have identical representation. For labeled graphs the comparison function for the node is different than the comparison function for the label, therefore it is a good idea to hide their representation equality in the interface.

type t

node type is opaque

type graph

node type is opaque

the type of the node graph

type label

the type of the node graph

the label type

type edge

the label type

the edge type

val create : label -> t

create x creates a node labeled with x.

For unlabeled graphs this is an identity function.

val label : t -> label

label n the label of the node n.

val mem : t -> graph -> bool

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

For labeled graphs the membership is tested without taking into account the label of the node.

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 for a graph with labeled nodes if node n is not in N(g) then returns g else returns graph g where node n is labeled with l.

For unlabeled graph returns g.

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 Core.Maybe_bound.t -> t Validate.check
val validate_ubound : max:t Core.Maybe_bound.t -> t Validate.check
val validate_bound : min:t Core.Maybe_bound.t -> max:t Core.Maybe_bound.t -> t Validate.check
include Core_kernel.Hashable.S with type t := t
include Ppx_compare_lib.Comparable.S with type t := t
val compare : t -> t -> int
include Ppx_hash_lib.Hashable.S with type t := 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.Hashtbl.S with type key = t
module Hash_set : Core.Hash_set.S with type elt = t
module Hash_queue : Core.Hash_queue.S with type key = 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