Graph

This document is auto-generated for Owl’s APIs. #46 entries have been extracted.

Github: {Signature} {Implementation}

Type definition

type order = BFS | DFS

Order to traverse a graph, BFS or DFS.

type traversal = PreOrder | PostOrder

Order of the function evaluation.

type dir = Ancestor | 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.

source code

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

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

source code

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

parents x returns the parents of node x.

source code

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

set_parents x parents set x parents to parents.

source code

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

children x returns the children of node x.

source code

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

set_children x children sets x children to children.

source code

val indegree : 'a node -> int

indegree x returns the in-degree of node x.

source code

val outdegree : 'a node -> int

outdegree x returns the out-degree of node x.

source code

val degree : 'a node -> int

degree x returns the total number of links of x.

source code

val attr : 'a node -> 'a

attr x returns the attr field of node x.

source code

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

set_attr x sets the attr field of node x.

source code

val num_ancestor : 'a node array -> int

num_ancestor x returns the number of ancestors of x.

source code

val num_descendant : 'a node array -> int

num_descendant x returns the number of descendants of x.

source code

val length : 'a node array -> int

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

source code

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.

source code

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.

source code

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.

source code

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.

source code

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.

source code

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.

source code

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.

source code

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.

source code

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.

source code

Iterators

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

Iterate the ancestors of a given node.

source code

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

Iterate the descendants of a given node.

source code

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

Filter the ancestors of a given node.

source code

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

Iterate the descendants of a given node.

source code

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

Fold the ancestors of a given node.

source code

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

Fold the descendants of a given node.

source code

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

Iterate all the in-edges of a given node.

source code

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

Iterate all the out-edges of a given node.

source code

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

Fold all the in-edges of a given node.

source code

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

Fold all the out-edges of a given node.

source code

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.

source code

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

Pretty print a given node.

source code

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

Convert a given node to its string representaion.

source code