Owl_graph (u.c3d6cc7b25d72e215baa811863351ebc.owl-base.0.3.8.doc.owl-base.Owl

Type definition

Sourcetype order =

| BFS
| DFS
(*
Order to traverse a graph, BFS or DFS.
*)

Sourcetype dir =

| Ancestor
| 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 parents : 'a node -> 'a node array

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

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

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

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

Manipulation functions

Source

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.

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.

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. Note that it does not remove dst -> src if there exists one.

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

Iterators

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

Iterate the ancestors of a given node.

Source

val iter_descendants : 
  ?order:order ->
  ('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.

Source

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

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

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

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

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