2
* Graph: generic graph library
4
* Sylvain Conchon, Jean-Christophe Filliatre and Julien Signoles
6
* This software is free software; you can redistribute it and/or
7
* modify it under the terms of the GNU Library General Public
8
* License version 2, as published by the Free Software Foundation.
10
* This software is distributed in the hope that it will be useful,
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14
* See the GNU Library General Public License version 2 for more details
15
* (enclosed in the file LGPL).
18
(* $Id: oper.mli,v 1.14 2004/11/04 15:39:41 filliatr Exp $ *)
2
20
(** Basic operations over graphs *)
22
(** {1 Basic operations over graphs} *)
40
module Make(G : Sig.G)(B : Builder.S with module G = G) : S with type g = G.t
60
module Make(B : Builder.S) : S with type g = B.G.t
61
(** Basic operations over graphs *)
42
63
module P(G : Sig.P) : S with type g = G.t
43
64
(** Basic operations over persistent graphs *)
45
66
module I(G : Sig.I) : S with type g = G.t
46
67
(** Basic operations over imperative graphs *)
71
(** Choose an element in a graph *)
76
val iter_vertex : (vertex -> unit) -> t -> unit
77
val iter_edges_e : (edge -> unit) -> t -> unit
81
val choose_vertex : G.t -> G.vertex
82
(** [choose_vertex g] returns a vertex from the graph.
83
@raise Invalid_argument if the graph is empty. *)
85
val choose_edge : G.t -> G.edge
86
(** [choose_edge g] returns an edge from the graph.
87
@raise Invalid_argument if the graph has no edge. *)
91
(** {1 Neighbourhood } *)
93
(** Neighbourhood of vertex / vertices *)
94
module Neighbourhood(G : sig
96
module V : Sig.COMPARABLE
97
val fold_succ: (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
98
val succ: t -> V.t -> V.t list
102
module Vertex_Set : Set.S with type elt = G.V.t
104
(** The neighbourhood of a vertex [v] is
105
\{ v' | (succ g v) and (v <> v') \} *)
107
val list_from_vertex : G.t -> G.V.t -> G.V.t list
108
(** Neighbourhood of a vertex as a list. *)
110
val set_from_vertex : G.t -> G.V.t -> Vertex_Set.t
111
(** Neighbourhood of a vertex as a set.
112
Less efficient that [list_from_vertex]. *)
114
(** The neighbourhood of a set [S] of vertices is [U \ S] where
115
[U] is the union of neighbourhoods of each vertex of [S]. *)
117
val list_from_vertices : G.t -> G.V.t list -> G.V.t list
118
(** Neighbourhood of a list of vertices as a list. *)
120
val set_from_vertices : G.t -> G.V.t list -> Vertex_Set.t
121
(** Neighbourhood of a list of vertices as a set.
122
More efficient that [list_from_vertices]. *)