Module Object_graph.Make

Build a graph.

Parameters

module Node_key : Type.S
module Branch : Type.S

Signature

Directed graph

include Graph.Sig.I with type V.t = [ `Contents of Contents_key.t | `Node of Node_key.t | `Commit of Commit_key.t | `Branch of Branch.t ]
type t
module V : sig ... end
type vertex = V.t
module E : sig ... end
type edge = E.t
val is_directed : bool
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
val in_degree : t -> vertex -> int
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
val pred : t -> vertex -> vertex list
val succ_e : t -> vertex -> edge list
val pred_e : t -> vertex -> edge list
val iter_vertex : (vertex -> unit) -> t -> unit
val fold_vertex : (vertex -> 'a -> 'a) -> t -> 'a -> 'a
val iter_edges : (vertex -> vertex -> unit) -> t -> unit
val fold_edges : (vertex -> vertex -> 'a -> 'a) -> t -> 'a -> 'a
val iter_edges_e : (edge -> unit) -> t -> unit
val fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> 'a
val map_vertex : (vertex -> vertex) -> t -> t
val iter_succ : (vertex -> unit) -> t -> vertex -> unit
val iter_pred : (vertex -> unit) -> t -> vertex -> unit
val fold_succ : (vertex -> 'a -> 'a) -> t -> vertex -> 'a -> 'a
val fold_pred : (vertex -> 'a -> 'a) -> t -> vertex -> 'a -> 'a
val iter_succ_e : (edge -> unit) -> t -> vertex -> unit
val fold_succ_e : (edge -> 'a -> 'a) -> t -> vertex -> 'a -> 'a
val iter_pred_e : (edge -> unit) -> t -> vertex -> unit
val fold_pred_e : (edge -> 'a -> 'a) -> t -> vertex -> 'a -> 'a
val create : ?size:int -> unit -> t
val clear : t -> unit
val copy : t -> t
val add_vertex : t -> vertex -> unit
val remove_vertex : t -> vertex -> unit
val add_edge : t -> vertex -> vertex -> unit
val add_edge_e : t -> edge -> unit
val remove_edge : t -> vertex -> vertex -> unit
val remove_edge_e : t -> edge -> unit

Basic operations.

include Graph.Oper.S with type g := t
val transitive_closure : ?reflexive:bool -> t -> t
val add_transitive_closure : ?reflexive:bool -> t -> t
val transitive_reduction : ?reflexive:bool -> t -> t
val replace_by_transitive_reduction : ?reflexive:bool -> t -> t
val mirror : t -> t
val complement : t -> t
val intersect : t -> t -> t
val union : t -> t -> t
module Topological : sig ... end

Topological traversal

val vertex : t -> vertex list

Get all the vertices.

val edges : t -> (vertex * vertex) list

Get all the relations.

val closure : ?depth:int -> pred:(vertex -> vertex list) -> min:vertex list -> max:vertex list -> unit -> t

closure depth pred min max () creates the transitive closure graph of max using the predecessor relation pred. The graph is bounded by the min nodes and by depth.

Note: Both min and max are subsets of n.

val iter : ?cache_size:int -> ?depth:int -> pred:(vertex -> vertex list) -> min:vertex list -> max:vertex list -> node:(vertex -> unit) -> ?edge:(vertex -> vertex -> unit) -> skip:(vertex -> bool) -> rev:bool -> unit -> unit

iter depth min max node edge skip rev () iterates in topological order over the closure graph starting with the max nodes and bounded by the min nodes and by depth.

It applies three functions while traversing the graph: node on the nodes; edge n predecessor_of_n on the directed edges and skip n to not include a node n, its predecessors and the outgoing edges of n.

If rev is true (the default) then the graph is traversed in the reverse order: node n is applied only after it was applied on all its predecessors; edge n p is applied after node n. Note that edge n p is applied even if p is skipped.

cache_size is the size of the LRU cache used to store nodes already seen. If None (by default) every traversed nodes is stored (and thus no entries are never removed from the LRU).

val breadth_first_traversal : ?cache_size:int -> pred:(vertex -> vertex list) -> max:vertex list -> node:(vertex -> unit) -> unit -> unit

breadth_first_traversal ?cache_size pred max node () traverses the closure graph in breadth-first order starting with the max nodes. It applies node on the nodes of the graph while traversing it.

val output : Stdlib.Format.formatter -> (vertex * Graph.Graphviz.DotAttributes.vertex list) list -> (vertex * Graph.Graphviz.DotAttributes.edge list * vertex) list -> string -> unit

output ppf vertex edges name create aand dumps the graph contents on ppf. The graph is defined by its vertex and edges. name is the name of the output graph.

val min : t -> vertex list

Compute the minimum vertex.

val max : t -> vertex list

Compute the maximun vertex.

type dump = vertex list * (vertex * vertex) list

Expose the graph internals.

val export : t -> dump

Expose the graph as a pair of vertices and edges.

val import : dump -> t

Import a graph.

module Dump : Type.S with type t = dump

The base functions over graph internals.