Up  

Module Builder.S.G


module G: Sig.G

Graph structure


type t
Abstract type of graphs
module V: Sig.VERTEX
Vertices have type V.t and are labeled with type V.label (note that an implementation may identify the vertex with its label) 
type vertex = V.t 
module E: Sig.EDGE  with type vertex = vertex
Edges have type E.t and are labeled with type E.label. 
type edge = E.t 
val is_directed : bool
Is this an implementation of directed graphs?

Size functions


val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int

Degree of a vertex
val out_degree : t -> vertex -> int
out_degree g v returns the out-degree of v in g.
Raises Invalid_argument if v is not in g.
val in_degree : t -> vertex -> int
in_degree g v returns the in-degree of v in g.
Raises Invalid_argument if v is not in g.

Membership functions


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
find_edge g v1 v2 returns the edge from v1 to v2 if it exists. The behaviour is unspecified if g has several edges from v1 to v2.
Raises Not_found if no such edge exists.

Successors and predecessors


val succ : t -> vertex -> vertex list
succ g v returns the successors of v in g.
Raises Invalid_argument if v is not in g.
val pred : t -> vertex -> vertex list
pred g v returns the predecessors of v in g.
Raises Invalid_argument if v is not in g.

Labeled edges going from/to a vertex
val succ_e : t -> vertex -> edge list
succ_e g v returns the edges going from v in g.
Raises Invalid_argument if v is not in g.
val pred_e : t -> vertex -> edge list
pred_e g v returns the edges going to v in g.
Raises Invalid_argument if v is not in g.

Graph iterators



iter/fold on all vertices/edges of a graph
val iter_vertex : (vertex -> unit) -> t -> unit
val iter_edges : (vertex -> vertex -> unit) -> t -> unit
val fold_vertex : (vertex -> 'a -> 'a) -> t -> 'a -> 'a
val fold_edges : (vertex -> vertex -> 'a -> 'a) -> t -> 'a -> 'a
val map_vertex : (vertex -> vertex) -> t -> t
map iterator on vertex

iter/fold on all labeled edges of a graph
val iter_edges_e : (edge -> unit) -> t -> unit
val fold_edges_e : (edge -> 'a -> 'a) -> t -> 'a -> 'a

Vertex iterators

Each iterator iterator f v g iters f to the successors/predecessors of v in the graph g and raises Invalid_argument if v is not in g.

iter/fold on all successors/predecessors of a vertex.

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

iter/fold on all edges going from/to a vertex.
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