graphlib 2.5.0 · OCaml Package

Graph nodes.

type t = node

node type is opaque

type graph = t

node type is opaque

the type of the node graph

type label

the type of the node graph

the label type

type edge = 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 comparator : (t, comparator_witness) Base.Comparator.comparator

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

module Replace_polymorphic_compare : 
  Base.Comparable.Polymorphic_compare with type t := t

module Map : 
  Core.Map.S
    with type Key.t = t
    with type Key.comparator_witness = comparator_witness

module Set : 
  Core.Set.S
    with type Elt.t = t
    with type Elt.comparator_witness = comparator_witness

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

package graphlib