1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
(*
* Graph: generic graph library
* Copyright (C) 2004
* Sylvain Conchon, Jean-Christophe Filliatre and Julien Signoles
*
* This software is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License version 2, as published by the Free Software Foundation.
*
* This software is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* See the GNU Library General Public License version 2 for more details
* (enclosed in the file LGPL).
*)
(* $Id: traverse.mli,v 1.14 2005/04/01 07:13:24 filliatr Exp $ *)
(** Graph traversal *)
(** {1 Dfs and Bfs} *)
(** Minimal graph signature for [Dfs] or [Bfs] *)
module type G = sig
type t
module V : Sig.COMPARABLE
val iter_vertex : (V.t -> unit) -> t -> unit
val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
val fold_succ : (V.t -> 'a -> 'a) -> t -> V.t -> 'a -> 'a
end
(** Depth-first search *)
module Dfs(G : G) : sig
(** {2 Classical big-step iterators} *)
val iter : ?pre:(G.V.t -> unit) ->
?post:(G.V.t -> unit) -> G.t -> unit
(** [iter pre post g] visits all nodes of [g] in depth-first search,
applying [pre] to each visited node before its successors,
and [post] after them. Each node is visited exactly once.
Not tail-recursive. *)
val prefix : (G.V.t -> unit) -> G.t -> unit
(** applies only a prefix function; note that this function is more
efficient than [iter] and is tail-recursive. *)
val postfix : (G.V.t -> unit) -> G.t -> unit
(** applies only a postfix function. Not tail-recursive. *)
(** Same thing, but for a single connected component
(only [prefix_component] is tail-recursive) *)
val iter_component : ?pre:(G.V.t -> unit) ->
?post:(G.V.t -> unit) -> G.t -> G.V.t -> unit
val prefix_component : (G.V.t -> unit) -> G.t -> G.V.t -> unit
val postfix_component : (G.V.t -> unit) -> G.t -> G.V.t -> unit
(** {2 Step-by-step iterator}
This is a variant of the iterators above where you can move on
step by step. The abstract type [iterator] represents the current
state of the iteration. The [step] function returns the next state.
In each state, function [get] returns the currently visited vertex.
On the final state both [get] and [step] raises exception [Exit].
Note: the iterator type is persistent (i.e. is not modified by the
[step] function) and thus can be used in backtracking algorithms. *)
type iterator
val start : G.t -> iterator
val step : iterator -> iterator
val get : iterator -> G.V.t
(** {2 Cycle detection} *)
val has_cycle : G.t -> bool
(** [has_cycle g] checks for a cycle in [g]. Linear in time and space. *)
end
(** Breadth-first search *)
module Bfs(G : G) : sig
(** {2 Classical big-step iterators} *)
val iter : (G.V.t -> unit) -> G.t -> unit
val iter_component : (G.V.t -> unit) -> G.t -> G.V.t -> unit
(** {2 Step-by-step iterator}
See module [Dfs] *)
type iterator
val start : G.t -> iterator
val step : iterator -> iterator
val get : iterator -> G.V.t
end
(** {1 Traversal with marking} *)
(** Minimal graph signature for graph traversal with marking. *)
module type GM = sig
type t
module V : sig type t end
val iter_vertex : (V.t -> unit) -> t -> unit
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
module Mark : sig
val clear : t -> unit
val get : V.t -> int
val set : V.t -> int -> unit
end
end
(** Graph traversal with marking.
Only applies to imperative graphs with marks. *)
module Mark(G : GM) : sig
val dfs : G.t -> unit
(** [dfs g] traverses [g] in depth-first search, marking all nodes. *)
val has_cycle : G.t -> bool
(** [has_cycle g] checks for a cycle in [g]. Modifies the marks.
Linear time, constant space. *)
end
|