Module type Sig.G

module type G = sig  end

Graph structure

type t

Abstract type of graphs

module V: sig  end

Vertices have type V.t and are labeled with type V.label (note that an implementation may identify the vertex with its label)

module E: sig  end

Edges have type E.t and are labeled with type E.label.

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 -> V.t -> int

out_degree g v returns the out-degree of v in g. Raise Invalid_argument if v is not in g.

val in_degree : t -> V.t -> int

in_degree g v returns the in-degree of v in g. Raise Invalid_argument if v is not in g.

Membership functions

val mem_vertex : t -> V.t -> bool

val mem_edge : t -> V.t -> V.t -> bool

val mem_edge_e : t -> E.t -> bool

Successors and predecessors

val succ : t -> V.t -> V.t list

succ g v returns the successors of v in g. Raise Invalid_argument if v is not in g.

val pred : t -> V.t -> V.t list

pred g v returns the predecessors of v in g. Raise Invalid_argument if v is not in g.

Labeled edges going from/to a vertex

val succ_e : t -> V.t -> E.t list

succ_e g v returns the edges going from v in g. Raise Invalid_argument if v is not in g.

val pred_e : t -> V.t -> E.t list

pred_e g v returns the edges going to v in g. Raise Invalid_argument if v is not in g.

Graph iterators

iter/fold on all vertices/edges of a graph

val iter_vertex : (V.t -> unit) -> t -> unit

val iter_edges : (V.t -> V.t -> unit) -> t -> unit

val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a

val fold_edges : (V.t -> V.t -> 'a -> 'a) -> t -> 'a -> 'a

val map_vertex : (V.t -> V.t) -> t -> t

map iterator on vertex

iter/fold on all labeled edges of a graph

val iter_edges_e : (E.t -> unit) -> t -> unit

val fold_edges_e : (E.t -> '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 : (V.t -> unit) -> t -> V.t -> unit

val iter_pred : (V.t -> unit) -> t -> V.t -> unit

val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a

val fold_pred : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a

iter/fold on all edges going from/to a vertex.

val iter_succ_e : (E.t -> unit) -> t -> V.t -> unit

val fold_succ_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a

val iter_pred_e : (E.t -> unit) -> t -> V.t -> unit

val fold_pred_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a