package owl-base

  1. Overview
  2. Docs
package owl-base
Legend:
Library
Module
Module type
Parameter
Class
Class type

Graph module supports basic operations on DAG.

Type definition
type order =
  1. | BFS
  2. | DFS
    (*

    Order to traverse a graph, BFS or DFS.

    *)
type traversal =
  1. | PreOrder
  2. | PostOrder
    (*

    Order of the function evaluation.

    *)
type dir =
  1. | Ancestor
  2. | Descendant
    (*

    Iteration direction, i.e. ancestors or descendants

    *)
type 'a node

type definition of a node

Obtaining properties
val id : 'a node -> int

``id x`` returns the id of node ``x``.

val name : 'a node -> string

``name x`` returns the name string of node ``x``.

val set_name : 'a node -> string -> unit

``set_name x s`` sets the name string of node ``x`` to ``s``.

val parents : 'a node -> 'a node array

``parents x`` returns the parents of node ``x``.

val set_parents : 'a node -> 'a node array -> unit

``set_parents x parents`` set ``x`` parents to ``parents``.

val children : 'a node -> 'a node array

``children x`` returns the children of node ``x``.

val set_children : 'a node -> 'a node array -> unit

``set_children x children`` sets ``x`` children to ``children``.

val indegree : 'a node -> int

``indegree x`` returns the in-degree of node ``x``.

val outdegree : 'a node -> int

``outdegree x`` returns the out-degree of node ``x``.

val degree : 'a node -> int

``degree x`` returns the total number of links of ``x``.

val attr : 'a node -> 'a

``attr x`` returns the ``attr`` field of node ``x``.

val set_attr : 'a node -> 'a -> unit

``set_attr x`` sets the ``attr`` field of node ``x``.

val num_ancestor : 'a node array -> int

``num_ancestor x`` returns the number of ancestors of ``x``.

val num_descendant : 'a node array -> int

``num_descendant x`` returns the number of descendants of ``x``.

val length : 'a node array -> int

``length x`` returns the total number of ancestors and descendants of ``x``.

Manipulation functions
val node : ?id:int -> ?name:string -> ?prev:'a node array -> ?next:'a node array -> 'a -> 'a node

``node ~id ~name ~prev ~next attr`` creates a node with given id and name string. The created node is also connected to parents in ``prev`` and children in ``next``. The ``attr`` will be saved in ``attr`` field.

val connect : 'a node array -> 'a node array -> unit

``connect parents children`` connects a set of parents to a set of children. The created links are the Cartesian product of parents and children. In other words, they are bidirectional links between parents and children.

NOTE: this function does not eliminate any duplicates in the array.

val connect_descendants : 'a node array -> 'a node array -> unit

``connect_descendants parents children`` connects parents to their children. This function creates unidirectional links from parents to children. In other words, this function save ``children`` to ``parent.next`` field.

val connect_ancestors : 'a node array -> 'a node array -> unit

``connect_ancestors parents children`` connects children to their parents. This function creates unidirectional links from children to parents. In other words, this function save ``parents`` to ``child.prev`` field.

val remove_node : 'a node -> unit

``remove_node x`` removes node ``x`` from the graph by disconnecting itself from all its parent nodes and child nodes.

val remove_edge : 'a node -> 'a node -> unit

``remove_edge src dst`` removes a link ``src -> dst`` from the graph. Namely, the correponding entry of ``dst`` in ``src.next`` and ``src`` in ``dst.prev`` will be removed. Note that it does not remove dst -> src if there exists one.

val replace_child : 'a node -> 'a node -> unit

``replace_child x y`` replaces ``x`` with ``y`` in ``x`` parents. Namely, ``x`` parents now make link to ``y`` rather than ``x`` in ``next`` field.

NOTE: The function does NOT make link from ``y`` to ``x`` parents. Namely, the ``prev`` field of ``y`` remains intact.

val replace_parent : 'a node -> 'a node -> unit

``replace_parent x y`` replaces ``x`` with ``y`` in ``x`` children. Namely, ``x`` children now make link to ``y`` rather than ``x`` in ``prev`` field.

NOTE: The function does NOT make link from ``y`` to ``x`` children. Namely, the ``next`` field of ``y`` remains intact.

val copy : ?dir:dir -> 'a node array -> 'a node array

``copy ~dir x`` makes a copy of ``x`` and all its ancestors (if ``dir = Ancestor``) or all its descendants (if ``dir = Descendant``).

Note that this function only makes a copy of the graph structure, ``attr`` fileds of the nodes in the new graph share the same memory with those in the original graph.

Iterators
val iter_ancestors : ?order:order -> ?traversal:traversal -> ('a node -> unit) -> 'a node array -> unit

Iterate the ancestors of a given node.

val iter_descendants : ?order:order -> ?traversal:traversal -> ('a node -> unit) -> 'a node array -> unit

Iterate the descendants of a given node.

val filter_ancestors : ('a node -> bool) -> 'a node array -> 'a node array

Filter the ancestors of a given node.

val filter_descendants : ('a node -> bool) -> 'a node array -> 'a node array

Iterate the descendants of a given node.

val fold_ancestors : ('b -> 'a node -> 'b) -> 'b -> 'a node array -> 'b

Fold the ancestors of a given node.

val fold_descendants : ('b -> 'a node -> 'b) -> 'b -> 'a node array -> 'b

Fold the descendants of a given node.

val iter_in_edges : ?order:order -> ('a node -> 'a node -> unit) -> 'a node array -> unit

Iterate all the in-edges of a given node.

val iter_out_edges : ?order:order -> ('a node -> 'a node -> unit) -> 'a node array -> unit

Iterate all the out-edges of a given node.

val fold_in_edges : ('b -> 'a node -> 'a node -> 'b) -> 'b -> 'a node array -> 'b

Fold all the in-edges of a given node.

val fold_out_edges : ('b -> 'a node -> 'a node -> 'b) -> 'b -> 'a node array -> 'b

Fold all the out-edges of a given node.

Helper functions
val topo_sort : 'a node array -> 'a node array

Topological sort of a given graph using a DFS order. Assumes that the graph is acyclic.

val pp_node : Stdlib.Format.formatter -> 'a node -> unit

Pretty print a given node.

val to_string : bool -> 'a node array -> string

Convert a given node to its string representaion.

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