alpar@209
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
alpar@100
|
2 |
*
|
alpar@209
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
alpar@100
|
4 |
*
|
alpar@440
|
5 |
* Copyright (C) 2003-2009
|
alpar@100
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@100
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@100
|
8 |
*
|
alpar@100
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@100
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@100
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@100
|
12 |
*
|
alpar@100
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@100
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@100
|
15 |
* purpose.
|
alpar@100
|
16 |
*
|
alpar@100
|
17 |
*/
|
alpar@100
|
18 |
|
alpar@100
|
19 |
#ifndef LEMON_BFS_H
|
alpar@100
|
20 |
#define LEMON_BFS_H
|
alpar@100
|
21 |
|
alpar@100
|
22 |
///\ingroup search
|
alpar@100
|
23 |
///\file
|
kpeter@244
|
24 |
///\brief BFS algorithm.
|
alpar@100
|
25 |
|
alpar@100
|
26 |
#include <lemon/list_graph.h>
|
alpar@100
|
27 |
#include <lemon/bits/path_dump.h>
|
deba@220
|
28 |
#include <lemon/core.h>
|
alpar@100
|
29 |
#include <lemon/error.h>
|
alpar@100
|
30 |
#include <lemon/maps.h>
|
kpeter@278
|
31 |
#include <lemon/path.h>
|
alpar@100
|
32 |
|
alpar@100
|
33 |
namespace lemon {
|
alpar@100
|
34 |
|
alpar@100
|
35 |
///Default traits class of Bfs class.
|
alpar@100
|
36 |
|
alpar@100
|
37 |
///Default traits class of Bfs class.
|
kpeter@157
|
38 |
///\tparam GR Digraph type.
|
alpar@100
|
39 |
template<class GR>
|
alpar@100
|
40 |
struct BfsDefaultTraits
|
alpar@100
|
41 |
{
|
kpeter@244
|
42 |
///The type of the digraph the algorithm runs on.
|
alpar@100
|
43 |
typedef GR Digraph;
|
kpeter@244
|
44 |
|
kpeter@244
|
45 |
///\brief The type of the map that stores the predecessor
|
alpar@100
|
46 |
///arcs of the shortest paths.
|
alpar@209
|
47 |
///
|
kpeter@244
|
48 |
///The type of the map that stores the predecessor
|
alpar@100
|
49 |
///arcs of the shortest paths.
|
kpeter@716
|
50 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@244
|
51 |
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
|
kpeter@503
|
52 |
///Instantiates a \c PredMap.
|
alpar@209
|
53 |
|
kpeter@503
|
54 |
///This function instantiates a \ref PredMap.
|
kpeter@244
|
55 |
///\param g is the digraph, to which we would like to define the
|
kpeter@503
|
56 |
///\ref PredMap.
|
kpeter@244
|
57 |
static PredMap *createPredMap(const Digraph &g)
|
alpar@100
|
58 |
{
|
kpeter@244
|
59 |
return new PredMap(g);
|
alpar@100
|
60 |
}
|
kpeter@244
|
61 |
|
alpar@100
|
62 |
///The type of the map that indicates which nodes are processed.
|
alpar@209
|
63 |
|
alpar@100
|
64 |
///The type of the map that indicates which nodes are processed.
|
kpeter@716
|
65 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@716
|
66 |
///By default it is a NullMap.
|
alpar@100
|
67 |
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
|
kpeter@503
|
68 |
///Instantiates a \c ProcessedMap.
|
alpar@209
|
69 |
|
kpeter@503
|
70 |
///This function instantiates a \ref ProcessedMap.
|
alpar@100
|
71 |
///\param g is the digraph, to which
|
kpeter@503
|
72 |
///we would like to define the \ref ProcessedMap
|
alpar@100
|
73 |
#ifdef DOXYGEN
|
kpeter@244
|
74 |
static ProcessedMap *createProcessedMap(const Digraph &g)
|
alpar@100
|
75 |
#else
|
kpeter@244
|
76 |
static ProcessedMap *createProcessedMap(const Digraph &)
|
alpar@100
|
77 |
#endif
|
alpar@100
|
78 |
{
|
alpar@100
|
79 |
return new ProcessedMap();
|
alpar@100
|
80 |
}
|
kpeter@244
|
81 |
|
alpar@100
|
82 |
///The type of the map that indicates which nodes are reached.
|
alpar@209
|
83 |
|
kpeter@405
|
84 |
///The type of the map that indicates which nodes are reached.
|
kpeter@716
|
85 |
///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
|
alpar@100
|
86 |
typedef typename Digraph::template NodeMap<bool> ReachedMap;
|
kpeter@503
|
87 |
///Instantiates a \c ReachedMap.
|
alpar@209
|
88 |
|
kpeter@503
|
89 |
///This function instantiates a \ref ReachedMap.
|
kpeter@244
|
90 |
///\param g is the digraph, to which
|
kpeter@503
|
91 |
///we would like to define the \ref ReachedMap.
|
kpeter@244
|
92 |
static ReachedMap *createReachedMap(const Digraph &g)
|
alpar@100
|
93 |
{
|
kpeter@244
|
94 |
return new ReachedMap(g);
|
alpar@100
|
95 |
}
|
alpar@209
|
96 |
|
kpeter@244
|
97 |
///The type of the map that stores the distances of the nodes.
|
kpeter@244
|
98 |
|
kpeter@244
|
99 |
///The type of the map that stores the distances of the nodes.
|
kpeter@716
|
100 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
alpar@100
|
101 |
typedef typename Digraph::template NodeMap<int> DistMap;
|
kpeter@503
|
102 |
///Instantiates a \c DistMap.
|
alpar@209
|
103 |
|
kpeter@503
|
104 |
///This function instantiates a \ref DistMap.
|
kpeter@244
|
105 |
///\param g is the digraph, to which we would like to define the
|
kpeter@503
|
106 |
///\ref DistMap.
|
kpeter@244
|
107 |
static DistMap *createDistMap(const Digraph &g)
|
alpar@100
|
108 |
{
|
kpeter@244
|
109 |
return new DistMap(g);
|
alpar@100
|
110 |
}
|
alpar@100
|
111 |
};
|
alpar@209
|
112 |
|
alpar@100
|
113 |
///%BFS algorithm class.
|
alpar@209
|
114 |
|
alpar@100
|
115 |
///\ingroup search
|
alpar@100
|
116 |
///This class provides an efficient implementation of the %BFS algorithm.
|
alpar@100
|
117 |
///
|
kpeter@278
|
118 |
///There is also a \ref bfs() "function-type interface" for the BFS
|
kpeter@244
|
119 |
///algorithm, which is convenient in the simplier cases and it can be
|
kpeter@244
|
120 |
///used easier.
|
kpeter@244
|
121 |
///
|
kpeter@244
|
122 |
///\tparam GR The type of the digraph the algorithm runs on.
|
kpeter@405
|
123 |
///The default type is \ref ListDigraph.
|
alpar@100
|
124 |
#ifdef DOXYGEN
|
alpar@100
|
125 |
template <typename GR,
|
alpar@209
|
126 |
typename TR>
|
alpar@100
|
127 |
#else
|
alpar@100
|
128 |
template <typename GR=ListDigraph,
|
alpar@209
|
129 |
typename TR=BfsDefaultTraits<GR> >
|
alpar@100
|
130 |
#endif
|
alpar@100
|
131 |
class Bfs {
|
alpar@100
|
132 |
public:
|
alpar@100
|
133 |
|
kpeter@244
|
134 |
///The type of the digraph the algorithm runs on.
|
alpar@100
|
135 |
typedef typename TR::Digraph Digraph;
|
alpar@209
|
136 |
|
kpeter@244
|
137 |
///\brief The type of the map that stores the predecessor arcs of the
|
kpeter@244
|
138 |
///shortest paths.
|
alpar@100
|
139 |
typedef typename TR::PredMap PredMap;
|
kpeter@244
|
140 |
///The type of the map that stores the distances of the nodes.
|
kpeter@244
|
141 |
typedef typename TR::DistMap DistMap;
|
kpeter@244
|
142 |
///The type of the map that indicates which nodes are reached.
|
alpar@100
|
143 |
typedef typename TR::ReachedMap ReachedMap;
|
kpeter@244
|
144 |
///The type of the map that indicates which nodes are processed.
|
alpar@100
|
145 |
typedef typename TR::ProcessedMap ProcessedMap;
|
kpeter@244
|
146 |
///The type of the paths.
|
kpeter@244
|
147 |
typedef PredMapPath<Digraph, PredMap> Path;
|
kpeter@244
|
148 |
|
kpeter@405
|
149 |
///The \ref BfsDefaultTraits "traits class" of the algorithm.
|
kpeter@244
|
150 |
typedef TR Traits;
|
kpeter@244
|
151 |
|
alpar@100
|
152 |
private:
|
alpar@100
|
153 |
|
alpar@100
|
154 |
typedef typename Digraph::Node Node;
|
alpar@100
|
155 |
typedef typename Digraph::NodeIt NodeIt;
|
alpar@100
|
156 |
typedef typename Digraph::Arc Arc;
|
alpar@100
|
157 |
typedef typename Digraph::OutArcIt OutArcIt;
|
alpar@100
|
158 |
|
kpeter@244
|
159 |
//Pointer to the underlying digraph.
|
alpar@100
|
160 |
const Digraph *G;
|
kpeter@244
|
161 |
//Pointer to the map of predecessor arcs.
|
alpar@100
|
162 |
PredMap *_pred;
|
kpeter@244
|
163 |
//Indicates if _pred is locally allocated (true) or not.
|
alpar@100
|
164 |
bool local_pred;
|
kpeter@244
|
165 |
//Pointer to the map of distances.
|
alpar@100
|
166 |
DistMap *_dist;
|
kpeter@244
|
167 |
//Indicates if _dist is locally allocated (true) or not.
|
alpar@100
|
168 |
bool local_dist;
|
kpeter@244
|
169 |
//Pointer to the map of reached status of the nodes.
|
alpar@100
|
170 |
ReachedMap *_reached;
|
kpeter@244
|
171 |
//Indicates if _reached is locally allocated (true) or not.
|
alpar@100
|
172 |
bool local_reached;
|
kpeter@244
|
173 |
//Pointer to the map of processed status of the nodes.
|
alpar@100
|
174 |
ProcessedMap *_processed;
|
kpeter@244
|
175 |
//Indicates if _processed is locally allocated (true) or not.
|
alpar@100
|
176 |
bool local_processed;
|
alpar@100
|
177 |
|
alpar@100
|
178 |
std::vector<typename Digraph::Node> _queue;
|
alpar@100
|
179 |
int _queue_head,_queue_tail,_queue_next_dist;
|
alpar@100
|
180 |
int _curr_dist;
|
alpar@100
|
181 |
|
alpar@280
|
182 |
//Creates the maps if necessary.
|
alpar@209
|
183 |
void create_maps()
|
alpar@100
|
184 |
{
|
alpar@100
|
185 |
if(!_pred) {
|
alpar@209
|
186 |
local_pred = true;
|
alpar@209
|
187 |
_pred = Traits::createPredMap(*G);
|
alpar@100
|
188 |
}
|
alpar@100
|
189 |
if(!_dist) {
|
alpar@209
|
190 |
local_dist = true;
|
alpar@209
|
191 |
_dist = Traits::createDistMap(*G);
|
alpar@100
|
192 |
}
|
alpar@100
|
193 |
if(!_reached) {
|
alpar@209
|
194 |
local_reached = true;
|
alpar@209
|
195 |
_reached = Traits::createReachedMap(*G);
|
alpar@100
|
196 |
}
|
alpar@100
|
197 |
if(!_processed) {
|
alpar@209
|
198 |
local_processed = true;
|
alpar@209
|
199 |
_processed = Traits::createProcessedMap(*G);
|
alpar@100
|
200 |
}
|
alpar@100
|
201 |
}
|
alpar@100
|
202 |
|
alpar@100
|
203 |
protected:
|
alpar@209
|
204 |
|
alpar@100
|
205 |
Bfs() {}
|
alpar@209
|
206 |
|
alpar@100
|
207 |
public:
|
alpar@209
|
208 |
|
alpar@100
|
209 |
typedef Bfs Create;
|
alpar@100
|
210 |
|
kpeter@405
|
211 |
///\name Named Template Parameters
|
alpar@100
|
212 |
|
alpar@100
|
213 |
///@{
|
alpar@100
|
214 |
|
alpar@100
|
215 |
template <class T>
|
kpeter@257
|
216 |
struct SetPredMapTraits : public Traits {
|
alpar@100
|
217 |
typedef T PredMap;
|
alpar@209
|
218 |
static PredMap *createPredMap(const Digraph &)
|
alpar@100
|
219 |
{
|
deba@290
|
220 |
LEMON_ASSERT(false, "PredMap is not initialized");
|
deba@290
|
221 |
return 0; // ignore warnings
|
alpar@100
|
222 |
}
|
alpar@100
|
223 |
};
|
alpar@100
|
224 |
///\brief \ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
225 |
///\c PredMap type.
|
alpar@100
|
226 |
///
|
kpeter@244
|
227 |
///\ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
228 |
///\c PredMap type.
|
kpeter@716
|
229 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
alpar@100
|
230 |
template <class T>
|
kpeter@257
|
231 |
struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
|
kpeter@257
|
232 |
typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
|
alpar@100
|
233 |
};
|
alpar@209
|
234 |
|
alpar@100
|
235 |
template <class T>
|
kpeter@257
|
236 |
struct SetDistMapTraits : public Traits {
|
alpar@100
|
237 |
typedef T DistMap;
|
alpar@209
|
238 |
static DistMap *createDistMap(const Digraph &)
|
alpar@100
|
239 |
{
|
deba@290
|
240 |
LEMON_ASSERT(false, "DistMap is not initialized");
|
deba@290
|
241 |
return 0; // ignore warnings
|
alpar@100
|
242 |
}
|
alpar@100
|
243 |
};
|
alpar@100
|
244 |
///\brief \ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
245 |
///\c DistMap type.
|
alpar@100
|
246 |
///
|
kpeter@244
|
247 |
///\ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
248 |
///\c DistMap type.
|
kpeter@716
|
249 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
alpar@100
|
250 |
template <class T>
|
kpeter@257
|
251 |
struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
|
kpeter@257
|
252 |
typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
|
alpar@100
|
253 |
};
|
alpar@209
|
254 |
|
alpar@100
|
255 |
template <class T>
|
kpeter@257
|
256 |
struct SetReachedMapTraits : public Traits {
|
alpar@100
|
257 |
typedef T ReachedMap;
|
alpar@209
|
258 |
static ReachedMap *createReachedMap(const Digraph &)
|
alpar@100
|
259 |
{
|
deba@290
|
260 |
LEMON_ASSERT(false, "ReachedMap is not initialized");
|
deba@290
|
261 |
return 0; // ignore warnings
|
alpar@100
|
262 |
}
|
alpar@100
|
263 |
};
|
alpar@100
|
264 |
///\brief \ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
265 |
///\c ReachedMap type.
|
alpar@100
|
266 |
///
|
kpeter@244
|
267 |
///\ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
268 |
///\c ReachedMap type.
|
kpeter@716
|
269 |
///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
|
alpar@100
|
270 |
template <class T>
|
kpeter@257
|
271 |
struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
|
kpeter@257
|
272 |
typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
|
alpar@100
|
273 |
};
|
alpar@209
|
274 |
|
alpar@100
|
275 |
template <class T>
|
kpeter@257
|
276 |
struct SetProcessedMapTraits : public Traits {
|
alpar@100
|
277 |
typedef T ProcessedMap;
|
alpar@209
|
278 |
static ProcessedMap *createProcessedMap(const Digraph &)
|
alpar@100
|
279 |
{
|
deba@290
|
280 |
LEMON_ASSERT(false, "ProcessedMap is not initialized");
|
deba@290
|
281 |
return 0; // ignore warnings
|
alpar@100
|
282 |
}
|
alpar@100
|
283 |
};
|
alpar@100
|
284 |
///\brief \ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
285 |
///\c ProcessedMap type.
|
alpar@100
|
286 |
///
|
kpeter@244
|
287 |
///\ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
288 |
///\c ProcessedMap type.
|
kpeter@716
|
289 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
alpar@100
|
290 |
template <class T>
|
kpeter@257
|
291 |
struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
|
kpeter@257
|
292 |
typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
|
alpar@100
|
293 |
};
|
alpar@209
|
294 |
|
kpeter@257
|
295 |
struct SetStandardProcessedMapTraits : public Traits {
|
alpar@100
|
296 |
typedef typename Digraph::template NodeMap<bool> ProcessedMap;
|
kpeter@244
|
297 |
static ProcessedMap *createProcessedMap(const Digraph &g)
|
alpar@100
|
298 |
{
|
kpeter@244
|
299 |
return new ProcessedMap(g);
|
deba@290
|
300 |
return 0; // ignore warnings
|
alpar@100
|
301 |
}
|
alpar@100
|
302 |
};
|
kpeter@244
|
303 |
///\brief \ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
304 |
///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
|
alpar@100
|
305 |
///
|
kpeter@244
|
306 |
///\ref named-templ-param "Named parameter" for setting
|
kpeter@503
|
307 |
///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
|
alpar@100
|
308 |
///If you don't set it explicitly, it will be automatically allocated.
|
kpeter@257
|
309 |
struct SetStandardProcessedMap :
|
kpeter@257
|
310 |
public Bfs< Digraph, SetStandardProcessedMapTraits > {
|
kpeter@257
|
311 |
typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
|
alpar@100
|
312 |
};
|
alpar@209
|
313 |
|
alpar@100
|
314 |
///@}
|
alpar@100
|
315 |
|
alpar@209
|
316 |
public:
|
alpar@209
|
317 |
|
alpar@100
|
318 |
///Constructor.
|
alpar@209
|
319 |
|
kpeter@244
|
320 |
///Constructor.
|
kpeter@244
|
321 |
///\param g The digraph the algorithm runs on.
|
kpeter@244
|
322 |
Bfs(const Digraph &g) :
|
kpeter@244
|
323 |
G(&g),
|
alpar@100
|
324 |
_pred(NULL), local_pred(false),
|
alpar@100
|
325 |
_dist(NULL), local_dist(false),
|
alpar@100
|
326 |
_reached(NULL), local_reached(false),
|
alpar@100
|
327 |
_processed(NULL), local_processed(false)
|
alpar@100
|
328 |
{ }
|
alpar@209
|
329 |
|
alpar@100
|
330 |
///Destructor.
|
alpar@209
|
331 |
~Bfs()
|
alpar@100
|
332 |
{
|
alpar@100
|
333 |
if(local_pred) delete _pred;
|
alpar@100
|
334 |
if(local_dist) delete _dist;
|
alpar@100
|
335 |
if(local_reached) delete _reached;
|
alpar@100
|
336 |
if(local_processed) delete _processed;
|
alpar@100
|
337 |
}
|
alpar@100
|
338 |
|
kpeter@244
|
339 |
///Sets the map that stores the predecessor arcs.
|
alpar@100
|
340 |
|
kpeter@244
|
341 |
///Sets the map that stores the predecessor arcs.
|
kpeter@405
|
342 |
///If you don't use this function before calling \ref run(Node) "run()"
|
kpeter@405
|
343 |
///or \ref init(), an instance will be allocated automatically.
|
kpeter@405
|
344 |
///The destructor deallocates this automatically allocated map,
|
kpeter@405
|
345 |
///of course.
|
alpar@100
|
346 |
///\return <tt> (*this) </tt>
|
alpar@209
|
347 |
Bfs &predMap(PredMap &m)
|
alpar@100
|
348 |
{
|
alpar@100
|
349 |
if(local_pred) {
|
alpar@209
|
350 |
delete _pred;
|
alpar@209
|
351 |
local_pred=false;
|
alpar@100
|
352 |
}
|
alpar@100
|
353 |
_pred = &m;
|
alpar@100
|
354 |
return *this;
|
alpar@100
|
355 |
}
|
alpar@100
|
356 |
|
kpeter@244
|
357 |
///Sets the map that indicates which nodes are reached.
|
alpar@100
|
358 |
|
kpeter@244
|
359 |
///Sets the map that indicates which nodes are reached.
|
kpeter@405
|
360 |
///If you don't use this function before calling \ref run(Node) "run()"
|
kpeter@405
|
361 |
///or \ref init(), an instance will be allocated automatically.
|
kpeter@405
|
362 |
///The destructor deallocates this automatically allocated map,
|
kpeter@405
|
363 |
///of course.
|
alpar@100
|
364 |
///\return <tt> (*this) </tt>
|
alpar@209
|
365 |
Bfs &reachedMap(ReachedMap &m)
|
alpar@100
|
366 |
{
|
alpar@100
|
367 |
if(local_reached) {
|
alpar@209
|
368 |
delete _reached;
|
alpar@209
|
369 |
local_reached=false;
|
alpar@100
|
370 |
}
|
alpar@100
|
371 |
_reached = &m;
|
alpar@100
|
372 |
return *this;
|
alpar@100
|
373 |
}
|
alpar@100
|
374 |
|
kpeter@244
|
375 |
///Sets the map that indicates which nodes are processed.
|
alpar@100
|
376 |
|
kpeter@244
|
377 |
///Sets the map that indicates which nodes are processed.
|
kpeter@405
|
378 |
///If you don't use this function before calling \ref run(Node) "run()"
|
kpeter@405
|
379 |
///or \ref init(), an instance will be allocated automatically.
|
kpeter@405
|
380 |
///The destructor deallocates this automatically allocated map,
|
kpeter@405
|
381 |
///of course.
|
alpar@100
|
382 |
///\return <tt> (*this) </tt>
|
alpar@209
|
383 |
Bfs &processedMap(ProcessedMap &m)
|
alpar@100
|
384 |
{
|
alpar@100
|
385 |
if(local_processed) {
|
alpar@209
|
386 |
delete _processed;
|
alpar@209
|
387 |
local_processed=false;
|
alpar@100
|
388 |
}
|
alpar@100
|
389 |
_processed = &m;
|
alpar@100
|
390 |
return *this;
|
alpar@100
|
391 |
}
|
alpar@100
|
392 |
|
kpeter@244
|
393 |
///Sets the map that stores the distances of the nodes.
|
alpar@100
|
394 |
|
kpeter@244
|
395 |
///Sets the map that stores the distances of the nodes calculated by
|
kpeter@244
|
396 |
///the algorithm.
|
kpeter@405
|
397 |
///If you don't use this function before calling \ref run(Node) "run()"
|
kpeter@405
|
398 |
///or \ref init(), an instance will be allocated automatically.
|
kpeter@405
|
399 |
///The destructor deallocates this automatically allocated map,
|
kpeter@405
|
400 |
///of course.
|
alpar@100
|
401 |
///\return <tt> (*this) </tt>
|
alpar@209
|
402 |
Bfs &distMap(DistMap &m)
|
alpar@100
|
403 |
{
|
alpar@100
|
404 |
if(local_dist) {
|
alpar@209
|
405 |
delete _dist;
|
alpar@209
|
406 |
local_dist=false;
|
alpar@100
|
407 |
}
|
alpar@100
|
408 |
_dist = &m;
|
alpar@100
|
409 |
return *this;
|
alpar@100
|
410 |
}
|
alpar@100
|
411 |
|
alpar@100
|
412 |
public:
|
kpeter@244
|
413 |
|
kpeter@405
|
414 |
///\name Execution Control
|
kpeter@405
|
415 |
///The simplest way to execute the BFS algorithm is to use one of the
|
kpeter@405
|
416 |
///member functions called \ref run(Node) "run()".\n
|
kpeter@405
|
417 |
///If you need more control on the execution, first you have to call
|
kpeter@405
|
418 |
///\ref init(), then you can add several source nodes with
|
kpeter@405
|
419 |
///\ref addSource(). Finally the actual path computation can be
|
kpeter@405
|
420 |
///performed with one of the \ref start() functions.
|
alpar@100
|
421 |
|
alpar@100
|
422 |
///@{
|
alpar@100
|
423 |
|
kpeter@405
|
424 |
///\brief Initializes the internal data structures.
|
kpeter@405
|
425 |
///
|
kpeter@244
|
426 |
///Initializes the internal data structures.
|
alpar@100
|
427 |
void init()
|
alpar@100
|
428 |
{
|
alpar@100
|
429 |
create_maps();
|
alpar@100
|
430 |
_queue.resize(countNodes(*G));
|
alpar@100
|
431 |
_queue_head=_queue_tail=0;
|
alpar@100
|
432 |
_curr_dist=1;
|
alpar@100
|
433 |
for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
|
alpar@209
|
434 |
_pred->set(u,INVALID);
|
alpar@209
|
435 |
_reached->set(u,false);
|
alpar@209
|
436 |
_processed->set(u,false);
|
alpar@100
|
437 |
}
|
alpar@100
|
438 |
}
|
alpar@209
|
439 |
|
alpar@100
|
440 |
///Adds a new source node.
|
alpar@100
|
441 |
|
alpar@100
|
442 |
///Adds a new source node to the set of nodes to be processed.
|
alpar@100
|
443 |
///
|
alpar@100
|
444 |
void addSource(Node s)
|
alpar@100
|
445 |
{
|
alpar@100
|
446 |
if(!(*_reached)[s])
|
alpar@209
|
447 |
{
|
alpar@209
|
448 |
_reached->set(s,true);
|
alpar@209
|
449 |
_pred->set(s,INVALID);
|
alpar@209
|
450 |
_dist->set(s,0);
|
alpar@209
|
451 |
_queue[_queue_head++]=s;
|
alpar@209
|
452 |
_queue_next_dist=_queue_head;
|
alpar@209
|
453 |
}
|
alpar@100
|
454 |
}
|
alpar@209
|
455 |
|
alpar@100
|
456 |
///Processes the next node.
|
alpar@100
|
457 |
|
alpar@100
|
458 |
///Processes the next node.
|
alpar@100
|
459 |
///
|
alpar@100
|
460 |
///\return The processed node.
|
alpar@100
|
461 |
///
|
kpeter@244
|
462 |
///\pre The queue must not be empty.
|
alpar@100
|
463 |
Node processNextNode()
|
alpar@100
|
464 |
{
|
alpar@100
|
465 |
if(_queue_tail==_queue_next_dist) {
|
alpar@209
|
466 |
_curr_dist++;
|
alpar@209
|
467 |
_queue_next_dist=_queue_head;
|
alpar@100
|
468 |
}
|
alpar@100
|
469 |
Node n=_queue[_queue_tail++];
|
alpar@100
|
470 |
_processed->set(n,true);
|
alpar@100
|
471 |
Node m;
|
alpar@100
|
472 |
for(OutArcIt e(*G,n);e!=INVALID;++e)
|
alpar@209
|
473 |
if(!(*_reached)[m=G->target(e)]) {
|
alpar@209
|
474 |
_queue[_queue_head++]=m;
|
alpar@209
|
475 |
_reached->set(m,true);
|
alpar@209
|
476 |
_pred->set(m,e);
|
alpar@209
|
477 |
_dist->set(m,_curr_dist);
|
alpar@209
|
478 |
}
|
alpar@100
|
479 |
return n;
|
alpar@100
|
480 |
}
|
alpar@100
|
481 |
|
alpar@100
|
482 |
///Processes the next node.
|
alpar@100
|
483 |
|
kpeter@244
|
484 |
///Processes the next node and checks if the given target node
|
alpar@100
|
485 |
///is reached. If the target node is reachable from the processed
|
kpeter@244
|
486 |
///node, then the \c reach parameter will be set to \c true.
|
alpar@100
|
487 |
///
|
alpar@100
|
488 |
///\param target The target node.
|
kpeter@244
|
489 |
///\retval reach Indicates if the target node is reached.
|
kpeter@244
|
490 |
///It should be initially \c false.
|
kpeter@244
|
491 |
///
|
alpar@100
|
492 |
///\return The processed node.
|
alpar@100
|
493 |
///
|
kpeter@244
|
494 |
///\pre The queue must not be empty.
|
alpar@100
|
495 |
Node processNextNode(Node target, bool& reach)
|
alpar@100
|
496 |
{
|
alpar@100
|
497 |
if(_queue_tail==_queue_next_dist) {
|
alpar@209
|
498 |
_curr_dist++;
|
alpar@209
|
499 |
_queue_next_dist=_queue_head;
|
alpar@100
|
500 |
}
|
alpar@100
|
501 |
Node n=_queue[_queue_tail++];
|
alpar@100
|
502 |
_processed->set(n,true);
|
alpar@100
|
503 |
Node m;
|
alpar@100
|
504 |
for(OutArcIt e(*G,n);e!=INVALID;++e)
|
alpar@209
|
505 |
if(!(*_reached)[m=G->target(e)]) {
|
alpar@209
|
506 |
_queue[_queue_head++]=m;
|
alpar@209
|
507 |
_reached->set(m,true);
|
alpar@209
|
508 |
_pred->set(m,e);
|
alpar@209
|
509 |
_dist->set(m,_curr_dist);
|
alpar@100
|
510 |
reach = reach || (target == m);
|
alpar@209
|
511 |
}
|
alpar@100
|
512 |
return n;
|
alpar@100
|
513 |
}
|
alpar@100
|
514 |
|
alpar@100
|
515 |
///Processes the next node.
|
alpar@100
|
516 |
|
kpeter@244
|
517 |
///Processes the next node and checks if at least one of reached
|
kpeter@244
|
518 |
///nodes has \c true value in the \c nm node map. If one node
|
kpeter@244
|
519 |
///with \c true value is reachable from the processed node, then the
|
kpeter@244
|
520 |
///\c rnode parameter will be set to the first of such nodes.
|
alpar@100
|
521 |
///
|
kpeter@244
|
522 |
///\param nm A \c bool (or convertible) node map that indicates the
|
kpeter@244
|
523 |
///possible targets.
|
alpar@100
|
524 |
///\retval rnode The reached target node.
|
kpeter@244
|
525 |
///It should be initially \c INVALID.
|
kpeter@244
|
526 |
///
|
alpar@100
|
527 |
///\return The processed node.
|
alpar@100
|
528 |
///
|
kpeter@244
|
529 |
///\pre The queue must not be empty.
|
alpar@100
|
530 |
template<class NM>
|
alpar@100
|
531 |
Node processNextNode(const NM& nm, Node& rnode)
|
alpar@100
|
532 |
{
|
alpar@100
|
533 |
if(_queue_tail==_queue_next_dist) {
|
alpar@209
|
534 |
_curr_dist++;
|
alpar@209
|
535 |
_queue_next_dist=_queue_head;
|
alpar@100
|
536 |
}
|
alpar@100
|
537 |
Node n=_queue[_queue_tail++];
|
alpar@100
|
538 |
_processed->set(n,true);
|
alpar@100
|
539 |
Node m;
|
alpar@100
|
540 |
for(OutArcIt e(*G,n);e!=INVALID;++e)
|
alpar@209
|
541 |
if(!(*_reached)[m=G->target(e)]) {
|
alpar@209
|
542 |
_queue[_queue_head++]=m;
|
alpar@209
|
543 |
_reached->set(m,true);
|
alpar@209
|
544 |
_pred->set(m,e);
|
alpar@209
|
545 |
_dist->set(m,_curr_dist);
|
alpar@209
|
546 |
if (nm[m] && rnode == INVALID) rnode = m;
|
alpar@209
|
547 |
}
|
alpar@100
|
548 |
return n;
|
alpar@100
|
549 |
}
|
alpar@209
|
550 |
|
kpeter@244
|
551 |
///The next node to be processed.
|
alpar@100
|
552 |
|
kpeter@244
|
553 |
///Returns the next node to be processed or \c INVALID if the queue
|
kpeter@244
|
554 |
///is empty.
|
kpeter@244
|
555 |
Node nextNode() const
|
alpar@209
|
556 |
{
|
alpar@100
|
557 |
return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
|
alpar@100
|
558 |
}
|
alpar@209
|
559 |
|
kpeter@405
|
560 |
///Returns \c false if there are nodes to be processed.
|
kpeter@405
|
561 |
|
kpeter@405
|
562 |
///Returns \c false if there are nodes to be processed
|
kpeter@405
|
563 |
///in the queue.
|
kpeter@244
|
564 |
bool emptyQueue() const { return _queue_tail==_queue_head; }
|
kpeter@244
|
565 |
|
alpar@100
|
566 |
///Returns the number of the nodes to be processed.
|
alpar@209
|
567 |
|
kpeter@405
|
568 |
///Returns the number of the nodes to be processed
|
kpeter@405
|
569 |
///in the queue.
|
kpeter@244
|
570 |
int queueSize() const { return _queue_head-_queue_tail; }
|
alpar@209
|
571 |
|
alpar@100
|
572 |
///Executes the algorithm.
|
alpar@100
|
573 |
|
alpar@100
|
574 |
///Executes the algorithm.
|
alpar@100
|
575 |
///
|
kpeter@244
|
576 |
///This method runs the %BFS algorithm from the root node(s)
|
kpeter@244
|
577 |
///in order to compute the shortest path to each node.
|
alpar@100
|
578 |
///
|
kpeter@244
|
579 |
///The algorithm computes
|
kpeter@244
|
580 |
///- the shortest path tree (forest),
|
kpeter@244
|
581 |
///- the distance of each node from the root(s).
|
kpeter@244
|
582 |
///
|
kpeter@244
|
583 |
///\pre init() must be called and at least one root node should be
|
kpeter@244
|
584 |
///added with addSource() before using this function.
|
kpeter@244
|
585 |
///
|
kpeter@244
|
586 |
///\note <tt>b.start()</tt> is just a shortcut of the following code.
|
kpeter@244
|
587 |
///\code
|
kpeter@244
|
588 |
/// while ( !b.emptyQueue() ) {
|
kpeter@244
|
589 |
/// b.processNextNode();
|
kpeter@244
|
590 |
/// }
|
kpeter@244
|
591 |
///\endcode
|
alpar@100
|
592 |
void start()
|
alpar@100
|
593 |
{
|
alpar@100
|
594 |
while ( !emptyQueue() ) processNextNode();
|
alpar@100
|
595 |
}
|
alpar@209
|
596 |
|
kpeter@244
|
597 |
///Executes the algorithm until the given target node is reached.
|
alpar@100
|
598 |
|
kpeter@244
|
599 |
///Executes the algorithm until the given target node is reached.
|
alpar@100
|
600 |
///
|
alpar@100
|
601 |
///This method runs the %BFS algorithm from the root node(s)
|
kpeter@286
|
602 |
///in order to compute the shortest path to \c t.
|
kpeter@244
|
603 |
///
|
alpar@100
|
604 |
///The algorithm computes
|
kpeter@286
|
605 |
///- the shortest path to \c t,
|
kpeter@286
|
606 |
///- the distance of \c t from the root(s).
|
kpeter@244
|
607 |
///
|
kpeter@244
|
608 |
///\pre init() must be called and at least one root node should be
|
kpeter@244
|
609 |
///added with addSource() before using this function.
|
kpeter@244
|
610 |
///
|
kpeter@244
|
611 |
///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
|
kpeter@244
|
612 |
///\code
|
kpeter@244
|
613 |
/// bool reach = false;
|
kpeter@244
|
614 |
/// while ( !b.emptyQueue() && !reach ) {
|
kpeter@244
|
615 |
/// b.processNextNode(t, reach);
|
kpeter@244
|
616 |
/// }
|
kpeter@244
|
617 |
///\endcode
|
kpeter@286
|
618 |
void start(Node t)
|
alpar@100
|
619 |
{
|
alpar@100
|
620 |
bool reach = false;
|
kpeter@286
|
621 |
while ( !emptyQueue() && !reach ) processNextNode(t, reach);
|
alpar@100
|
622 |
}
|
alpar@209
|
623 |
|
alpar@100
|
624 |
///Executes the algorithm until a condition is met.
|
alpar@100
|
625 |
|
alpar@100
|
626 |
///Executes the algorithm until a condition is met.
|
alpar@100
|
627 |
///
|
kpeter@244
|
628 |
///This method runs the %BFS algorithm from the root node(s) in
|
kpeter@244
|
629 |
///order to compute the shortest path to a node \c v with
|
kpeter@244
|
630 |
/// <tt>nm[v]</tt> true, if such a node can be found.
|
alpar@100
|
631 |
///
|
kpeter@244
|
632 |
///\param nm A \c bool (or convertible) node map. The algorithm
|
kpeter@244
|
633 |
///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
|
alpar@100
|
634 |
///
|
alpar@100
|
635 |
///\return The reached node \c v with <tt>nm[v]</tt> true or
|
alpar@100
|
636 |
///\c INVALID if no such node was found.
|
kpeter@244
|
637 |
///
|
kpeter@244
|
638 |
///\pre init() must be called and at least one root node should be
|
kpeter@244
|
639 |
///added with addSource() before using this function.
|
kpeter@244
|
640 |
///
|
kpeter@244
|
641 |
///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
|
kpeter@244
|
642 |
///\code
|
kpeter@244
|
643 |
/// Node rnode = INVALID;
|
kpeter@244
|
644 |
/// while ( !b.emptyQueue() && rnode == INVALID ) {
|
kpeter@244
|
645 |
/// b.processNextNode(nm, rnode);
|
kpeter@244
|
646 |
/// }
|
kpeter@244
|
647 |
/// return rnode;
|
kpeter@244
|
648 |
///\endcode
|
kpeter@244
|
649 |
template<class NodeBoolMap>
|
kpeter@244
|
650 |
Node start(const NodeBoolMap &nm)
|
alpar@100
|
651 |
{
|
alpar@100
|
652 |
Node rnode = INVALID;
|
alpar@100
|
653 |
while ( !emptyQueue() && rnode == INVALID ) {
|
alpar@209
|
654 |
processNextNode(nm, rnode);
|
alpar@100
|
655 |
}
|
alpar@100
|
656 |
return rnode;
|
alpar@100
|
657 |
}
|
alpar@209
|
658 |
|
kpeter@286
|
659 |
///Runs the algorithm from the given source node.
|
alpar@209
|
660 |
|
kpeter@244
|
661 |
///This method runs the %BFS algorithm from node \c s
|
kpeter@244
|
662 |
///in order to compute the shortest path to each node.
|
alpar@100
|
663 |
///
|
kpeter@244
|
664 |
///The algorithm computes
|
kpeter@244
|
665 |
///- the shortest path tree,
|
kpeter@244
|
666 |
///- the distance of each node from the root.
|
kpeter@244
|
667 |
///
|
kpeter@244
|
668 |
///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
|
alpar@100
|
669 |
///\code
|
alpar@100
|
670 |
/// b.init();
|
alpar@100
|
671 |
/// b.addSource(s);
|
alpar@100
|
672 |
/// b.start();
|
alpar@100
|
673 |
///\endcode
|
alpar@100
|
674 |
void run(Node s) {
|
alpar@100
|
675 |
init();
|
alpar@100
|
676 |
addSource(s);
|
alpar@100
|
677 |
start();
|
alpar@100
|
678 |
}
|
alpar@209
|
679 |
|
alpar@100
|
680 |
///Finds the shortest path between \c s and \c t.
|
alpar@209
|
681 |
|
kpeter@244
|
682 |
///This method runs the %BFS algorithm from node \c s
|
kpeter@286
|
683 |
///in order to compute the shortest path to node \c t
|
kpeter@286
|
684 |
///(it stops searching when \c t is processed).
|
alpar@100
|
685 |
///
|
kpeter@286
|
686 |
///\return \c true if \c t is reachable form \c s.
|
kpeter@244
|
687 |
///
|
kpeter@244
|
688 |
///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
|
kpeter@244
|
689 |
///shortcut of the following code.
|
alpar@100
|
690 |
///\code
|
alpar@100
|
691 |
/// b.init();
|
alpar@100
|
692 |
/// b.addSource(s);
|
alpar@100
|
693 |
/// b.start(t);
|
alpar@100
|
694 |
///\endcode
|
kpeter@286
|
695 |
bool run(Node s,Node t) {
|
alpar@100
|
696 |
init();
|
alpar@100
|
697 |
addSource(s);
|
alpar@100
|
698 |
start(t);
|
kpeter@286
|
699 |
return reached(t);
|
alpar@100
|
700 |
}
|
alpar@209
|
701 |
|
kpeter@244
|
702 |
///Runs the algorithm to visit all nodes in the digraph.
|
kpeter@244
|
703 |
|
kpeter@244
|
704 |
///This method runs the %BFS algorithm in order to
|
kpeter@244
|
705 |
///compute the shortest path to each node.
|
kpeter@244
|
706 |
///
|
kpeter@244
|
707 |
///The algorithm computes
|
kpeter@244
|
708 |
///- the shortest path tree (forest),
|
kpeter@244
|
709 |
///- the distance of each node from the root(s).
|
kpeter@244
|
710 |
///
|
kpeter@244
|
711 |
///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
|
kpeter@244
|
712 |
///\code
|
kpeter@244
|
713 |
/// b.init();
|
kpeter@244
|
714 |
/// for (NodeIt n(gr); n != INVALID; ++n) {
|
kpeter@244
|
715 |
/// if (!b.reached(n)) {
|
kpeter@244
|
716 |
/// b.addSource(n);
|
kpeter@244
|
717 |
/// b.start();
|
kpeter@244
|
718 |
/// }
|
kpeter@244
|
719 |
/// }
|
kpeter@244
|
720 |
///\endcode
|
kpeter@244
|
721 |
void run() {
|
kpeter@244
|
722 |
init();
|
kpeter@244
|
723 |
for (NodeIt n(*G); n != INVALID; ++n) {
|
kpeter@244
|
724 |
if (!reached(n)) {
|
kpeter@244
|
725 |
addSource(n);
|
kpeter@244
|
726 |
start();
|
kpeter@244
|
727 |
}
|
kpeter@244
|
728 |
}
|
kpeter@244
|
729 |
}
|
kpeter@244
|
730 |
|
alpar@100
|
731 |
///@}
|
alpar@100
|
732 |
|
alpar@100
|
733 |
///\name Query Functions
|
kpeter@405
|
734 |
///The results of the BFS algorithm can be obtained using these
|
alpar@100
|
735 |
///functions.\n
|
kpeter@405
|
736 |
///Either \ref run(Node) "run()" or \ref start() should be called
|
kpeter@405
|
737 |
///before using them.
|
alpar@209
|
738 |
|
alpar@100
|
739 |
///@{
|
alpar@100
|
740 |
|
kpeter@716
|
741 |
///The shortest path to the given node.
|
alpar@100
|
742 |
|
kpeter@716
|
743 |
///Returns the shortest path to the given node from the root(s).
|
kpeter@244
|
744 |
///
|
kpeter@405
|
745 |
///\warning \c t should be reached from the root(s).
|
kpeter@244
|
746 |
///
|
kpeter@405
|
747 |
///\pre Either \ref run(Node) "run()" or \ref init()
|
kpeter@405
|
748 |
///must be called before using this function.
|
kpeter@244
|
749 |
Path path(Node t) const { return Path(*G, *_pred, t); }
|
alpar@100
|
750 |
|
kpeter@716
|
751 |
///The distance of the given node from the root(s).
|
alpar@100
|
752 |
|
kpeter@716
|
753 |
///Returns the distance of the given node from the root(s).
|
kpeter@244
|
754 |
///
|
kpeter@405
|
755 |
///\warning If node \c v is not reached from the root(s), then
|
kpeter@244
|
756 |
///the return value of this function is undefined.
|
kpeter@244
|
757 |
///
|
kpeter@405
|
758 |
///\pre Either \ref run(Node) "run()" or \ref init()
|
kpeter@405
|
759 |
///must be called before using this function.
|
alpar@100
|
760 |
int dist(Node v) const { return (*_dist)[v]; }
|
alpar@100
|
761 |
|
kpeter@716
|
762 |
///\brief Returns the 'previous arc' of the shortest path tree for
|
kpeter@716
|
763 |
///the given node.
|
kpeter@716
|
764 |
///
|
kpeter@244
|
765 |
///This function returns the 'previous arc' of the shortest path
|
kpeter@244
|
766 |
///tree for the node \c v, i.e. it returns the last arc of a
|
kpeter@405
|
767 |
///shortest path from a root to \c v. It is \c INVALID if \c v
|
kpeter@405
|
768 |
///is not reached from the root(s) or if \c v is a root.
|
kpeter@244
|
769 |
///
|
kpeter@244
|
770 |
///The shortest path tree used here is equal to the shortest path
|
kpeter@716
|
771 |
///tree used in \ref predNode() and \ref predMap().
|
kpeter@244
|
772 |
///
|
kpeter@405
|
773 |
///\pre Either \ref run(Node) "run()" or \ref init()
|
kpeter@405
|
774 |
///must be called before using this function.
|
alpar@100
|
775 |
Arc predArc(Node v) const { return (*_pred)[v];}
|
alpar@100
|
776 |
|
kpeter@716
|
777 |
///\brief Returns the 'previous node' of the shortest path tree for
|
kpeter@716
|
778 |
///the given node.
|
kpeter@716
|
779 |
///
|
kpeter@244
|
780 |
///This function returns the 'previous node' of the shortest path
|
kpeter@244
|
781 |
///tree for the node \c v, i.e. it returns the last but one node
|
kpeter@716
|
782 |
///of a shortest path from a root to \c v. It is \c INVALID
|
kpeter@405
|
783 |
///if \c v is not reached from the root(s) or if \c v is a root.
|
kpeter@244
|
784 |
///
|
alpar@100
|
785 |
///The shortest path tree used here is equal to the shortest path
|
kpeter@716
|
786 |
///tree used in \ref predArc() and \ref predMap().
|
kpeter@244
|
787 |
///
|
kpeter@405
|
788 |
///\pre Either \ref run(Node) "run()" or \ref init()
|
kpeter@405
|
789 |
///must be called before using this function.
|
alpar@100
|
790 |
Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
|
alpar@209
|
791 |
G->source((*_pred)[v]); }
|
alpar@209
|
792 |
|
kpeter@244
|
793 |
///\brief Returns a const reference to the node map that stores the
|
kpeter@244
|
794 |
/// distances of the nodes.
|
kpeter@244
|
795 |
///
|
kpeter@244
|
796 |
///Returns a const reference to the node map that stores the distances
|
kpeter@244
|
797 |
///of the nodes calculated by the algorithm.
|
kpeter@244
|
798 |
///
|
kpeter@405
|
799 |
///\pre Either \ref run(Node) "run()" or \ref init()
|
kpeter@244
|
800 |
///must be called before using this function.
|
alpar@100
|
801 |
const DistMap &distMap() const { return *_dist;}
|
alpar@209
|
802 |
|
kpeter@244
|
803 |
///\brief Returns a const reference to the node map that stores the
|
kpeter@244
|
804 |
///predecessor arcs.
|
kpeter@244
|
805 |
///
|
kpeter@244
|
806 |
///Returns a const reference to the node map that stores the predecessor
|
kpeter@716
|
807 |
///arcs, which form the shortest path tree (forest).
|
kpeter@244
|
808 |
///
|
kpeter@405
|
809 |
///\pre Either \ref run(Node) "run()" or \ref init()
|
alpar@100
|
810 |
///must be called before using this function.
|
alpar@100
|
811 |
const PredMap &predMap() const { return *_pred;}
|
alpar@209
|
812 |
|
kpeter@716
|
813 |
///Checks if the given node is reached from the root(s).
|
alpar@100
|
814 |
|
kpeter@405
|
815 |
///Returns \c true if \c v is reached from the root(s).
|
kpeter@405
|
816 |
///
|
kpeter@405
|
817 |
///\pre Either \ref run(Node) "run()" or \ref init()
|
alpar@100
|
818 |
///must be called before using this function.
|
kpeter@244
|
819 |
bool reached(Node v) const { return (*_reached)[v]; }
|
alpar@209
|
820 |
|
alpar@100
|
821 |
///@}
|
alpar@100
|
822 |
};
|
alpar@100
|
823 |
|
kpeter@244
|
824 |
///Default traits class of bfs() function.
|
alpar@100
|
825 |
|
kpeter@244
|
826 |
///Default traits class of bfs() function.
|
kpeter@157
|
827 |
///\tparam GR Digraph type.
|
alpar@100
|
828 |
template<class GR>
|
alpar@100
|
829 |
struct BfsWizardDefaultTraits
|
alpar@100
|
830 |
{
|
kpeter@244
|
831 |
///The type of the digraph the algorithm runs on.
|
alpar@100
|
832 |
typedef GR Digraph;
|
kpeter@244
|
833 |
|
kpeter@244
|
834 |
///\brief The type of the map that stores the predecessor
|
alpar@100
|
835 |
///arcs of the shortest paths.
|
alpar@209
|
836 |
///
|
kpeter@244
|
837 |
///The type of the map that stores the predecessor
|
alpar@100
|
838 |
///arcs of the shortest paths.
|
kpeter@716
|
839 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@278
|
840 |
typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
|
kpeter@301
|
841 |
///Instantiates a PredMap.
|
alpar@209
|
842 |
|
kpeter@301
|
843 |
///This function instantiates a PredMap.
|
kpeter@244
|
844 |
///\param g is the digraph, to which we would like to define the
|
kpeter@301
|
845 |
///PredMap.
|
kpeter@244
|
846 |
static PredMap *createPredMap(const Digraph &g)
|
alpar@100
|
847 |
{
|
kpeter@278
|
848 |
return new PredMap(g);
|
alpar@100
|
849 |
}
|
alpar@100
|
850 |
|
alpar@100
|
851 |
///The type of the map that indicates which nodes are processed.
|
alpar@209
|
852 |
|
alpar@100
|
853 |
///The type of the map that indicates which nodes are processed.
|
kpeter@716
|
854 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@278
|
855 |
///By default it is a NullMap.
|
alpar@100
|
856 |
typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
|
kpeter@301
|
857 |
///Instantiates a ProcessedMap.
|
alpar@209
|
858 |
|
kpeter@301
|
859 |
///This function instantiates a ProcessedMap.
|
alpar@100
|
860 |
///\param g is the digraph, to which
|
kpeter@301
|
861 |
///we would like to define the ProcessedMap.
|
alpar@100
|
862 |
#ifdef DOXYGEN
|
kpeter@244
|
863 |
static ProcessedMap *createProcessedMap(const Digraph &g)
|
alpar@100
|
864 |
#else
|
kpeter@244
|
865 |
static ProcessedMap *createProcessedMap(const Digraph &)
|
alpar@100
|
866 |
#endif
|
alpar@100
|
867 |
{
|
alpar@100
|
868 |
return new ProcessedMap();
|
alpar@100
|
869 |
}
|
kpeter@244
|
870 |
|
alpar@100
|
871 |
///The type of the map that indicates which nodes are reached.
|
alpar@209
|
872 |
|
alpar@100
|
873 |
///The type of the map that indicates which nodes are reached.
|
kpeter@716
|
874 |
///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
|
alpar@100
|
875 |
typedef typename Digraph::template NodeMap<bool> ReachedMap;
|
kpeter@301
|
876 |
///Instantiates a ReachedMap.
|
alpar@209
|
877 |
|
kpeter@301
|
878 |
///This function instantiates a ReachedMap.
|
kpeter@244
|
879 |
///\param g is the digraph, to which
|
kpeter@301
|
880 |
///we would like to define the ReachedMap.
|
kpeter@244
|
881 |
static ReachedMap *createReachedMap(const Digraph &g)
|
alpar@100
|
882 |
{
|
kpeter@244
|
883 |
return new ReachedMap(g);
|
alpar@100
|
884 |
}
|
alpar@209
|
885 |
|
kpeter@244
|
886 |
///The type of the map that stores the distances of the nodes.
|
kpeter@244
|
887 |
|
kpeter@244
|
888 |
///The type of the map that stores the distances of the nodes.
|
kpeter@716
|
889 |
///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
|
kpeter@278
|
890 |
typedef typename Digraph::template NodeMap<int> DistMap;
|
kpeter@301
|
891 |
///Instantiates a DistMap.
|
alpar@209
|
892 |
|
kpeter@301
|
893 |
///This function instantiates a DistMap.
|
alpar@210
|
894 |
///\param g is the digraph, to which we would like to define
|
kpeter@301
|
895 |
///the DistMap
|
kpeter@244
|
896 |
static DistMap *createDistMap(const Digraph &g)
|
alpar@100
|
897 |
{
|
kpeter@278
|
898 |
return new DistMap(g);
|
alpar@100
|
899 |
}
|
kpeter@278
|
900 |
|
kpeter@278
|
901 |
///The type of the shortest paths.
|
kpeter@278
|
902 |
|
kpeter@278
|
903 |
///The type of the shortest paths.
|
kpeter@716
|
904 |
///It must conform to the \ref concepts::Path "Path" concept.
|
kpeter@278
|
905 |
typedef lemon::Path<Digraph> Path;
|
alpar@100
|
906 |
};
|
alpar@209
|
907 |
|
kpeter@301
|
908 |
/// Default traits class used by BfsWizard
|
alpar@100
|
909 |
|
kpeter@716
|
910 |
/// Default traits class used by BfsWizard.
|
kpeter@716
|
911 |
/// \tparam GR The type of the digraph.
|
alpar@100
|
912 |
template<class GR>
|
alpar@100
|
913 |
class BfsWizardBase : public BfsWizardDefaultTraits<GR>
|
alpar@100
|
914 |
{
|
alpar@100
|
915 |
|
alpar@100
|
916 |
typedef BfsWizardDefaultTraits<GR> Base;
|
alpar@100
|
917 |
protected:
|
kpeter@244
|
918 |
//The type of the nodes in the digraph.
|
alpar@100
|
919 |
typedef typename Base::Digraph::Node Node;
|
alpar@100
|
920 |
|
kpeter@244
|
921 |
//Pointer to the digraph the algorithm runs on.
|
alpar@100
|
922 |
void *_g;
|
kpeter@244
|
923 |
//Pointer to the map of reached nodes.
|
alpar@100
|
924 |
void *_reached;
|
kpeter@244
|
925 |
//Pointer to the map of processed nodes.
|
alpar@100
|
926 |
void *_processed;
|
kpeter@244
|
927 |
//Pointer to the map of predecessors arcs.
|
alpar@100
|
928 |
void *_pred;
|
kpeter@244
|
929 |
//Pointer to the map of distances.
|
alpar@100
|
930 |
void *_dist;
|
kpeter@278
|
931 |
//Pointer to the shortest path to the target node.
|
kpeter@278
|
932 |
void *_path;
|
kpeter@278
|
933 |
//Pointer to the distance of the target node.
|
kpeter@278
|
934 |
int *_di;
|
alpar@209
|
935 |
|
alpar@100
|
936 |
public:
|
alpar@100
|
937 |
/// Constructor.
|
alpar@209
|
938 |
|
kpeter@716
|
939 |
/// This constructor does not require parameters, it initiates
|
kpeter@278
|
940 |
/// all of the attributes to \c 0.
|
alpar@100
|
941 |
BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
|
kpeter@278
|
942 |
_dist(0), _path(0), _di(0) {}
|
alpar@100
|
943 |
|
alpar@100
|
944 |
/// Constructor.
|
alpar@209
|
945 |
|
kpeter@278
|
946 |
/// This constructor requires one parameter,
|
kpeter@278
|
947 |
/// others are initiated to \c 0.
|
kpeter@244
|
948 |
/// \param g The digraph the algorithm runs on.
|
kpeter@278
|
949 |
BfsWizardBase(const GR &g) :
|
alpar@209
|
950 |
_g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
|
kpeter@278
|
951 |
_reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
|
alpar@100
|
952 |
|
alpar@100
|
953 |
};
|
alpar@209
|
954 |
|
kpeter@278
|
955 |
/// Auxiliary class for the function-type interface of BFS algorithm.
|
alpar@100
|
956 |
|
kpeter@278
|
957 |
/// This auxiliary class is created to implement the
|
kpeter@278
|
958 |
/// \ref bfs() "function-type interface" of \ref Bfs algorithm.
|
kpeter@405
|
959 |
/// It does not have own \ref run(Node) "run()" method, it uses the
|
kpeter@405
|
960 |
/// functions and features of the plain \ref Bfs.
|
alpar@100
|
961 |
///
|
kpeter@278
|
962 |
/// This class should only be used through the \ref bfs() function,
|
kpeter@278
|
963 |
/// which makes it easier to use the algorithm.
|
alpar@100
|
964 |
template<class TR>
|
alpar@100
|
965 |
class BfsWizard : public TR
|
alpar@100
|
966 |
{
|
alpar@100
|
967 |
typedef TR Base;
|
alpar@100
|
968 |
|
alpar@100
|
969 |
typedef typename TR::Digraph Digraph;
|
kpeter@244
|
970 |
|
alpar@100
|
971 |
typedef typename Digraph::Node Node;
|
alpar@100
|
972 |
typedef typename Digraph::NodeIt NodeIt;
|
alpar@100
|
973 |
typedef typename Digraph::Arc Arc;
|
alpar@100
|
974 |
typedef typename Digraph::OutArcIt OutArcIt;
|
alpar@209
|
975 |
|
alpar@100
|
976 |
typedef typename TR::PredMap PredMap;
|
alpar@100
|
977 |
typedef typename TR::DistMap DistMap;
|
kpeter@244
|
978 |
typedef typename TR::ReachedMap ReachedMap;
|
kpeter@244
|
979 |
typedef typename TR::ProcessedMap ProcessedMap;
|
kpeter@278
|
980 |
typedef typename TR::Path Path;
|
alpar@100
|
981 |
|
alpar@100
|
982 |
public:
|
kpeter@244
|
983 |
|
alpar@100
|
984 |
/// Constructor.
|
alpar@100
|
985 |
BfsWizard() : TR() {}
|
alpar@100
|
986 |
|
alpar@100
|
987 |
/// Constructor that requires parameters.
|
alpar@100
|
988 |
|
alpar@100
|
989 |
/// Constructor that requires parameters.
|
alpar@100
|
990 |
/// These parameters will be the default values for the traits class.
|
kpeter@278
|
991 |
/// \param g The digraph the algorithm runs on.
|
kpeter@278
|
992 |
BfsWizard(const Digraph &g) :
|
kpeter@278
|
993 |
TR(g) {}
|
alpar@100
|
994 |
|
alpar@100
|
995 |
///Copy constructor
|
alpar@100
|
996 |
BfsWizard(const TR &b) : TR(b) {}
|
alpar@100
|
997 |
|
alpar@100
|
998 |
~BfsWizard() {}
|
alpar@100
|
999 |
|
kpeter@278
|
1000 |
///Runs BFS algorithm from the given source node.
|
alpar@209
|
1001 |
|
kpeter@278
|
1002 |
///This method runs BFS algorithm from node \c s
|
kpeter@278
|
1003 |
///in order to compute the shortest path to each node.
|
kpeter@278
|
1004 |
void run(Node s)
|
kpeter@278
|
1005 |
{
|
kpeter@278
|
1006 |
Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
|
kpeter@278
|
1007 |
if (Base::_pred)
|
kpeter@278
|
1008 |
alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
|
kpeter@278
|
1009 |
if (Base::_dist)
|
kpeter@278
|
1010 |
alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
|
kpeter@278
|
1011 |
if (Base::_reached)
|
kpeter@278
|
1012 |
alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
|
kpeter@278
|
1013 |
if (Base::_processed)
|
kpeter@278
|
1014 |
alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
|
kpeter@278
|
1015 |
if (s!=INVALID)
|
kpeter@278
|
1016 |
alg.run(s);
|
kpeter@278
|
1017 |
else
|
kpeter@278
|
1018 |
alg.run();
|
kpeter@278
|
1019 |
}
|
kpeter@278
|
1020 |
|
kpeter@278
|
1021 |
///Finds the shortest path between \c s and \c t.
|
kpeter@278
|
1022 |
|
kpeter@278
|
1023 |
///This method runs BFS algorithm from node \c s
|
kpeter@278
|
1024 |
///in order to compute the shortest path to node \c t
|
kpeter@278
|
1025 |
///(it stops searching when \c t is processed).
|
kpeter@278
|
1026 |
///
|
kpeter@278
|
1027 |
///\return \c true if \c t is reachable form \c s.
|
kpeter@278
|
1028 |
bool run(Node s, Node t)
|
kpeter@278
|
1029 |
{
|
kpeter@278
|
1030 |
Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
|
kpeter@278
|
1031 |
if (Base::_pred)
|
kpeter@278
|
1032 |
alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
|
kpeter@278
|
1033 |
if (Base::_dist)
|
kpeter@278
|
1034 |
alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
|
kpeter@278
|
1035 |
if (Base::_reached)
|
kpeter@278
|
1036 |
alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
|
kpeter@278
|
1037 |
if (Base::_processed)
|
kpeter@278
|
1038 |
alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
|
kpeter@278
|
1039 |
alg.run(s,t);
|
kpeter@278
|
1040 |
if (Base::_path)
|
kpeter@278
|
1041 |
*reinterpret_cast<Path*>(Base::_path) = alg.path(t);
|
kpeter@278
|
1042 |
if (Base::_di)
|
kpeter@278
|
1043 |
*Base::_di = alg.dist(t);
|
kpeter@278
|
1044 |
return alg.reached(t);
|
kpeter@278
|
1045 |
}
|
kpeter@278
|
1046 |
|
kpeter@278
|
1047 |
///Runs BFS algorithm to visit all nodes in the digraph.
|
kpeter@278
|
1048 |
|
kpeter@278
|
1049 |
///This method runs BFS algorithm in order to compute
|
kpeter@278
|
1050 |
///the shortest path to each node.
|
alpar@100
|
1051 |
void run()
|
alpar@100
|
1052 |
{
|
kpeter@278
|
1053 |
run(INVALID);
|
alpar@100
|
1054 |
}
|
alpar@209
|
1055 |
|
kpeter@244
|
1056 |
template<class T>
|
kpeter@257
|
1057 |
struct SetPredMapBase : public Base {
|
kpeter@244
|
1058 |
typedef T PredMap;
|
kpeter@244
|
1059 |
static PredMap *createPredMap(const Digraph &) { return 0; };
|
kpeter@257
|
1060 |
SetPredMapBase(const TR &b) : TR(b) {}
|
kpeter@244
|
1061 |
};
|
kpeter@716
|
1062 |
|
kpeter@716
|
1063 |
///\brief \ref named-templ-param "Named parameter" for setting
|
kpeter@716
|
1064 |
///the predecessor map.
|
kpeter@244
|
1065 |
///
|
kpeter@716
|
1066 |
///\ref named-templ-param "Named parameter" function for setting
|
kpeter@716
|
1067 |
///the map that stores the predecessor arcs of the nodes.
|
kpeter@244
|
1068 |
template<class T>
|
kpeter@257
|
1069 |
BfsWizard<SetPredMapBase<T> > predMap(const T &t)
|
kpeter@244
|
1070 |
{
|
kpeter@244
|
1071 |
Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
|
kpeter@257
|
1072 |
return BfsWizard<SetPredMapBase<T> >(*this);
|
kpeter@244
|
1073 |
}
|
kpeter@244
|
1074 |
|
kpeter@244
|
1075 |
template<class T>
|
kpeter@257
|
1076 |
struct SetReachedMapBase : public Base {
|
kpeter@244
|
1077 |
typedef T ReachedMap;
|
kpeter@244
|
1078 |
static ReachedMap *createReachedMap(const Digraph &) { return 0; };
|
kpeter@257
|
1079 |
SetReachedMapBase(const TR &b) : TR(b) {}
|
kpeter@244
|
1080 |
};
|
kpeter@716
|
1081 |
|
kpeter@716
|
1082 |
///\brief \ref named-templ-param "Named parameter" for setting
|
kpeter@716
|
1083 |
///the reached map.
|
kpeter@244
|
1084 |
///
|
kpeter@716
|
1085 |
///\ref named-templ-param "Named parameter" function for setting
|
kpeter@716
|
1086 |
///the map that indicates which nodes are reached.
|
kpeter@244
|
1087 |
template<class T>
|
kpeter@257
|
1088 |
BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
|
kpeter@244
|
1089 |
{
|
kpeter@244
|
1090 |
Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
|
kpeter@257
|
1091 |
return BfsWizard<SetReachedMapBase<T> >(*this);
|
kpeter@244
|
1092 |
}
|
kpeter@244
|
1093 |
|
kpeter@244
|
1094 |
template<class T>
|
kpeter@278
|
1095 |
struct SetDistMapBase : public Base {
|
kpeter@278
|
1096 |
typedef T DistMap;
|
kpeter@278
|
1097 |
static DistMap *createDistMap(const Digraph &) { return 0; };
|
kpeter@278
|
1098 |
SetDistMapBase(const TR &b) : TR(b) {}
|
kpeter@278
|
1099 |
};
|
kpeter@716
|
1100 |
|
kpeter@716
|
1101 |
///\brief \ref named-templ-param "Named parameter" for setting
|
kpeter@716
|
1102 |
///the distance map.
|
kpeter@278
|
1103 |
///
|
kpeter@716
|
1104 |
///\ref named-templ-param "Named parameter" function for setting
|
kpeter@716
|
1105 |
///the map that stores the distances of the nodes calculated
|
kpeter@716
|
1106 |
///by the algorithm.
|
kpeter@278
|
1107 |
template<class T>
|
kpeter@278
|
1108 |
BfsWizard<SetDistMapBase<T> > distMap(const T &t)
|
kpeter@278
|
1109 |
{
|
kpeter@278
|
1110 |
Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
|
kpeter@278
|
1111 |
return BfsWizard<SetDistMapBase<T> >(*this);
|
kpeter@278
|
1112 |
}
|
kpeter@278
|
1113 |
|
kpeter@278
|
1114 |
template<class T>
|
kpeter@257
|
1115 |
struct SetProcessedMapBase : public Base {
|
kpeter@244
|
1116 |
typedef T ProcessedMap;
|
kpeter@244
|
1117 |
static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
|
kpeter@257
|
1118 |
SetProcessedMapBase(const TR &b) : TR(b) {}
|
kpeter@244
|
1119 |
};
|
kpeter@716
|
1120 |
|
kpeter@716
|
1121 |
///\brief \ref named-func-param "Named parameter" for setting
|
kpeter@716
|
1122 |
///the processed map.
|
kpeter@244
|
1123 |
///
|
kpeter@716
|
1124 |
///\ref named-templ-param "Named parameter" function for setting
|
kpeter@716
|
1125 |
///the map that indicates which nodes are processed.
|
kpeter@244
|
1126 |
template<class T>
|
kpeter@257
|
1127 |
BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
|
kpeter@244
|
1128 |
{
|
kpeter@244
|
1129 |
Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
|
kpeter@257
|
1130 |
return BfsWizard<SetProcessedMapBase<T> >(*this);
|
kpeter@244
|
1131 |
}
|
kpeter@244
|
1132 |
|
kpeter@244
|
1133 |
template<class T>
|
kpeter@278
|
1134 |
struct SetPathBase : public Base {
|
kpeter@278
|
1135 |
typedef T Path;
|
kpeter@278
|
1136 |
SetPathBase(const TR &b) : TR(b) {}
|
kpeter@244
|
1137 |
};
|
kpeter@278
|
1138 |
///\brief \ref named-func-param "Named parameter"
|
kpeter@278
|
1139 |
///for getting the shortest path to the target node.
|
kpeter@244
|
1140 |
///
|
kpeter@278
|
1141 |
///\ref named-func-param "Named parameter"
|
kpeter@278
|
1142 |
///for getting the shortest path to the target node.
|
kpeter@244
|
1143 |
template<class T>
|
kpeter@278
|
1144 |
BfsWizard<SetPathBase<T> > path(const T &t)
|
kpeter@244
|
1145 |
{
|
kpeter@278
|
1146 |
Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
|
kpeter@278
|
1147 |
return BfsWizard<SetPathBase<T> >(*this);
|
kpeter@278
|
1148 |
}
|
kpeter@278
|
1149 |
|
kpeter@278
|
1150 |
///\brief \ref named-func-param "Named parameter"
|
kpeter@278
|
1151 |
///for getting the distance of the target node.
|
kpeter@278
|
1152 |
///
|
kpeter@278
|
1153 |
///\ref named-func-param "Named parameter"
|
kpeter@278
|
1154 |
///for getting the distance of the target node.
|
kpeter@278
|
1155 |
BfsWizard dist(const int &d)
|
kpeter@278
|
1156 |
{
|
kpeter@278
|
1157 |
Base::_di=const_cast<int*>(&d);
|
kpeter@278
|
1158 |
return *this;
|
kpeter@244
|
1159 |
}
|
kpeter@244
|
1160 |
|
alpar@100
|
1161 |
};
|
alpar@209
|
1162 |
|
kpeter@278
|
1163 |
///Function-type interface for BFS algorithm.
|
alpar@100
|
1164 |
|
alpar@100
|
1165 |
/// \ingroup search
|
kpeter@278
|
1166 |
///Function-type interface for BFS algorithm.
|
alpar@100
|
1167 |
///
|
kpeter@278
|
1168 |
///This function also has several \ref named-func-param "named parameters",
|
alpar@100
|
1169 |
///they are declared as the members of class \ref BfsWizard.
|
kpeter@278
|
1170 |
///The following examples show how to use these parameters.
|
alpar@100
|
1171 |
///\code
|
kpeter@278
|
1172 |
/// // Compute shortest path from node s to each node
|
kpeter@278
|
1173 |
/// bfs(g).predMap(preds).distMap(dists).run(s);
|
kpeter@278
|
1174 |
///
|
kpeter@278
|
1175 |
/// // Compute shortest path from s to t
|
kpeter@278
|
1176 |
/// bool reached = bfs(g).path(p).dist(d).run(s,t);
|
alpar@100
|
1177 |
///\endcode
|
kpeter@405
|
1178 |
///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
|
alpar@100
|
1179 |
///to the end of the parameter list.
|
alpar@100
|
1180 |
///\sa BfsWizard
|
alpar@100
|
1181 |
///\sa Bfs
|
alpar@100
|
1182 |
template<class GR>
|
alpar@100
|
1183 |
BfsWizard<BfsWizardBase<GR> >
|
kpeter@278
|
1184 |
bfs(const GR &digraph)
|
alpar@100
|
1185 |
{
|
kpeter@278
|
1186 |
return BfsWizard<BfsWizardBase<GR> >(digraph);
|
alpar@100
|
1187 |
}
|
alpar@100
|
1188 |
|
alpar@100
|
1189 |
#ifdef DOXYGEN
|
kpeter@244
|
1190 |
/// \brief Visitor class for BFS.
|
alpar@209
|
1191 |
///
|
alpar@100
|
1192 |
/// This class defines the interface of the BfsVisit events, and
|
kpeter@244
|
1193 |
/// it could be the base of a real visitor class.
|
kpeter@503
|
1194 |
template <typename GR>
|
alpar@100
|
1195 |
struct BfsVisitor {
|
kpeter@503
|
1196 |
typedef GR Digraph;
|
alpar@100
|
1197 |
typedef typename Digraph::Arc Arc;
|
alpar@100
|
1198 |
typedef typename Digraph::Node Node;
|
kpeter@244
|
1199 |
/// \brief Called for the source node(s) of the BFS.
|
alpar@209
|
1200 |
///
|
kpeter@244
|
1201 |
/// This function is called for the source node(s) of the BFS.
|
kpeter@244
|
1202 |
void start(const Node& node) {}
|
kpeter@244
|
1203 |
/// \brief Called when a node is reached first time.
|
kpeter@244
|
1204 |
///
|
kpeter@244
|
1205 |
/// This function is called when a node is reached first time.
|
kpeter@244
|
1206 |
void reach(const Node& node) {}
|
kpeter@244
|
1207 |
/// \brief Called when a node is processed.
|
kpeter@244
|
1208 |
///
|
kpeter@244
|
1209 |
/// This function is called when a node is processed.
|
kpeter@244
|
1210 |
void process(const Node& node) {}
|
kpeter@244
|
1211 |
/// \brief Called when an arc reaches a new node.
|
kpeter@244
|
1212 |
///
|
kpeter@244
|
1213 |
/// This function is called when the BFS finds an arc whose target node
|
kpeter@244
|
1214 |
/// is not reached yet.
|
alpar@100
|
1215 |
void discover(const Arc& arc) {}
|
kpeter@244
|
1216 |
/// \brief Called when an arc is examined but its target node is
|
alpar@100
|
1217 |
/// already discovered.
|
alpar@209
|
1218 |
///
|
kpeter@244
|
1219 |
/// This function is called when an arc is examined but its target node is
|
alpar@100
|
1220 |
/// already discovered.
|
alpar@100
|
1221 |
void examine(const Arc& arc) {}
|
alpar@100
|
1222 |
};
|
alpar@100
|
1223 |
#else
|
kpeter@503
|
1224 |
template <typename GR>
|
alpar@100
|
1225 |
struct BfsVisitor {
|
kpeter@503
|
1226 |
typedef GR Digraph;
|
alpar@100
|
1227 |
typedef typename Digraph::Arc Arc;
|
alpar@100
|
1228 |
typedef typename Digraph::Node Node;
|
kpeter@244
|
1229 |
void start(const Node&) {}
|
kpeter@244
|
1230 |
void reach(const Node&) {}
|
kpeter@244
|
1231 |
void process(const Node&) {}
|
alpar@100
|
1232 |
void discover(const Arc&) {}
|
alpar@100
|
1233 |
void examine(const Arc&) {}
|
alpar@100
|
1234 |
|
alpar@100
|
1235 |
template <typename _Visitor>
|
alpar@100
|
1236 |
struct Constraints {
|
alpar@100
|
1237 |
void constraints() {
|
alpar@209
|
1238 |
Arc arc;
|
alpar@209
|
1239 |
Node node;
|
kpeter@244
|
1240 |
visitor.start(node);
|
kpeter@244
|
1241 |
visitor.reach(node);
|
kpeter@244
|
1242 |
visitor.process(node);
|
alpar@209
|
1243 |
visitor.discover(arc);
|
alpar@209
|
1244 |
visitor.examine(arc);
|
alpar@100
|
1245 |
}
|
alpar@100
|
1246 |
_Visitor& visitor;
|
alpar@100
|
1247 |
};
|
alpar@100
|
1248 |
};
|
alpar@100
|
1249 |
#endif
|
alpar@100
|
1250 |
|
alpar@100
|
1251 |
/// \brief Default traits class of BfsVisit class.
|
alpar@100
|
1252 |
///
|
alpar@100
|
1253 |
/// Default traits class of BfsVisit class.
|
kpeter@503
|
1254 |
/// \tparam GR The type of the digraph the algorithm runs on.
|
kpeter@503
|
1255 |
template<class GR>
|
alpar@100
|
1256 |
struct BfsVisitDefaultTraits {
|
alpar@100
|
1257 |
|
kpeter@244
|
1258 |
/// \brief The type of the digraph the algorithm runs on.
|
kpeter@503
|
1259 |
typedef GR Digraph;
|
alpar@100
|
1260 |
|
alpar@100
|
1261 |
/// \brief The type of the map that indicates which nodes are reached.
|
alpar@209
|
1262 |
///
|
alpar@100
|
1263 |
/// The type of the map that indicates which nodes are reached.
|
kpeter@716
|
1264 |
/// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
|
alpar@100
|
1265 |
typedef typename Digraph::template NodeMap<bool> ReachedMap;
|
alpar@100
|
1266 |
|
kpeter@301
|
1267 |
/// \brief Instantiates a ReachedMap.
|
alpar@100
|
1268 |
///
|
kpeter@301
|
1269 |
/// This function instantiates a ReachedMap.
|
alpar@100
|
1270 |
/// \param digraph is the digraph, to which
|
kpeter@301
|
1271 |
/// we would like to define the ReachedMap.
|
alpar@100
|
1272 |
static ReachedMap *createReachedMap(const Digraph &digraph) {
|
alpar@100
|
1273 |
return new ReachedMap(digraph);
|
alpar@100
|
1274 |
}
|
alpar@100
|
1275 |
|
alpar@100
|
1276 |
};
|
alpar@100
|
1277 |
|
alpar@100
|
1278 |
/// \ingroup search
|
alpar@209
|
1279 |
///
|
kpeter@503
|
1280 |
/// \brief BFS algorithm class with visitor interface.
|
alpar@209
|
1281 |
///
|
kpeter@503
|
1282 |
/// This class provides an efficient implementation of the BFS algorithm
|
alpar@100
|
1283 |
/// with visitor interface.
|
alpar@100
|
1284 |
///
|
kpeter@503
|
1285 |
/// The BfsVisit class provides an alternative interface to the Bfs
|
alpar@100
|
1286 |
/// class. It works with callback mechanism, the BfsVisit object calls
|
kpeter@244
|
1287 |
/// the member functions of the \c Visitor class on every BFS event.
|
alpar@100
|
1288 |
///
|
kpeter@252
|
1289 |
/// This interface of the BFS algorithm should be used in special cases
|
kpeter@252
|
1290 |
/// when extra actions have to be performed in connection with certain
|
kpeter@252
|
1291 |
/// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
|
kpeter@252
|
1292 |
/// instead.
|
kpeter@252
|
1293 |
///
|
kpeter@503
|
1294 |
/// \tparam GR The type of the digraph the algorithm runs on.
|
kpeter@503
|
1295 |
/// The default type is \ref ListDigraph.
|
kpeter@503
|
1296 |
/// The value of GR is not used directly by \ref BfsVisit,
|
kpeter@503
|
1297 |
/// it is only passed to \ref BfsVisitDefaultTraits.
|
kpeter@503
|
1298 |
/// \tparam VS The Visitor type that is used by the algorithm.
|
kpeter@503
|
1299 |
/// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
|
kpeter@244
|
1300 |
/// does not observe the BFS events. If you want to observe the BFS
|
kpeter@244
|
1301 |
/// events, you should implement your own visitor class.
|
kpeter@503
|
1302 |
/// \tparam TR Traits class to set various data types used by the
|
alpar@100
|
1303 |
/// algorithm. The default traits class is
|
kpeter@503
|
1304 |
/// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
|
alpar@100
|
1305 |
/// See \ref BfsVisitDefaultTraits for the documentation of
|
kpeter@244
|
1306 |
/// a BFS visit traits class.
|
alpar@100
|
1307 |
#ifdef DOXYGEN
|
kpeter@503
|
1308 |
template <typename GR, typename VS, typename TR>
|
alpar@100
|
1309 |
#else
|
kpeter@503
|
1310 |
template <typename GR = ListDigraph,
|
kpeter@503
|
1311 |
typename VS = BfsVisitor<GR>,
|
kpeter@503
|
1312 |
typename TR = BfsVisitDefaultTraits<GR> >
|
alpar@100
|
1313 |
#endif
|
alpar@100
|
1314 |
class BfsVisit {
|
alpar@100
|
1315 |
public:
|
alpar@209
|
1316 |
|
kpeter@244
|
1317 |
///The traits class.
|
kpeter@503
|
1318 |
typedef TR Traits;
|
alpar@100
|
1319 |
|
kpeter@244
|
1320 |
///The type of the digraph the algorithm runs on.
|
alpar@100
|
1321 |
typedef typename Traits::Digraph Digraph;
|
alpar@100
|
1322 |
|
kpeter@244
|
1323 |
///The visitor type used by the algorithm.
|
kpeter@503
|
1324 |
typedef VS Visitor;
|
alpar@100
|
1325 |
|
kpeter@244
|
1326 |
///The type of the map that indicates which nodes are reached.
|
alpar@100
|
1327 |
typedef typename Traits::ReachedMap ReachedMap;
|
alpar@100
|
1328 |
|
alpar@100
|
1329 |
private:
|
alpar@100
|
1330 |
|
alpar@100
|
1331 |
typedef typename Digraph::Node Node;
|
alpar@100
|
1332 |
typedef typename Digraph::NodeIt NodeIt;
|
alpar@100
|
1333 |
typedef typename Digraph::Arc Arc;
|
alpar@100
|
1334 |
typedef typename Digraph::OutArcIt OutArcIt;
|
alpar@100
|
1335 |
|
kpeter@244
|
1336 |
//Pointer to the underlying digraph.
|
alpar@100
|
1337 |
const Digraph *_digraph;
|
kpeter@244
|
1338 |
//Pointer to the visitor object.
|
alpar@100
|
1339 |
Visitor *_visitor;
|
kpeter@244
|
1340 |
//Pointer to the map of reached status of the nodes.
|
alpar@100
|
1341 |
ReachedMap *_reached;
|
kpeter@244
|
1342 |
//Indicates if _reached is locally allocated (true) or not.
|
alpar@100
|
1343 |
bool local_reached;
|
alpar@100
|
1344 |
|
alpar@100
|
1345 |
std::vector<typename Digraph::Node> _list;
|
alpar@100
|
1346 |
int _list_front, _list_back;
|
alpar@100
|
1347 |
|
alpar@280
|
1348 |
//Creates the maps if necessary.
|
alpar@100
|
1349 |
void create_maps() {
|
alpar@100
|
1350 |
if(!_reached) {
|
alpar@209
|
1351 |
local_reached = true;
|
alpar@209
|
1352 |
_reached = Traits::createReachedMap(*_digraph);
|
alpar@100
|
1353 |
}
|
alpar@100
|
1354 |
}
|
alpar@100
|
1355 |
|
alpar@100
|
1356 |
protected:
|
alpar@100
|
1357 |
|
alpar@100
|
1358 |
BfsVisit() {}
|
alpar@209
|
1359 |
|
alpar@100
|
1360 |
public:
|
alpar@100
|
1361 |
|
alpar@100
|
1362 |
typedef BfsVisit Create;
|
alpar@100
|
1363 |
|
kpeter@405
|
1364 |
/// \name Named Template Parameters
|
alpar@100
|
1365 |
|
alpar@100
|
1366 |
///@{
|
alpar@100
|
1367 |
template <class T>
|
kpeter@257
|
1368 |
struct SetReachedMapTraits : public Traits {
|
alpar@100
|
1369 |
typedef T ReachedMap;
|
alpar@100
|
1370 |
static ReachedMap *createReachedMap(const Digraph &digraph) {
|
deba@290
|
1371 |
LEMON_ASSERT(false, "ReachedMap is not initialized");
|
deba@290
|
1372 |
return 0; // ignore warnings
|
alpar@100
|
1373 |
}
|
alpar@100
|
1374 |
};
|
alpar@209
|
1375 |
/// \brief \ref named-templ-param "Named parameter" for setting
|
kpeter@244
|
1376 |
/// ReachedMap type.
|
alpar@100
|
1377 |
///
|
kpeter@244
|
1378 |
/// \ref named-templ-param "Named parameter" for setting ReachedMap type.
|
alpar@100
|
1379 |
template <class T>
|
kpeter@257
|
1380 |
struct SetReachedMap : public BfsVisit< Digraph, Visitor,
|
kpeter@257
|
1381 |
SetReachedMapTraits<T> > {
|
kpeter@257
|
1382 |
typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
|
alpar@100
|
1383 |
};
|
alpar@100
|
1384 |
///@}
|
alpar@100
|
1385 |
|
alpar@209
|
1386 |
public:
|
alpar@209
|
1387 |
|
alpar@100
|
1388 |
/// \brief Constructor.
|
alpar@100
|
1389 |
///
|
alpar@100
|
1390 |
/// Constructor.
|
alpar@100
|
1391 |
///
|
kpeter@244
|
1392 |
/// \param digraph The digraph the algorithm runs on.
|
kpeter@244
|
1393 |
/// \param visitor The visitor object of the algorithm.
|
alpar@209
|
1394 |
BfsVisit(const Digraph& digraph, Visitor& visitor)
|
alpar@100
|
1395 |
: _digraph(&digraph), _visitor(&visitor),
|
alpar@209
|
1396 |
_reached(0), local_reached(false) {}
|
alpar@209
|
1397 |
|
alpar@100
|
1398 |
/// \brief Destructor.
|
alpar@100
|
1399 |
~BfsVisit() {
|
alpar@100
|
1400 |
if(local_reached) delete _reached;
|
alpar@100
|
1401 |
}
|
alpar@100
|
1402 |
|
kpeter@244
|
1403 |
/// \brief Sets the map that indicates which nodes are reached.
|
alpar@100
|
1404 |
///
|
kpeter@244
|
1405 |
/// Sets the map that indicates which nodes are reached.
|
kpeter@405
|
1406 |
/// If you don't use this function before calling \ref run(Node) "run()"
|
kpeter@405
|
1407 |
/// or \ref init(), an instance will be allocated automatically.
|
kpeter@405
|
1408 |
/// The destructor deallocates this automatically allocated map,
|
kpeter@405
|
1409 |
/// of course.
|
alpar@100
|
1410 |
/// \return <tt> (*this) </tt>
|
alpar@100
|
1411 |
BfsVisit &reachedMap(ReachedMap &m) {
|
alpar@100
|
1412 |
if(local_reached) {
|
alpar@209
|
1413 |
delete _reached;
|
alpar@209
|
1414 |
local_reached = false;
|
alpar@100
|
1415 |
}
|
alpar@100
|
1416 |
_reached = &m;
|
alpar@100
|
1417 |
return *this;
|
alpar@100
|
1418 |
}
|
alpar@100
|
1419 |
|
alpar@100
|
1420 |
public:
|
kpeter@244
|
1421 |
|
kpeter@405
|
1422 |
/// \name Execution Control
|
kpeter@405
|
1423 |
/// The simplest way to execute the BFS algorithm is to use one of the
|
kpeter@405
|
1424 |
/// member functions called \ref run(Node) "run()".\n
|
kpeter@405
|
1425 |
/// If you need more control on the execution, first you have to call
|
kpeter@405
|
1426 |
/// \ref init(), then you can add several source nodes with
|
kpeter@405
|
1427 |
/// \ref addSource(). Finally the actual path computation can be
|
kpeter@405
|
1428 |
/// performed with one of the \ref start() functions.
|
alpar@100
|
1429 |
|
alpar@100
|
1430 |
/// @{
|
kpeter@244
|
1431 |
|
alpar@100
|
1432 |
/// \brief Initializes the internal data structures.
|
alpar@100
|
1433 |
///
|
alpar@100
|
1434 |
/// Initializes the internal data structures.
|
alpar@100
|
1435 |
void init() {
|
alpar@100
|
1436 |
create_maps();
|
alpar@100
|
1437 |
_list.resize(countNodes(*_digraph));
|
alpar@100
|
1438 |
_list_front = _list_back = -1;
|
alpar@100
|
1439 |
for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
|
alpar@209
|
1440 |
_reached->set(u, false);
|
alpar@100
|
1441 |
}
|
alpar@100
|
1442 |
}
|
alpar@209
|
1443 |
|
alpar@100
|
1444 |
/// \brief Adds a new source node.
|
alpar@100
|
1445 |
///
|
alpar@100
|
1446 |
/// Adds a new source node to the set of nodes to be processed.
|
alpar@100
|
1447 |
void addSource(Node s) {
|
alpar@100
|
1448 |
if(!(*_reached)[s]) {
|
alpar@209
|
1449 |
_reached->set(s,true);
|
alpar@209
|
1450 |
_visitor->start(s);
|
alpar@209
|
1451 |
_visitor->reach(s);
|
alpar@100
|
1452 |
_list[++_list_back] = s;
|
alpar@209
|
1453 |
}
|
alpar@100
|
1454 |
}
|
alpar@209
|
1455 |
|
alpar@100
|
1456 |
/// \brief Processes the next node.
|
alpar@100
|
1457 |
///
|
alpar@100
|
1458 |
/// Processes the next node.
|
alpar@100
|
1459 |
///
|
alpar@100
|
1460 |
/// \return The processed node.
|
alpar@100
|
1461 |
///
|
kpeter@244
|
1462 |
/// \pre The queue must not be empty.
|
alpar@209
|
1463 |
Node processNextNode() {
|
alpar@100
|
1464 |
Node n = _list[++_list_front];
|
alpar@100
|
1465 |
_visitor->process(n);
|
alpar@100
|
1466 |
Arc e;
|
alpar@100
|
1467 |
for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
|
alpar@100
|
1468 |
Node m = _digraph->target(e);
|
alpar@100
|
1469 |
if (!(*_reached)[m]) {
|
alpar@100
|
1470 |
_visitor->discover(e);
|
alpar@100
|
1471 |
_visitor->reach(m);
|
alpar@100
|
1472 |
_reached->set(m, true);
|
alpar@100
|
1473 |
_list[++_list_back] = m;
|
alpar@100
|
1474 |
} else {
|
alpar@100
|
1475 |
_visitor->examine(e);
|
alpar@100
|
1476 |
}
|
alpar@100
|
1477 |
}
|
alpar@100
|
1478 |
return n;
|
alpar@100
|
1479 |
}
|
alpar@100
|
1480 |
|
alpar@100
|
1481 |
/// \brief Processes the next node.
|
alpar@100
|
1482 |
///
|
kpeter@244
|
1483 |
/// Processes the next node and checks if the given target node
|
alpar@100
|
1484 |
/// is reached. If the target node is reachable from the processed
|
kpeter@244
|
1485 |
/// node, then the \c reach parameter will be set to \c true.
|
alpar@100
|
1486 |
///
|
alpar@100
|
1487 |
/// \param target The target node.
|
kpeter@244
|
1488 |
/// \retval reach Indicates if the target node is reached.
|
kpeter@244
|
1489 |
/// It should be initially \c false.
|
kpeter@244
|
1490 |
///
|
alpar@100
|
1491 |
/// \return The processed node.
|
alpar@100
|
1492 |
///
|
kpeter@244
|
1493 |
/// \pre The queue must not be empty.
|
alpar@100
|
1494 |
Node processNextNode(Node target, bool& reach) {
|
alpar@100
|
1495 |
Node n = _list[++_list_front];
|
alpar@100
|
1496 |
_visitor->process(n);
|
alpar@100
|
1497 |
Arc e;
|
alpar@100
|
1498 |
for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
|
alpar@100
|
1499 |
Node m = _digraph->target(e);
|
alpar@100
|
1500 |
if (!(*_reached)[m]) {
|
alpar@100
|
1501 |
_visitor->discover(e);
|
alpar@100
|
1502 |
_visitor->reach(m);
|
alpar@100
|
1503 |
_reached->set(m, true);
|
alpar@100
|
1504 |
_list[++_list_back] = m;
|
alpar@100
|
1505 |
reach = reach || (target == m);
|
alpar@100
|
1506 |
} else {
|
alpar@100
|
1507 |
_visitor->examine(e);
|
alpar@100
|
1508 |
}
|
alpar@100
|
1509 |
}
|
alpar@100
|
1510 |
return n;
|
alpar@100
|
1511 |
}
|
alpar@100
|
1512 |
|
alpar@100
|
1513 |
/// \brief Processes the next node.
|
alpar@100
|
1514 |
///
|
kpeter@244
|
1515 |
/// Processes the next node and checks if at least one of reached
|
kpeter@244
|
1516 |
/// nodes has \c true value in the \c nm node map. If one node
|
kpeter@244
|
1517 |
/// with \c true value is reachable from the processed node, then the
|
kpeter@244
|
1518 |
/// \c rnode parameter will be set to the first of such nodes.
|
alpar@100
|
1519 |
///
|
kpeter@244
|
1520 |
/// \param nm A \c bool (or convertible) node map that indicates the
|
kpeter@244
|
1521 |
/// possible targets.
|
alpar@100
|
1522 |
/// \retval rnode The reached target node.
|
kpeter@244
|
1523 |
/// It should be initially \c INVALID.
|
kpeter@244
|
1524 |
///
|
alpar@100
|
1525 |
/// \return The processed node.
|
alpar@100
|
1526 |
///
|
kpeter@244
|
1527 |
/// \pre The queue must not be empty.
|
alpar@100
|
1528 |
template <typename NM>
|
alpar@100
|
1529 |
Node processNextNode(const NM& nm, Node& rnode) {
|
alpar@100
|
1530 |
Node n = _list[++_list_front];
|
alpar@100
|
1531 |
_visitor->process(n);
|
alpar@100
|
1532 |
Arc e;
|
alpar@100
|
1533 |
for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
|
alpar@100
|
1534 |
Node m = _digraph->target(e);
|
alpar@100
|
1535 |
if (!(*_reached)[m]) {
|
alpar@100
|
1536 |
_visitor->discover(e);
|
alpar@100
|
1537 |
_visitor->reach(m);
|
alpar@100
|
1538 |
_reached->set(m, true);
|
alpar@100
|
1539 |
_list[++_list_back] = m;
|
alpar@100
|
1540 |
if (nm[m] && rnode == INVALID) rnode = m;
|
alpar@100
|
1541 |
} else {
|
alpar@100
|
1542 |
_visitor->examine(e);
|
alpar@100
|
1543 |
}
|
alpar@100
|
1544 |
}
|
alpar@100
|
1545 |
return n;
|
alpar@100
|
1546 |
}
|
alpar@100
|
1547 |
|
kpeter@244
|
1548 |
/// \brief The next node to be processed.
|
alpar@100
|
1549 |
///
|
kpeter@244
|
1550 |
/// Returns the next node to be processed or \c INVALID if the queue
|
kpeter@244
|
1551 |
/// is empty.
|
kpeter@244
|
1552 |
Node nextNode() const {
|
alpar@100
|
1553 |
return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
|
alpar@100
|
1554 |
}
|
alpar@100
|
1555 |
|
alpar@100
|
1556 |
/// \brief Returns \c false if there are nodes
|
kpeter@244
|
1557 |
/// to be processed.
|
alpar@100
|
1558 |
///
|
alpar@100
|
1559 |
/// Returns \c false if there are nodes
|
kpeter@244
|
1560 |
/// to be processed in the queue.
|
kpeter@244
|
1561 |
bool emptyQueue() const { return _list_front == _list_back; }
|
alpar@100
|
1562 |
|
alpar@100
|
1563 |
/// \brief Returns the number of the nodes to be processed.
|
alpar@100
|
1564 |
///
|
alpar@100
|
1565 |
/// Returns the number of the nodes to be processed in the queue.
|
kpeter@244
|
1566 |
int queueSize() const { return _list_back - _list_front; }
|
alpar@209
|
1567 |
|
alpar@100
|
1568 |
/// \brief Executes the algorithm.
|
alpar@100
|
1569 |
///
|
alpar@100
|
1570 |
/// Executes the algorithm.
|
alpar@100
|
1571 |
///
|
kpeter@244
|
1572 |
/// This method runs the %BFS algorithm from the root node(s)
|
kpeter@244
|
1573 |
/// in order to compute the shortest path to each node.
|
kpeter@244
|
1574 |
///
|
kpeter@244
|
1575 |
/// The algorithm computes
|
kpeter@244
|
1576 |
/// - the shortest path tree (forest),
|
kpeter@244
|
1577 |
/// - the distance of each node from the root(s).
|
kpeter@244
|
1578 |
///
|
kpeter@244
|
1579 |
/// \pre init() must be called and at least one root node should be added
|
alpar@100
|
1580 |
/// with addSource() before using this function.
|
kpeter@244
|
1581 |
///
|
kpeter@244
|
1582 |
/// \note <tt>b.start()</tt> is just a shortcut of the following code.
|
kpeter@244
|
1583 |
/// \code
|
kpeter@244
|
1584 |
/// while ( !b.emptyQueue() ) {
|
kpeter@244
|
1585 |
/// b.processNextNode();
|
kpeter@244
|
1586 |
/// }
|
kpeter@244
|
1587 |
/// \endcode
|
alpar@100
|
1588 |
void start() {
|
alpar@100
|
1589 |
while ( !emptyQueue() ) processNextNode();
|
alpar@100
|
1590 |
}
|
alpar@209
|
1591 |
|
kpeter@244
|
1592 |
/// \brief Executes the algorithm until the given target node is reached.
|
alpar@100
|
1593 |
///
|
kpeter@244
|
1594 |
/// Executes the algorithm until the given target node is reached.
|
alpar@100
|
1595 |
///
|
kpeter@244
|
1596 |
/// This method runs the %BFS algorithm from the root node(s)
|
kpeter@286
|
1597 |
/// in order to compute the shortest path to \c t.
|
kpeter@244
|
1598 |
///
|
kpeter@244
|
1599 |
/// The algorithm computes
|
kpeter@286
|
1600 |
/// - the shortest path to \c t,
|
kpeter@286
|
1601 |
/// - the distance of \c t from the root(s).
|
kpeter@244
|
1602 |
///
|
kpeter@244
|
1603 |
/// \pre init() must be called and at least one root node should be
|
kpeter@244
|
1604 |
/// added with addSource() before using this function.
|
kpeter@244
|
1605 |
///
|
kpeter@244
|
1606 |
/// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
|
kpeter@244
|
1607 |
/// \code
|
kpeter@244
|
1608 |
/// bool reach = false;
|
kpeter@244
|
1609 |
/// while ( !b.emptyQueue() && !reach ) {
|
kpeter@244
|
1610 |
/// b.processNextNode(t, reach);
|
kpeter@244
|
1611 |
/// }
|
kpeter@244
|
1612 |
/// \endcode
|
kpeter@286
|
1613 |
void start(Node t) {
|
alpar@100
|
1614 |
bool reach = false;
|
kpeter@286
|
1615 |
while ( !emptyQueue() && !reach ) processNextNode(t, reach);
|
alpar@100
|
1616 |
}
|
alpar@209
|
1617 |
|
alpar@100
|
1618 |
/// \brief Executes the algorithm until a condition is met.
|
alpar@100
|
1619 |
///
|
alpar@100
|
1620 |
/// Executes the algorithm until a condition is met.
|
alpar@100
|
1621 |
///
|
kpeter@244
|
1622 |
/// This method runs the %BFS algorithm from the root node(s) in
|
kpeter@244
|
1623 |
/// order to compute the shortest path to a node \c v with
|
kpeter@244
|
1624 |
/// <tt>nm[v]</tt> true, if such a node can be found.
|
alpar@100
|
1625 |
///
|
kpeter@244
|
1626 |
/// \param nm must be a bool (or convertible) node map. The
|
kpeter@244
|
1627 |
/// algorithm will stop when it reaches a node \c v with
|
alpar@100
|
1628 |
/// <tt>nm[v]</tt> true.
|
alpar@100
|
1629 |
///
|
kpeter@244
|
1630 |
/// \return The reached node \c v with <tt>nm[v]</tt> true or
|
kpeter@244
|
1631 |
/// \c INVALID if no such node was found.
|
kpeter@244
|
1632 |
///
|
kpeter@244
|
1633 |
/// \pre init() must be called and at least one root node should be
|
kpeter@244
|
1634 |
/// added with addSource() before using this function.
|
kpeter@244
|
1635 |
///
|
kpeter@244
|
1636 |
/// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
|
kpeter@244
|
1637 |
/// \code
|
kpeter@244
|
1638 |
/// Node rnode = INVALID;
|
kpeter@244
|
1639 |
/// while ( !b.emptyQueue() && rnode == INVALID ) {
|
kpeter@244
|
1640 |
/// b.processNextNode(nm, rnode);
|
kpeter@244
|
1641 |
/// }
|
kpeter@244
|
1642 |
/// return rnode;
|
kpeter@244
|
1643 |
/// \endcode
|
alpar@100
|
1644 |
template <typename NM>
|
alpar@100
|
1645 |
Node start(const NM &nm) {
|
alpar@100
|
1646 |
Node rnode = INVALID;
|
alpar@100
|
1647 |
while ( !emptyQueue() && rnode == INVALID ) {
|
alpar@209
|
1648 |
processNextNode(nm, rnode);
|
alpar@100
|
1649 |
}
|
alpar@100
|
1650 |
return rnode;
|
alpar@100
|
1651 |
}
|
alpar@100
|
1652 |
|
kpeter@286
|
1653 |
/// \brief Runs the algorithm from the given source node.
|
alpar@100
|
1654 |
///
|
kpeter@244
|
1655 |
/// This method runs the %BFS algorithm from node \c s
|
kpeter@244
|
1656 |
/// in order to compute the shortest path to each node.
|
kpeter@244
|
1657 |
///
|
kpeter@244
|
1658 |
/// The algorithm computes
|
kpeter@244
|
1659 |
/// - the shortest path tree,
|
kpeter@244
|
1660 |
/// - the distance of each node from the root.
|
kpeter@244
|
1661 |
///
|
kpeter@244
|
1662 |
/// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
|
alpar@100
|
1663 |
///\code
|
alpar@100
|
1664 |
/// b.init();
|
alpar@100
|
1665 |
/// b.addSource(s);
|
alpar@100
|
1666 |
/// b.start();
|
alpar@100
|
1667 |
///\endcode
|
alpar@100
|
1668 |
void run(Node s) {
|
alpar@100
|
1669 |
init();
|
alpar@100
|
1670 |
addSource(s);
|
alpar@100
|
1671 |
start();
|
alpar@100
|
1672 |
}
|
alpar@100
|
1673 |
|
kpeter@286
|
1674 |
/// \brief Finds the shortest path between \c s and \c t.
|
kpeter@286
|
1675 |
///
|
kpeter@286
|
1676 |
/// This method runs the %BFS algorithm from node \c s
|
kpeter@286
|
1677 |
/// in order to compute the shortest path to node \c t
|
kpeter@286
|
1678 |
/// (it stops searching when \c t is processed).
|
kpeter@286
|
1679 |
///
|
kpeter@286
|
1680 |
/// \return \c true if \c t is reachable form \c s.
|
kpeter@286
|
1681 |
///
|
kpeter@286
|
1682 |
/// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
|
kpeter@286
|
1683 |
/// shortcut of the following code.
|
kpeter@286
|
1684 |
///\code
|
kpeter@286
|
1685 |
/// b.init();
|
kpeter@286
|
1686 |
/// b.addSource(s);
|
kpeter@286
|
1687 |
/// b.start(t);
|
kpeter@286
|
1688 |
///\endcode
|
kpeter@286
|
1689 |
bool run(Node s,Node t) {
|
kpeter@286
|
1690 |
init();
|
kpeter@286
|
1691 |
addSource(s);
|
kpeter@286
|
1692 |
start(t);
|
kpeter@286
|
1693 |
return reached(t);
|
kpeter@286
|
1694 |
}
|
kpeter@286
|
1695 |
|
kpeter@244
|
1696 |
/// \brief Runs the algorithm to visit all nodes in the digraph.
|
alpar@209
|
1697 |
///
|
alpar@100
|
1698 |
/// This method runs the %BFS algorithm in order to
|
kpeter@244
|
1699 |
/// compute the shortest path to each node.
|
alpar@100
|
1700 |
///
|
kpeter@244
|
1701 |
/// The algorithm computes
|
kpeter@244
|
1702 |
/// - the shortest path tree (forest),
|
kpeter@244
|
1703 |
/// - the distance of each node from the root(s).
|
kpeter@244
|
1704 |
///
|
kpeter@244
|
1705 |
/// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
|
alpar@100
|
1706 |
///\code
|
alpar@100
|
1707 |
/// b.init();
|
kpeter@244
|
1708 |
/// for (NodeIt n(gr); n != INVALID; ++n) {
|
kpeter@244
|
1709 |
/// if (!b.reached(n)) {
|
kpeter@244
|
1710 |
/// b.addSource(n);
|
alpar@100
|
1711 |
/// b.start();
|
alpar@100
|
1712 |
/// }
|
alpar@100
|
1713 |
/// }
|
alpar@100
|
1714 |
///\endcode
|
alpar@100
|
1715 |
void run() {
|
alpar@100
|
1716 |
init();
|
alpar@100
|
1717 |
for (NodeIt it(*_digraph); it != INVALID; ++it) {
|
alpar@100
|
1718 |
if (!reached(it)) {
|
alpar@100
|
1719 |
addSource(it);
|
alpar@100
|
1720 |
start();
|
alpar@100
|
1721 |
}
|
alpar@100
|
1722 |
}
|
alpar@100
|
1723 |
}
|
kpeter@244
|
1724 |
|
alpar@100
|
1725 |
///@}
|
alpar@100
|
1726 |
|
alpar@100
|
1727 |
/// \name Query Functions
|
kpeter@405
|
1728 |
/// The results of the BFS algorithm can be obtained using these
|
alpar@100
|
1729 |
/// functions.\n
|
kpeter@405
|
1730 |
/// Either \ref run(Node) "run()" or \ref start() should be called
|
kpeter@405
|
1731 |
/// before using them.
|
kpeter@405
|
1732 |
|
alpar@100
|
1733 |
///@{
|
alpar@100
|
1734 |
|
kpeter@716
|
1735 |
/// \brief Checks if the given node is reached from the root(s).
|
alpar@100
|
1736 |
///
|
kpeter@405
|
1737 |
/// Returns \c true if \c v is reached from the root(s).
|
kpeter@405
|
1738 |
///
|
kpeter@405
|
1739 |
/// \pre Either \ref run(Node) "run()" or \ref init()
|
alpar@100
|
1740 |
/// must be called before using this function.
|
kpeter@420
|
1741 |
bool reached(Node v) const { return (*_reached)[v]; }
|
kpeter@244
|
1742 |
|
alpar@100
|
1743 |
///@}
|
kpeter@244
|
1744 |
|
alpar@100
|
1745 |
};
|
alpar@100
|
1746 |
|
alpar@100
|
1747 |
} //END OF NAMESPACE LEMON
|
alpar@100
|
1748 |
|
alpar@100
|
1749 |
#endif
|