« back to all changes in this revision
Viewing changes to sig_pack.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_pack.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_pack.mli,v 1.15 2004/02/27 12:21:07 conchon Exp $ *)
19
20
(** Immediate access to the library.
21
Signature [S] gathers an imperative implementation and all algorithms into
22
a single module.
23
Vertices and edges are labeled with integers. *)
24
25
module type S = sig
26
27
(** {2 Graph structure} *)
28
29
(** abstract type of graphs *)
30
type t
31
32
(** Vertices *)
33
module V : sig
34
(** Vertices are [COMPARABLE] *)
35
36
type t
37
val compare : t -> t -> int
38
val hash : t -> int
39
val equal : t -> t -> bool
40
41
(** vertices are labeled with integers *)
42
43
type label = int
44
val create : label -> t
45
val label : t -> label
46
end
47
48
(** Edges *)
49
module E : sig
50
(** Edges are [ORDERED]. *)
51
52
type t
53
val compare : t -> t -> int
54
55
(** Edges are directed. *)
56
57
val src : t -> V.t
58
val dst : t -> V.t
59
60
(** Edges are labeled with integers. *)
61
62
type label = int
63
val create : V.t -> label -> V.t -> t
64
(** [create v1 l v2] creates an edge from [v1] to [v2] with label [l] *)
65
val label : t -> label
66
end
67
68
(** is this an implementation of directed graphs? *)
69
val is_directed : bool
70
71
(** {2 Graph constructors and destructors} *)
72
73
val create : unit -> t
74
(** Return an empty graph. *)
75
76
val copy : t -> t
77
(** [copy g] returns a copy of [g]. Vertices and edges (and eventually
78
marks, see module [Mark]) are duplicated. *)
79
80
val add_vertex : t -> V.t -> unit
81
(** [add_vertex g v] adds the vertex [v] from the graph [g].
82
Do nothing if [v] is already in [g]. *)
83
84
val remove_vertex : t -> V.t -> unit
85
(** [remove g v] removes the vertex [v] from the graph [g]
86
(and all the edges going from [v] in [g]).
87
Do nothing if [v] is not in [g]. *)
88
89
val add_edge : t -> V.t -> V.t -> unit
90
(** [add_edge g v1 v2] adds an edge from the vertex [v1] to the vertex [v2]
91
in the graph [g].
92
Add also [v1] (resp. [v2]) in [g] if [v1] (resp. [v2]) is not in [g].
93
Do nothing if this edge is already in [g]. *)
94
95
val add_edge_e : t -> E.t -> unit
96
(** [add_edge_e g e] adds the edge [e] in the graph [g].
97
Add also [E.src e] (resp. [E.dst e]) in [g] if [E.src e] (resp. [E.dst
98
e]) is not in [g].
99
Do nothing if [e] is already in [g]. *)
100
101
val remove_edge : t -> V.t -> V.t -> unit
102
(** [remove_edge g v1 v2] removes the edge going from [v1] to [v2] from the
103
graph [g].
104
Raise [Invalid_argument] if [v1] or [v2] are not in [g].
105
Do nothing if this edge is not in [g]. *)
106
107
val remove_edge_e : t -> E.t -> unit
108
(** [remove_edge_e g e] removes the edge [e] from the graph [g].
109
Raise [Invalid_argument] if [E.src e] or [E.dst e] are not in [g].
110
Do nothing if [e] is not in [g]. *)
111
112
(** Vertices contains integers marks, which can be set or used by some
113
algorithms (see for instance module [Marking] below) *)
114
module Mark : sig
115
val clear : t -> unit
116
(** [clear g] removes all the marks from all the vertives of [g]. *)
117
val get : V.t -> int
118
val set : V.t -> int -> unit
119
end
120
121
(** {2 Size functions} *)
122
123
val is_empty : t -> bool
124
val nb_vertex : t -> int
125
val nb_edges : t -> int
126
127
(** Degree of a vertex *)
128
129
val out_degree : t -> V.t -> int
130
(** [out_degree g v] returns the out-degree of [v] in [g].
131
Raise [Invalid_argument] if [v] is not in [g]. *)
132
133
val in_degree : t -> V.t -> int
134
(** [in_degree g v] returns the in-degree of [v] in [g].
135
Raise [Invalid_argument] if [v] is not in [g]. *)
136
137
(** {2 Membership functions} *)
138
139
val mem_vertex : t -> V.t -> bool
140
val mem_edge : t -> V.t -> V.t -> bool
141
val mem_edge_e : t -> E.t -> bool
142
143
(** {2 Successors and predecessors of a vertex} *)
144
145
val succ : t -> V.t -> V.t list
146
(** [succ g v] returns the successors of [v] in [g].
147
Raise [Invalid_argument] if [v] is not in [g]. *)
148
149
val pred : t -> V.t -> V.t list
150
(** [pred g v] returns the predecessors of [v] in [g].
151
Raise [Invalid_argument] if [v] is not in [g]. *)
152
153
(** Labeled edges going from/to a vertex *)
154
155
val succ_e : t -> V.t -> E.t list
156
(** [succ_e g v] returns the edges going from [v] in [g].
157
Raise [Invalid_argument] if [v] is not in [g]. *)
158
159
val pred_e : t -> V.t -> E.t list
160
(** [pred_e g v] returns the edges going to [v] in [g].
161
Raise [Invalid_argument] if [v] is not in [g]. *)
162
163
(** {2 Graph iterators} *)
164
165
(** iter/fold on all vertices/edges of a graph *)
166
167
val iter_vertex : (V.t -> unit) -> t -> unit
168
val iter_edges : (V.t -> V.t -> unit) -> t -> unit
169
val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
170
val fold_edges : (V.t -> V.t -> 'a -> 'a) -> t -> 'a -> 'a
171
172
(** map iterator on vertex *)
173
val map_vertex : (V.t -> V.t) -> t -> t
174
175
(** iter/fold on all labeled edges of a graph *)
176
177
val iter_edges_e : (E.t -> unit) -> t -> unit
178
val fold_edges_e : (E.t -> 'a -> 'a) -> t -> 'a -> 'a
179
180
(** {2 Vertex iterators}
181
182
Each iterator [iterator f v g] iters [f] to the successors/predecessors
183
of [v] in the graph [g] and raises [Invalid_argument] if [v] is not in
184
[g]. *)
185
186
(** iter/fold on all successors/predecessors of a vertex. *)
187
188
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
189
val iter_pred : (V.t -> unit) -> t -> V.t -> unit
190
val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
191
val fold_pred : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
192
193
(** iter/fold on all edges going from/to a vertex. *)
194
195
val iter_succ_e : (E.t -> unit) -> t -> V.t -> unit
196
val fold_succ_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
197
val iter_pred_e : (E.t -> unit) -> t -> V.t -> unit
198
val fold_pred_e : (E.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
199
200
(** {2 Basic operations} *)
201
202
val find_vertex : t -> int -> V.t
203
(** [vertex g i] returns a vertex of label [i] in [g]. The behaviour is
204
unspecified if [g] has several vertices with label [i].
205
Note: this function is inefficient (linear in the number of vertices);
206
you should better keep the vertices as long as you create them. *)
207
208
val transitive_closure : ?reflexive:bool -> t -> t
209
(** [transitive_closure ?reflexive g] returns the transitive closure
210
of [g] (as a new graph). Loops (i.e. edges from a vertex to itself)
211
are added only if [reflexive] is [true] (default is [false]). *)
212
213
val add_transitive_closure : ?reflexive:bool -> t -> t
214
(** [add_transitive_closure ?reflexive g] replaces [g] by its
215
transitive closure. Meaningless for persistent implementations
216
(then acts as [transitive_closure]). *)
217
218
val mirror : t -> t
219
(** [mirror g] returns a new graph which is the mirror image of [g]:
220
each edge from [u] to [v] has been replaced by an edge from [v] to [u].
221
For undirected graphs, it simply returns of copy of [g]. *)
222
223
val complement : t -> t
224
(** [complement g] builds a new graph which is the complement of [g]:
225
each edge present in [g] is not present in the resulting graph and
226
vice-versa. Edges of the returned graph are unlabeled. *)
227
228
val intersect : t -> t -> t
229
(** [intersect g1 g2] returns a new graph which is the intersection of [g1]
230
and [g2]: each vertex and edge present in [g1] *and* [g2] is present
231
in the resulting graph. *)
232
233
val union : t -> t -> t
234
(** [union g1 g2] returns a new graph which is the union of [g1] and [g2]:
235
each vertex and edge present in [g1] *or* [g2] is present in the
236
resulting graph. *)
237
238
(** {2 Traversal} *)
239
240
(** Depth-first search *)
241
module Dfs : sig
242
val iter : ?pre:(V.t -> unit) ->
243
?post:(V.t -> unit) -> t -> unit
244
(** [iter pre post g] visits all nodes of [g] in depth-first search,
245
applying [pre] to each visited node before its successors,
246
and [post] after them. Each node is visited exactly once. *)
247
val prefix : (V.t -> unit) -> t -> unit
248
(** applies only a prefix function *)
249
val postfix : (V.t -> unit) -> t -> unit
250
(** applies only a postfix function *)
251
252
(** Same thing, but for a single connected component *)
253
254
val iter_component :
255
?pre:(V.t -> unit) ->
256
?post:(V.t -> unit) -> t -> V.t -> unit
257
val prefix_component : (V.t -> unit) -> t -> V.t -> unit
258
val postfix_component : (V.t -> unit) -> t -> V.t -> unit
259
260
val has_cycle : t -> bool
261
end
262
263
(** Breadth-first search *)
264
module Bfs : sig
265
val iter : (V.t -> unit) -> t -> unit
266
val iter_component : (V.t -> unit) -> t -> V.t -> unit
267
end
268
269
(** Graph traversal with marking *)
270
module Marking : sig
271
val dfs : t -> unit
272
val has_cycle : t -> bool
273
end
274
275
(** {2 Graph generators} *)
276
277
(** Classic graphs *)
278
module Classic : sig
279
val divisors : int -> t
280
(** [divisors n] builds the graph of divisors.
281
Vertices are integers from [2] to [n]. [i] is connected to [j] if
282
and only if [i] divides [j]. Raises [Invalid_argument] is [n < 2]. *)
283
284
val de_bruijn : int -> t
285
(** [de_bruijn n] builds the de Bruijn graph of order [n].
286
Vertices are bit sequences of length [n] (encoded as their
287
interpretation as binary integers). The sequence [xw] is connected
288
to the sequence [wy] for any bits [x] and [y] and any bit sequence
289
[w] of length [n-1].
290
Raises [Invalid_argument] is [n < 1] or [n > Sys.word_size-1]. *)
291
292
val vertex_only : int -> t
293
(** [vertex_only n] builds a graph with [n] vertices and no edge. *)
294
295
val full : ?self:bool -> int -> t
296
(** [full n] builds a graph with [n] vertices and all possible edges.
297
The optional argument [self] indicates if loop edges should be added
298
(default value is [true]). *)
299
end
300
301
(** Random graphs *)
302
module Rand : sig
303
val graph : ?loops:bool -> v:int -> e:int -> unit -> t
304
(** [random v e] generates a random with [v] vertices and [e] edges. *)
305
306
val labeled :
307
(V.t -> V.t -> E.label) ->
308
?loops:bool -> v:int -> e:int -> unit -> t
309
(** [random_labeled f] is similar to [random] except that edges are
310
labeled using function [f] *)
311
end
312
313
(** {2 Classical algorithms} *)
314
315
val scc : t -> (V.t -> int)
316
(** strongly connected components *)
317
318
val shortest_path : t -> V.t -> V.t -> E.t list * int
319
(** Dijkstra's shortest path algorithm. Weights are the labels. *)
320
321
val ford_fulkerson : t -> V.t -> V.t -> (E.t -> int) * int
322
(** Ford Fulkerson maximum flow algorithm *)
323
324
val goldberg : t -> V.t -> V.t -> (E.t -> int) * int
325
(** Goldberg maximum flow algorithm *)
326
327
328
(** Topological order *)
329
module Topological : sig
330
val fold : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
331
val iter : (V.t -> unit) -> t -> unit
332
end
333
334
val spanningtree : t -> E.t list
335
(** Kruskal algorithm *)
336
337
(** {2 Input / Output} *)
338
339
val dot_output : t -> string -> unit
340
(** DOT output *)
341
end
Loggerhead is a web-based interface for Breezy
Version: 2.0.1