Module Owl_graphSource

Graph module supports basic operations on DAG.

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

    Order to traverse a graph, BFS or DFS.

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

    Order of the function evaluation.

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

    Iteration direction, i.e. ancestors or descendants

    *)
Sourcetype 'a node

type definition of a node

Obtaining properties
Sourceval id : 'a node -> int

id x returns the id of node x.

Sourceval name : 'a node -> string

name x returns the name string of node x.

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

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

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

parents x returns the parents of node x.

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

set_parents x parents set x parents to parents.

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

children x returns the children of node x.

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

set_children x children sets x children to children.

Sourceval indegree : 'a node -> int

indegree x returns the in-degree of node x.

Sourceval outdegree : 'a node -> int

outdegree x returns the out-degree of node x.

Sourceval degree : 'a node -> int

degree x returns the total number of links of x.

Sourceval attr : 'a node -> 'a

attr x returns the attr field of node x.

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

set_attr x sets the attr field of node x.

Sourceval num_ancestor : 'a node array -> int

num_ancestor x returns the number of ancestors of x.

Sourceval num_descendant : 'a node array -> int

num_descendant x returns the number of descendants of x.

Sourceval length : 'a node array -> int

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

Manipulation functions
Sourceval 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.

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

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

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

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

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

remove_edge src dst removes a link src -> dst from the graph. Namely, the corresponding 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.

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

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

Sourceval 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 fields of the nodes in the new graph share the same memory with those in the original graph.

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

Iterate the ancestors of a given node.

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

Iterate the descendants of a given node.

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

Filter the ancestors of a given node.

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

Iterate the descendants of a given node.

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

Fold the ancestors of a given node.

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

Fold the descendants of a given node.

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

Iterate all the in-edges of a given node.

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

Iterate all the out-edges of a given node.

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

Fold all the in-edges of a given node.

Sourceval 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
Sourceval topo_sort : 'a node array -> 'a node array

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

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

Pretty print a given node.

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

Convert a given node to its string representation.