« back to all changes in this revision
Viewing changes to sig.ml
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Bazaar Package Importer
- Author(s): Sylvain Le Gall
- Date: 2005-03-23 23:17:46 UTC
- mfrom: (2.1.1 hoary)
- Revision ID: james.westby@ubuntu.com-20050323231746-8rmzgp3zyslg4me5
Tags: 0.90-2
* Transition to ocaml 3.08.3 : depends on ocaml-nox-3.08.3
* Patch 03_META use graph.cma and graph.cmxa ( Closes: #294806 )
* Correct the patch 01_makefile to install graph.a ( Closes: #289138 )
* Patch 03_META use graph.cma and graph.cmxa ( Closes: #294806 )
* Correct the patch 01_makefile to install graph.a ( Closes: #289138 )
- files added:
- cliquetree.ml
- files removed:
- sig.ml
- files modified:
- .depend
added
removed
sig.ml
1
(*
2
* Graph: generic graph library
3
* Copyright (C) 2004
4
* Sylvain Conchon, Jean-Christophe Filliatre and Julien Signoles
5
*
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.
9
*
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.
13
*
14
* See the GNU Library General Public License version 2 for more details
15
* (enclosed in the file LGPL).
16
*)
17
18
(* $Id: sig.mli,v 1.14 2004/02/23 10:06:30 signoles Exp $ *)
19
20
(** Signatures for graph implementations *)
21
22
(** {1 Signatures for graph implementations} *)
23
24
(** Common interface for all graph implementations *)
25
26
module type G = sig
27
28
(** {2 Graph structure} *)
29
30
(** Abstract type of graphs *)
31
type t
32
33
(** Vertices have type [V.t] and are labeled with type [V.label]
34
(note that an implementation may identify the vertex with its
35
label) *)
36
module V : sig
37
(** Vertices are [COMPARABLE] *)
38
39
type t
40
val compare : t -> t -> int
41
val hash : t -> int
42
val equal : t -> t -> bool
43
44
(** Vertices are labeled. *)
45
46
type label
47
val create : label -> t
48
val label : t -> label
49
end
50
51
(** Edges have type [E.t] and are labeled with type [E.label].
52
[src] (resp. [dst]) returns the origin (resp. the destination) of a
53
given edge. *)
54
module E : sig
55
(** Edges are [ORDERED]. *)
56
57
type t
58
val compare : t -> t -> int
59
60
(** Edges are directed. *)
61
62
val src : t -> V.t
63
val dst : t -> V.t
64
65
(** Edges are labeled. *)
66
67
type label
68
val create : V.t -> label -> V.t -> t
69
(** [create v1 l v2] creates an edge from [v1] to [v2] with label [l] *)
70
val label : t -> label
71
end
72
73
(** Is this an implementation of directed graphs? *)
74
val is_directed : bool
75
76
(** {2 Size functions} *)
77
78
val is_empty : t -> bool
79
val nb_vertex : t -> int
80
val nb_edges : t -> int
81
82
(** Degree of a vertex *)
83
84
val out_degree : t -> V.t -> int
85
(** [out_degree g v] returns the out-degree of [v] in [g].
86
Raise [Invalid_argument] if [v] is not in [g]. *)
87
88
val in_degree : t -> V.t -> int
89
(** [in_degree g v] returns the in-degree of [v] in [g].
90
Raise [Invalid_argument] if [v] is not in [g]. *)
91
92
(** {2 Membership functions} *)
93
94
val mem_vertex : t -> V.t -> bool
95
val mem_edge : t -> V.t -> V.t -> bool
96
val mem_edge_e : t -> E.t -> bool
97
98
(** {2 Successors and predecessors} *)
99
100
val succ : t -> V.t -> V.t list
101
(** [succ g v] returns the successors of [v] in [g].
102
Raise [Invalid_argument] if [v] is not in [g]. *)
103
104
val pred : t -> V.t -> V.t list
105
(** [pred g v] returns the predecessors of [v] in [g].
106
Raise [Invalid_argument] if [v] is not in [g]. *)
107
108
(** Labeled edges going from/to a vertex *)
109
110
val succ_e : t -> V.t -> E.t list
111
(** [succ_e g v] returns the edges going from [v] in [g].
112
Raise [Invalid_argument] if [v] is not in [g]. *)
113
114
val pred_e : t -> V.t -> E.t list
115
(** [pred_e g v] returns the edges going to [v] in [g].
116
Raise [Invalid_argument] if [v] is not in [g]. *)
117
118
(** {2 Graph iterators} *)
119
120
(** iter/fold on all vertices/edges of a graph *)
121
122
val iter_vertex : (V.t -> unit) -> t -> unit
123
val iter_edges : (V.t -> V.t -> unit) -> t -> unit
124
val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
125
val fold_edges : (V.t -> V.t -> 'a -> 'a) -> t -> 'a -> 'a
126
127
(** map iterator on vertex *)
128
val map_vertex : (V.t -> V.t) -> t -> t
129
130
(** iter/fold on all labeled edges of a graph *)
131
132
val iter_edges_e : (E.t -> unit) -> t -> unit
133
val fold_edges_e : (E.t -> 'a -> 'a) -> t -> 'a -> 'a
134
135
(** {2 Vertex iterators}
136
137
Each iterator [iterator f v g] iters [f] to the successors/predecessors
138
of [v] in the graph [g] and raises [Invalid_argument] if [v] is not in
139
[g]. *)
140
141
(** iter/fold on all successors/predecessors of a vertex. *)
142
143
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
144
val iter_pred : (V.t -> unit) -> t -> V.t -> unit
145
val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
146
val fold_pred : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
147
148
(** iter/fold on all edges going from/to a vertex. *)
149
150
val iter_succ_e : (E.t -> unit) -> t -> V.t -> unit
151
val fold_succ_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
152
val iter_pred_e : (E.t -> unit) -> t -> V.t -> unit
153
val fold_pred_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
154
155
end
156
157
(** Persistent (i.e. immutable) implementation *)
158
159
module type P = sig
160
include G
161
162
val empty : t
163
(** The empty graph. *)
164
165
val add_vertex : t -> V.t -> t
166
(** [add_vertex g v] adds the vertex [v] from the graph [g].
167
Just return [g] if [v] is already in [g]. *)
168
169
val remove_vertex : t -> V.t -> t
170
(** [remove g v] removes the vertex [v] from the graph [g]
171
(and all the edges going from [v] in [g]).
172
Just return [g] if [v] is not in [g]. *)
173
174
val add_edge : t -> V.t -> V.t -> t
175
(** [add_edge g v1 v2] adds an edge from the vertex [v1] to the vertex [v2]
176
in the graph [g].
177
Add also [v1] (resp. [v2]) in [g] if [v1] (resp. [v2]) is not in [g].
178
Just return [g] if this edge is already in [g]. *)
179
180
val add_edge_e : t -> E.t -> t
181
(** [add_edge_e g e] adds the edge [e] in the graph [g].
182
Add also [E.src e] (resp. [E.dst e]) in [g] if [E.src e] (resp. [E.dst
183
e]) is not in [g].
184
Just return [g] if [e] is already in [g]. *)
185
186
val remove_edge : t -> V.t -> V.t -> t
187
(** [remove_edge g v1 v2] removes the edge going from [v1] to [v2] from the
188
graph [g].
189
Raise [Invalid_argument] if [v1] or [v2] are not in [g].
190
Just return [g] if this edge is not in [g]. *)
191
192
val remove_edge_e : t -> E.t -> t
193
(** [remove_edge_e g e] removes the edge [e] from the graph [g].
194
Raise [Invalid_argument] if [E.src e] or [E.dst e] are not in [g].
195
Just return [g] if [e] is not in [g]. *)
196
197
end
198
199
(** Imperative (i.e. mutable) implementation *)
200
201
module type I = sig
202
include G
203
204
val create : unit -> t
205
(** Return an empty graph. *)
206
207
val copy : t -> t
208
(** [copy g] returns a copy of [g]. Vertices and edges (and eventually
209
marks, see module [Mark]) are duplicated. *)
210
211
val add_vertex : t -> V.t -> unit
212
(** [add_vertex g v] adds the vertex [v] from the graph [g].
213
Do nothing if [v] is already in [g]. *)
214
215
val remove_vertex : t -> V.t -> unit
216
(** [remove g v] removes the vertex [v] from the graph [g]
217
(and all the edges going from [v] in [g]).
218
Do nothing if [v] is not in [g]. *)
219
220
val add_edge : t -> V.t -> V.t -> unit
221
(** [add_edge g v1 v2] adds an edge from the vertex [v1] to the vertex [v2]
222
in the graph [g].
223
Add also [v1] (resp. [v2]) in [g] if [v1] (resp. [v2]) is not in [g].
224
Do nothing if this edge is already in [g]. *)
225
226
val add_edge_e : t -> E.t -> unit
227
(** [add_edge_e g e] adds the edge [e] in the graph [g].
228
Add also [E.src e] (resp. [E.dst e]) in [g] if [E.src e] (resp. [E.dst
229
e]) is not in [g].
230
Do nothing if [e] is already in [g]. *)
231
232
val remove_edge : t -> V.t -> V.t -> unit
233
(** [remove_edge g v1 v2] removes the edge going from [v1] to [v2] from the
234
graph [g].
235
Raise [Invalid_argument] if [v1] or [v2] are not in [g].
236
Do nothing if this edge is not in [g]. *)
237
238
val remove_edge_e : t -> E.t -> unit
239
(** [remove_edge_e g e] removes the edge [e] from the graph [g].
240
Raise [Invalid_argument] if [E.src e] or [E.dst e] are not in [g].
241
Do nothing if [e] is not in [g]. *)
242
243
end
244
245
(** Imperative implementation with marks *)
246
247
module type IA = sig
248
include I
249
module Mark : sig
250
val clear : t -> unit
251
(** [clear g] removes all the marks from all the vertives of [g]. *)
252
val get : V.t -> int
253
val set : V.t -> int -> unit
254
end
255
end
256
257
(** {1 Signature for ordered and hashable types} *)
258
259
module type ORDERED_TYPE = sig type t val compare : t -> t -> int end
260
261
module type ORDERED_TYPE_DFT = sig include ORDERED_TYPE val default : t end
262
263
module type HASHABLE = sig
264
type t
265
val hash : t -> int
266
val equal : t -> t -> bool
267
end
268
269
(** Comparable = Ordered + Hashable *)
270
271
module type COMPARABLE = sig
272
type t
273
val compare : t -> t -> int
274
val hash : t -> int
275
val equal : t -> t -> bool
276
end
Loggerhead is a web-based interface for Breezy
Version: 2.0.1