1 /* -*- C++ -*- |
|
2 * src/lemon/dfs.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_DFS_H |
|
18 #define LEMON_DFS_H |
|
19 |
|
20 ///\ingroup flowalgs |
|
21 ///\file |
|
22 ///\brief Dfs algorithm. |
|
23 |
|
24 #include <lemon/list_graph.h> |
|
25 #include <lemon/graph_utils.h> |
|
26 #include <lemon/invalid.h> |
|
27 #include <lemon/error.h> |
|
28 #include <lemon/maps.h> |
|
29 |
|
30 namespace lemon { |
|
31 |
|
32 |
|
33 |
|
34 ///Default traits class of Dfs class. |
|
35 |
|
36 ///Default traits class of Dfs class. |
|
37 ///\param GR Graph type. |
|
38 template<class GR> |
|
39 struct DfsDefaultTraits |
|
40 { |
|
41 ///The graph type the algorithm runs on. |
|
42 typedef GR Graph; |
|
43 ///\brief The type of the map that stores the last |
|
44 ///edges of the %DFS paths. |
|
45 /// |
|
46 ///The type of the map that stores the last |
|
47 ///edges of the %DFS paths. |
|
48 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
49 /// |
|
50 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; |
|
51 ///Instantiates a PredMap. |
|
52 |
|
53 ///This function instantiates a \ref PredMap. |
|
54 ///\param G is the graph, to which we would like to define the PredMap. |
|
55 ///\todo The graph alone may be insufficient to initialize |
|
56 static PredMap *createPredMap(const GR &G) |
|
57 { |
|
58 return new PredMap(G); |
|
59 } |
|
60 // ///\brief The type of the map that stores the last but one |
|
61 // ///nodes of the %DFS paths. |
|
62 // /// |
|
63 // ///The type of the map that stores the last but one |
|
64 // ///nodes of the %DFS paths. |
|
65 // ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
66 // /// |
|
67 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap; |
|
68 // ///Instantiates a PredNodeMap. |
|
69 |
|
70 // ///This function instantiates a \ref PredNodeMap. |
|
71 // ///\param G is the graph, to which |
|
72 // ///we would like to define the \ref PredNodeMap |
|
73 // static PredNodeMap *createPredNodeMap(const GR &G) |
|
74 // { |
|
75 // return new PredNodeMap(); |
|
76 // } |
|
77 |
|
78 ///The type of the map that indicates which nodes are processed. |
|
79 |
|
80 ///The type of the map that indicates which nodes are processed. |
|
81 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
82 ///\todo named parameter to set this type, function to read and write. |
|
83 typedef NullMap<typename Graph::Node,bool> ProcessedMap; |
|
84 ///Instantiates a ProcessedMap. |
|
85 |
|
86 ///This function instantiates a \ref ProcessedMap. |
|
87 ///\param G is the graph, to which |
|
88 ///we would like to define the \ref ProcessedMap |
|
89 static ProcessedMap *createProcessedMap(const GR &) |
|
90 { |
|
91 return new ProcessedMap(); |
|
92 } |
|
93 ///The type of the map that indicates which nodes are reached. |
|
94 |
|
95 ///The type of the map that indicates which nodes are reached. |
|
96 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
97 ///\todo named parameter to set this type, function to read and write. |
|
98 typedef typename Graph::template NodeMap<bool> ReachedMap; |
|
99 ///Instantiates a ReachedMap. |
|
100 |
|
101 ///This function instantiates a \ref ReachedMap. |
|
102 ///\param G is the graph, to which |
|
103 ///we would like to define the \ref ReachedMap. |
|
104 static ReachedMap *createReachedMap(const GR &G) |
|
105 { |
|
106 return new ReachedMap(G); |
|
107 } |
|
108 ///The type of the map that stores the dists of the nodes. |
|
109 |
|
110 ///The type of the map that stores the dists of the nodes. |
|
111 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
112 /// |
|
113 typedef typename Graph::template NodeMap<int> DistMap; |
|
114 ///Instantiates a DistMap. |
|
115 |
|
116 ///This function instantiates a \ref DistMap. |
|
117 ///\param G is the graph, to which we would like to define the \ref DistMap |
|
118 static DistMap *createDistMap(const GR &G) |
|
119 { |
|
120 return new DistMap(G); |
|
121 } |
|
122 }; |
|
123 |
|
124 ///%DFS algorithm class. |
|
125 |
|
126 ///\ingroup flowalgs |
|
127 ///This class provides an efficient implementation of the %DFS algorithm. |
|
128 /// |
|
129 ///\param GR The graph type the algorithm runs on. The default value is |
|
130 ///\ref ListGraph. The value of GR is not used directly by Dfs, it |
|
131 ///is only passed to \ref DfsDefaultTraits. |
|
132 ///\param TR Traits class to set various data types used by the algorithm. |
|
133 ///The default traits class is |
|
134 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>". |
|
135 ///See \ref DfsDefaultTraits for the documentation of |
|
136 ///a Dfs traits class. |
|
137 /// |
|
138 ///\author Jacint Szabo and Alpar Juttner |
|
139 ///\todo A compare object would be nice. |
|
140 |
|
141 #ifdef DOXYGEN |
|
142 template <typename GR, |
|
143 typename TR> |
|
144 #else |
|
145 template <typename GR=ListGraph, |
|
146 typename TR=DfsDefaultTraits<GR> > |
|
147 #endif |
|
148 class Dfs { |
|
149 public: |
|
150 /** |
|
151 * \brief \ref Exception for uninitialized parameters. |
|
152 * |
|
153 * This error represents problems in the initialization |
|
154 * of the parameters of the algorithms. |
|
155 */ |
|
156 class UninitializedParameter : public lemon::UninitializedParameter { |
|
157 public: |
|
158 virtual const char* exceptionName() const { |
|
159 return "lemon::Dfs::UninitializedParameter"; |
|
160 } |
|
161 }; |
|
162 |
|
163 typedef TR Traits; |
|
164 ///The type of the underlying graph. |
|
165 typedef typename TR::Graph Graph; |
|
166 ///\e |
|
167 typedef typename Graph::Node Node; |
|
168 ///\e |
|
169 typedef typename Graph::NodeIt NodeIt; |
|
170 ///\e |
|
171 typedef typename Graph::Edge Edge; |
|
172 ///\e |
|
173 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
174 |
|
175 ///\brief The type of the map that stores the last |
|
176 ///edges of the %DFS paths. |
|
177 typedef typename TR::PredMap PredMap; |
|
178 // ///\brief The type of the map that stores the last but one |
|
179 // ///nodes of the %DFS paths. |
|
180 // typedef typename TR::PredNodeMap PredNodeMap; |
|
181 ///The type of the map indicating which nodes are reached. |
|
182 typedef typename TR::ReachedMap ReachedMap; |
|
183 ///The type of the map indicating which nodes are processed. |
|
184 typedef typename TR::ProcessedMap ProcessedMap; |
|
185 ///The type of the map that stores the dists of the nodes. |
|
186 typedef typename TR::DistMap DistMap; |
|
187 private: |
|
188 /// Pointer to the underlying graph. |
|
189 const Graph *G; |
|
190 ///Pointer to the map of predecessors edges. |
|
191 PredMap *_pred; |
|
192 ///Indicates if \ref _pred is locally allocated (\c true) or not. |
|
193 bool local_pred; |
|
194 // ///Pointer to the map of predecessors nodes. |
|
195 // PredNodeMap *_predNode; |
|
196 // ///Indicates if \ref _predNode is locally allocated (\c true) or not. |
|
197 // bool local_predNode; |
|
198 ///Pointer to the map of distances. |
|
199 DistMap *_dist; |
|
200 ///Indicates if \ref _dist is locally allocated (\c true) or not. |
|
201 bool local_dist; |
|
202 ///Pointer to the map of reached status of the nodes. |
|
203 ReachedMap *_reached; |
|
204 ///Indicates if \ref _reached is locally allocated (\c true) or not. |
|
205 bool local_reached; |
|
206 ///Pointer to the map of processed status of the nodes. |
|
207 ProcessedMap *_processed; |
|
208 ///Indicates if \ref _processed is locally allocated (\c true) or not. |
|
209 bool local_processed; |
|
210 |
|
211 std::vector<typename Graph::OutEdgeIt> _stack; |
|
212 int _stack_head; |
|
213 // ///The source node of the last execution. |
|
214 // Node source; |
|
215 |
|
216 ///Creates the maps if necessary. |
|
217 |
|
218 ///\todo Error if \c G are \c NULL. |
|
219 ///\todo Better memory allocation (instead of new). |
|
220 void create_maps() |
|
221 { |
|
222 if(!_pred) { |
|
223 local_pred = true; |
|
224 _pred = Traits::createPredMap(*G); |
|
225 } |
|
226 // if(!_predNode) { |
|
227 // local_predNode = true; |
|
228 // _predNode = Traits::createPredNodeMap(*G); |
|
229 // } |
|
230 if(!_dist) { |
|
231 local_dist = true; |
|
232 _dist = Traits::createDistMap(*G); |
|
233 } |
|
234 if(!_reached) { |
|
235 local_reached = true; |
|
236 _reached = Traits::createReachedMap(*G); |
|
237 } |
|
238 if(!_processed) { |
|
239 local_processed = true; |
|
240 _processed = Traits::createProcessedMap(*G); |
|
241 } |
|
242 } |
|
243 |
|
244 public : |
|
245 |
|
246 ///\name Named template parameters |
|
247 |
|
248 ///@{ |
|
249 |
|
250 template <class T> |
|
251 struct DefPredMapTraits : public Traits { |
|
252 typedef T PredMap; |
|
253 static PredMap *createPredMap(const Graph &G) |
|
254 { |
|
255 throw UninitializedParameter(); |
|
256 } |
|
257 }; |
|
258 ///\ref named-templ-param "Named parameter" for setting PredMap type |
|
259 |
|
260 ///\ref named-templ-param "Named parameter" for setting PredMap type |
|
261 /// |
|
262 template <class T> |
|
263 class DefPredMap : public Dfs< Graph, |
|
264 DefPredMapTraits<T> > { }; |
|
265 |
|
266 // template <class T> |
|
267 // struct DefPredNodeMapTraits : public Traits { |
|
268 // typedef T PredNodeMap; |
|
269 // static PredNodeMap *createPredNodeMap(const Graph &G) |
|
270 // { |
|
271 // throw UninitializedParameter(); |
|
272 // } |
|
273 // }; |
|
274 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type |
|
275 |
|
276 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type |
|
277 // /// |
|
278 // template <class T> |
|
279 // class DefPredNodeMap : public Dfs< Graph, |
|
280 // LengthMap, |
|
281 // DefPredNodeMapTraits<T> > { }; |
|
282 |
|
283 template <class T> |
|
284 struct DefDistMapTraits : public Traits { |
|
285 typedef T DistMap; |
|
286 static DistMap *createDistMap(const Graph &G) |
|
287 { |
|
288 throw UninitializedParameter(); |
|
289 } |
|
290 }; |
|
291 ///\ref named-templ-param "Named parameter" for setting DistMap type |
|
292 |
|
293 ///\ref named-templ-param "Named parameter" for setting DistMap type |
|
294 /// |
|
295 template <class T> |
|
296 class DefDistMap : public Dfs< Graph, |
|
297 DefDistMapTraits<T> > { }; |
|
298 |
|
299 template <class T> |
|
300 struct DefReachedMapTraits : public Traits { |
|
301 typedef T ReachedMap; |
|
302 static ReachedMap *createReachedMap(const Graph &G) |
|
303 { |
|
304 throw UninitializedParameter(); |
|
305 } |
|
306 }; |
|
307 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
|
308 |
|
309 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
|
310 /// |
|
311 template <class T> |
|
312 class DefReachedMap : public Dfs< Graph, |
|
313 DefReachedMapTraits<T> > { }; |
|
314 |
|
315 struct DefGraphReachedMapTraits : public Traits { |
|
316 typedef typename Graph::template NodeMap<bool> ReachedMap; |
|
317 static ReachedMap *createReachedMap(const Graph &G) |
|
318 { |
|
319 return new ReachedMap(G); |
|
320 } |
|
321 }; |
|
322 template <class T> |
|
323 struct DefProcessedMapTraits : public Traits { |
|
324 typedef T ProcessedMap; |
|
325 static ProcessedMap *createProcessedMap(const Graph &G) |
|
326 { |
|
327 throw UninitializedParameter(); |
|
328 } |
|
329 }; |
|
330 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
|
331 |
|
332 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
|
333 /// |
|
334 template <class T> |
|
335 class DefProcessedMap : public Dfs< Graph, |
|
336 DefProcessedMapTraits<T> > { }; |
|
337 |
|
338 struct DefGraphProcessedMapTraits : public Traits { |
|
339 typedef typename Graph::template NodeMap<bool> ProcessedMap; |
|
340 static ProcessedMap *createProcessedMap(const Graph &G) |
|
341 { |
|
342 return new ProcessedMap(G); |
|
343 } |
|
344 }; |
|
345 ///\brief \ref named-templ-param "Named parameter" |
|
346 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. |
|
347 /// |
|
348 ///\ref named-templ-param "Named parameter" |
|
349 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. |
|
350 ///If you don't set it explicitely, it will be automatically allocated. |
|
351 template <class T> |
|
352 class DefProcessedMapToBeDefaultMap : |
|
353 public Dfs< Graph, |
|
354 DefGraphProcessedMapTraits> { }; |
|
355 |
|
356 ///@} |
|
357 |
|
358 public: |
|
359 |
|
360 ///Constructor. |
|
361 |
|
362 ///\param _G the graph the algorithm will run on. |
|
363 /// |
|
364 Dfs(const Graph& _G) : |
|
365 G(&_G), |
|
366 _pred(NULL), local_pred(false), |
|
367 // _predNode(NULL), local_predNode(false), |
|
368 _dist(NULL), local_dist(false), |
|
369 _reached(NULL), local_reached(false), |
|
370 _processed(NULL), local_processed(false) |
|
371 { } |
|
372 |
|
373 ///Destructor. |
|
374 ~Dfs() |
|
375 { |
|
376 if(local_pred) delete _pred; |
|
377 // if(local_predNode) delete _predNode; |
|
378 if(local_dist) delete _dist; |
|
379 if(local_reached) delete _reached; |
|
380 if(local_processed) delete _processed; |
|
381 } |
|
382 |
|
383 ///Sets the map storing the predecessor edges. |
|
384 |
|
385 ///Sets the map storing the predecessor edges. |
|
386 ///If you don't use this function before calling \ref run(), |
|
387 ///it will allocate one. The destuctor deallocates this |
|
388 ///automatically allocated map, of course. |
|
389 ///\return <tt> (*this) </tt> |
|
390 Dfs &predMap(PredMap &m) |
|
391 { |
|
392 if(local_pred) { |
|
393 delete _pred; |
|
394 local_pred=false; |
|
395 } |
|
396 _pred = &m; |
|
397 return *this; |
|
398 } |
|
399 |
|
400 // ///Sets the map storing the predecessor nodes. |
|
401 |
|
402 // ///Sets the map storing the predecessor nodes. |
|
403 // ///If you don't use this function before calling \ref run(), |
|
404 // ///it will allocate one. The destuctor deallocates this |
|
405 // ///automatically allocated map, of course. |
|
406 // ///\return <tt> (*this) </tt> |
|
407 // Dfs &predNodeMap(PredNodeMap &m) |
|
408 // { |
|
409 // if(local_predNode) { |
|
410 // delete _predNode; |
|
411 // local_predNode=false; |
|
412 // } |
|
413 // _predNode = &m; |
|
414 // return *this; |
|
415 // } |
|
416 |
|
417 ///Sets the map storing the distances calculated by the algorithm. |
|
418 |
|
419 ///Sets the map storing the distances calculated by the algorithm. |
|
420 ///If you don't use this function before calling \ref run(), |
|
421 ///it will allocate one. The destuctor deallocates this |
|
422 ///automatically allocated map, of course. |
|
423 ///\return <tt> (*this) </tt> |
|
424 Dfs &distMap(DistMap &m) |
|
425 { |
|
426 if(local_dist) { |
|
427 delete _dist; |
|
428 local_dist=false; |
|
429 } |
|
430 _dist = &m; |
|
431 return *this; |
|
432 } |
|
433 |
|
434 ///Sets the map indicating if a node is reached. |
|
435 |
|
436 ///Sets the map indicating if a node is reached. |
|
437 ///If you don't use this function before calling \ref run(), |
|
438 ///it will allocate one. The destuctor deallocates this |
|
439 ///automatically allocated map, of course. |
|
440 ///\return <tt> (*this) </tt> |
|
441 Dfs &reachedMap(ReachedMap &m) |
|
442 { |
|
443 if(local_reached) { |
|
444 delete _reached; |
|
445 local_reached=false; |
|
446 } |
|
447 _reached = &m; |
|
448 return *this; |
|
449 } |
|
450 |
|
451 ///Sets the map indicating if a node is processed. |
|
452 |
|
453 ///Sets the map indicating if a node is processed. |
|
454 ///If you don't use this function before calling \ref run(), |
|
455 ///it will allocate one. The destuctor deallocates this |
|
456 ///automatically allocated map, of course. |
|
457 ///\return <tt> (*this) </tt> |
|
458 Dfs &processedMap(ProcessedMap &m) |
|
459 { |
|
460 if(local_processed) { |
|
461 delete _processed; |
|
462 local_processed=false; |
|
463 } |
|
464 _processed = &m; |
|
465 return *this; |
|
466 } |
|
467 |
|
468 public: |
|
469 ///\name Execution control |
|
470 ///The simplest way to execute the algorithm is to use |
|
471 ///one of the member functions called \c run(...). |
|
472 ///\n |
|
473 ///If you need more control on the execution, |
|
474 ///first you must call \ref init(), then you can add several source nodes |
|
475 ///with \ref addSource(). |
|
476 ///Finally \ref start() will perform the actual path |
|
477 ///computation. |
|
478 |
|
479 ///@{ |
|
480 |
|
481 ///Initializes the internal data structures. |
|
482 |
|
483 ///Initializes the internal data structures. |
|
484 /// |
|
485 void init() |
|
486 { |
|
487 create_maps(); |
|
488 _stack.resize(countNodes(*G)); |
|
489 _stack_head=-1; |
|
490 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
|
491 _pred->set(u,INVALID); |
|
492 // _predNode->set(u,INVALID); |
|
493 _reached->set(u,false); |
|
494 _processed->set(u,false); |
|
495 } |
|
496 } |
|
497 |
|
498 ///Adds a new source node. |
|
499 |
|
500 ///Adds a new source node to the set of nodes to be processed. |
|
501 /// |
|
502 ///\bug dist's are wrong (or at least strange) in case of multiple sources. |
|
503 void addSource(Node s) |
|
504 { |
|
505 if(!(*_reached)[s]) |
|
506 { |
|
507 _reached->set(s,true); |
|
508 _pred->set(s,INVALID); |
|
509 // _predNode->set(u,INVALID); |
|
510 _stack[++_stack_head]=OutEdgeIt(*G,s); |
|
511 _dist->set(s,_stack_head); |
|
512 } |
|
513 } |
|
514 |
|
515 ///Processes the next node. |
|
516 |
|
517 ///Processes the next node. |
|
518 /// |
|
519 ///\warning The stack must not be empty! |
|
520 void processNextEdge() |
|
521 { |
|
522 Node m; |
|
523 Edge e=_stack[_stack_head]; |
|
524 if(!(*_reached)[m=G->target(e)]) { |
|
525 _pred->set(m,e); |
|
526 _reached->set(m,true); |
|
527 // _pred_node->set(m,G->source(e)); |
|
528 ++_stack_head; |
|
529 _stack[_stack_head] = OutEdgeIt(*G, m); |
|
530 _dist->set(m,_stack_head); |
|
531 } |
|
532 else { |
|
533 Node n; |
|
534 while(_stack_head>=0 && |
|
535 (n=G->source(_stack[_stack_head]), |
|
536 ++_stack[_stack_head]==INVALID)) |
|
537 { |
|
538 _processed->set(n,true); |
|
539 --_stack_head; |
|
540 } |
|
541 } |
|
542 } |
|
543 |
|
544 ///\brief Returns \c false if there are nodes |
|
545 ///to be processed in the queue |
|
546 /// |
|
547 ///Returns \c false if there are nodes |
|
548 ///to be processed in the queue |
|
549 bool emptyQueue() { return _stack_head<0; } |
|
550 ///Returns the number of the nodes to be processed. |
|
551 |
|
552 ///Returns the number of the nodes to be processed in the queue. |
|
553 /// |
|
554 int queueSize() { return _stack_head+1; } |
|
555 |
|
556 ///Executes the algorithm. |
|
557 |
|
558 ///Executes the algorithm. |
|
559 /// |
|
560 ///\pre init() must be called and at least one node should be added |
|
561 ///with addSource() before using this function. |
|
562 /// |
|
563 ///This method runs the %DFS algorithm from the root node(s) |
|
564 ///in order to |
|
565 ///compute the |
|
566 ///%DFS path to each node. The algorithm computes |
|
567 ///- The %DFS tree. |
|
568 ///- The distance of each node from the root(s). |
|
569 /// |
|
570 void start() |
|
571 { |
|
572 while ( !emptyQueue() ) processNextEdge(); |
|
573 } |
|
574 |
|
575 ///Executes the algorithm until \c dest is reached. |
|
576 |
|
577 ///Executes the algorithm until \c dest is reached. |
|
578 /// |
|
579 ///\pre init() must be called and at least one node should be added |
|
580 ///with addSource() before using this function. |
|
581 /// |
|
582 ///This method runs the %DFS algorithm from the root node(s) |
|
583 ///in order to |
|
584 ///compute the |
|
585 ///%DFS path to \c dest. The algorithm computes |
|
586 ///- The %DFS path to \c dest. |
|
587 ///- The distance of \c dest from the root(s). |
|
588 /// |
|
589 void start(Node dest) |
|
590 { |
|
591 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) |
|
592 processNextEdge(); |
|
593 } |
|
594 |
|
595 ///Executes the algorithm until a condition is met. |
|
596 |
|
597 ///Executes the algorithm until a condition is met. |
|
598 /// |
|
599 ///\pre init() must be called and at least one node should be added |
|
600 ///with addSource() before using this function. |
|
601 /// |
|
602 ///\param nm must be a bool (or convertible) edge map. The algorithm |
|
603 ///will stop when it reaches a edge \c v with <tt>nm[v]==true</tt>. |
|
604 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c mn is an edge map, |
|
605 ///not a node map. |
|
606 template<class NM> |
|
607 void start(const NM &nm) |
|
608 { |
|
609 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge(); |
|
610 } |
|
611 |
|
612 ///Runs %DFS algorithm from node \c s. |
|
613 |
|
614 ///This method runs the %DFS algorithm from a root node \c s |
|
615 ///in order to |
|
616 ///compute the |
|
617 ///%DFS path to each node. The algorithm computes |
|
618 ///- The %DFS tree. |
|
619 ///- The distance of each node from the root. |
|
620 /// |
|
621 ///\note d.run(s) is just a shortcut of the following code. |
|
622 ///\code |
|
623 /// d.init(); |
|
624 /// d.addSource(s); |
|
625 /// d.start(); |
|
626 ///\endcode |
|
627 void run(Node s) { |
|
628 init(); |
|
629 addSource(s); |
|
630 start(); |
|
631 } |
|
632 |
|
633 ///Finds the %DFS path between \c s and \c t. |
|
634 |
|
635 ///Finds the %DFS path between \c s and \c t. |
|
636 /// |
|
637 ///\return The length of the %DFS s---t path if there exists one, |
|
638 ///0 otherwise. |
|
639 ///\note Apart from the return value, d.run(s) is |
|
640 ///just a shortcut of the following code. |
|
641 ///\code |
|
642 /// d.init(); |
|
643 /// d.addSource(s); |
|
644 /// d.start(t); |
|
645 ///\endcode |
|
646 int run(Node s,Node t) { |
|
647 init(); |
|
648 addSource(s); |
|
649 start(t); |
|
650 return reached(t)?_stack_head+1:0; |
|
651 } |
|
652 |
|
653 ///@} |
|
654 |
|
655 ///\name Query Functions |
|
656 ///The result of the %DFS algorithm can be obtained using these |
|
657 ///functions.\n |
|
658 ///Before the use of these functions, |
|
659 ///either run() or start() must be called. |
|
660 |
|
661 ///@{ |
|
662 |
|
663 ///Copies the path to \c t on the DFS tree into \c p |
|
664 |
|
665 ///This function copies the path on the DFS tree to \c t into \c p. |
|
666 ///If it \c \t is a source itself or unreachable, then it does not |
|
667 ///alter \c p. |
|
668 ///\todo Is it the right way to handle unreachable nodes? |
|
669 ///\return Returns \c true if a path to \c t was actually copied to \c p, |
|
670 ///\c false otherwise. |
|
671 ///\sa DirPath |
|
672 template<class P> |
|
673 bool getPath(P &p,Node t) |
|
674 { |
|
675 if(reached(t)) { |
|
676 p.clear(); |
|
677 typename P::Builder b(p); |
|
678 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) |
|
679 b.pushFront(pred(t)); |
|
680 b.commit(); |
|
681 return true; |
|
682 } |
|
683 return false; |
|
684 } |
|
685 |
|
686 ///The distance of a node from the root(s). |
|
687 |
|
688 ///Returns the distance of a node from the root(s). |
|
689 ///\pre \ref run() must be called before using this function. |
|
690 ///\warning If node \c v in unreachable from the root(s) the return value |
|
691 ///of this funcion is undefined. |
|
692 int dist(Node v) const { return (*_dist)[v]; } |
|
693 |
|
694 ///Returns the 'previous edge' of the %DFS tree. |
|
695 |
|
696 ///For a node \c v it returns the 'previous edge' |
|
697 ///of the %DFS path, |
|
698 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c |
|
699 ///v. It is \ref INVALID |
|
700 ///if \c v is unreachable from the root(s) or \c v is a root. The |
|
701 ///%DFS tree used here is equal to the %DFS tree used in |
|
702 ///\ref predNode(Node v). |
|
703 ///\pre Either \ref run() or \ref start() must be called before using |
|
704 ///this function. |
|
705 ///\todo predEdge could be a better name. |
|
706 Edge pred(Node v) const { return (*_pred)[v];} |
|
707 |
|
708 ///Returns the 'previous node' of the %DFS tree. |
|
709 |
|
710 ///For a node \c v it returns the 'previous node' |
|
711 ///of the %DFS tree, |
|
712 ///i.e. it returns the last but one node from a %DFS path from the |
|
713 ///root(a) to \c /v. |
|
714 ///It is INVALID if \c v is unreachable from the root(s) or |
|
715 ///if \c v itself a root. |
|
716 ///The %DFS tree used here is equal to the %DFS |
|
717 ///tree used in \ref pred(Node v). |
|
718 ///\pre Either \ref run() or \ref start() must be called before |
|
719 ///using this function. |
|
720 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
|
721 G->source((*_pred)[v]); } |
|
722 |
|
723 ///Returns a reference to the NodeMap of distances. |
|
724 |
|
725 ///Returns a reference to the NodeMap of distances. |
|
726 ///\pre Either \ref run() or \ref init() must |
|
727 ///be called before using this function. |
|
728 const DistMap &distMap() const { return *_dist;} |
|
729 |
|
730 ///Returns a reference to the %DFS edge-tree map. |
|
731 |
|
732 ///Returns a reference to the NodeMap of the edges of the |
|
733 ///%DFS tree. |
|
734 ///\pre Either \ref run() or \ref init() |
|
735 ///must be called before using this function. |
|
736 const PredMap &predMap() const { return *_pred;} |
|
737 |
|
738 // ///Returns a reference to the map of nodes of %DFS paths. |
|
739 |
|
740 // ///Returns a reference to the NodeMap of the last but one nodes of the |
|
741 // ///%DFS tree. |
|
742 // ///\pre \ref run() must be called before using this function. |
|
743 // const PredNodeMap &predNodeMap() const { return *_predNode;} |
|
744 |
|
745 ///Checks if a node is reachable from the root. |
|
746 |
|
747 ///Returns \c true if \c v is reachable from the root. |
|
748 ///\warning The source nodes are inditated as unreached. |
|
749 ///\pre Either \ref run() or \ref start() |
|
750 ///must be called before using this function. |
|
751 /// |
|
752 bool reached(Node v) { return (*_reached)[v]; } |
|
753 |
|
754 ///@} |
|
755 }; |
|
756 |
|
757 ///Default traits class of Dfs function. |
|
758 |
|
759 ///Default traits class of Dfs function. |
|
760 ///\param GR Graph type. |
|
761 template<class GR> |
|
762 struct DfsWizardDefaultTraits |
|
763 { |
|
764 ///The graph type the algorithm runs on. |
|
765 typedef GR Graph; |
|
766 ///\brief The type of the map that stores the last |
|
767 ///edges of the %DFS paths. |
|
768 /// |
|
769 ///The type of the map that stores the last |
|
770 ///edges of the %DFS paths. |
|
771 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
772 /// |
|
773 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap; |
|
774 ///Instantiates a PredMap. |
|
775 |
|
776 ///This function instantiates a \ref PredMap. |
|
777 ///\param G is the graph, to which we would like to define the PredMap. |
|
778 ///\todo The graph alone may be insufficient to initialize |
|
779 static PredMap *createPredMap(const GR &) |
|
780 { |
|
781 return new PredMap(); |
|
782 } |
|
783 // ///\brief The type of the map that stores the last but one |
|
784 // ///nodes of the %DFS paths. |
|
785 // /// |
|
786 // ///The type of the map that stores the last but one |
|
787 // ///nodes of the %DFS paths. |
|
788 // ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
789 // /// |
|
790 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap; |
|
791 // ///Instantiates a PredNodeMap. |
|
792 |
|
793 // ///This function instantiates a \ref PredNodeMap. |
|
794 // ///\param G is the graph, to which |
|
795 // ///we would like to define the \ref PredNodeMap |
|
796 // static PredNodeMap *createPredNodeMap(const GR &G) |
|
797 // { |
|
798 // return new PredNodeMap(); |
|
799 // } |
|
800 |
|
801 ///The type of the map that indicates which nodes are processed. |
|
802 |
|
803 ///The type of the map that indicates which nodes are processed. |
|
804 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
805 ///\todo named parameter to set this type, function to read and write. |
|
806 typedef NullMap<typename Graph::Node,bool> ProcessedMap; |
|
807 ///Instantiates a ProcessedMap. |
|
808 |
|
809 ///This function instantiates a \ref ProcessedMap. |
|
810 ///\param G is the graph, to which |
|
811 ///we would like to define the \ref ProcessedMap |
|
812 static ProcessedMap *createProcessedMap(const GR &) |
|
813 { |
|
814 return new ProcessedMap(); |
|
815 } |
|
816 ///The type of the map that indicates which nodes are reached. |
|
817 |
|
818 ///The type of the map that indicates which nodes are reached. |
|
819 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
820 ///\todo named parameter to set this type, function to read and write. |
|
821 typedef typename Graph::template NodeMap<bool> ReachedMap; |
|
822 ///Instantiates a ReachedMap. |
|
823 |
|
824 ///This function instantiates a \ref ReachedMap. |
|
825 ///\param G is the graph, to which |
|
826 ///we would like to define the \ref ReachedMap. |
|
827 static ReachedMap *createReachedMap(const GR &G) |
|
828 { |
|
829 return new ReachedMap(G); |
|
830 } |
|
831 ///The type of the map that stores the dists of the nodes. |
|
832 |
|
833 ///The type of the map that stores the dists of the nodes. |
|
834 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
|
835 /// |
|
836 typedef NullMap<typename Graph::Node,int> DistMap; |
|
837 ///Instantiates a DistMap. |
|
838 |
|
839 ///This function instantiates a \ref DistMap. |
|
840 ///\param G is the graph, to which we would like to define the \ref DistMap |
|
841 static DistMap *createDistMap(const GR &) |
|
842 { |
|
843 return new DistMap(); |
|
844 } |
|
845 }; |
|
846 |
|
847 /// Default traits used by \ref DfsWizard |
|
848 |
|
849 /// To make it easier to use Dfs algorithm |
|
850 ///we have created a wizard class. |
|
851 /// This \ref DfsWizard class needs default traits, |
|
852 ///as well as the \ref Dfs class. |
|
853 /// The \ref DfsWizardBase is a class to be the default traits of the |
|
854 /// \ref DfsWizard class. |
|
855 template<class GR> |
|
856 class DfsWizardBase : public DfsWizardDefaultTraits<GR> |
|
857 { |
|
858 |
|
859 typedef DfsWizardDefaultTraits<GR> Base; |
|
860 protected: |
|
861 /// Type of the nodes in the graph. |
|
862 typedef typename Base::Graph::Node Node; |
|
863 |
|
864 /// Pointer to the underlying graph. |
|
865 void *_g; |
|
866 ///Pointer to the map of reached nodes. |
|
867 void *_reached; |
|
868 ///Pointer to the map of processed nodes. |
|
869 void *_processed; |
|
870 ///Pointer to the map of predecessors edges. |
|
871 void *_pred; |
|
872 // ///Pointer to the map of predecessors nodes. |
|
873 // void *_predNode; |
|
874 ///Pointer to the map of distances. |
|
875 void *_dist; |
|
876 ///Pointer to the source node. |
|
877 Node _source; |
|
878 |
|
879 public: |
|
880 /// Constructor. |
|
881 |
|
882 /// This constructor does not require parameters, therefore it initiates |
|
883 /// all of the attributes to default values (0, INVALID). |
|
884 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
|
885 // _predNode(0), |
|
886 _dist(0), _source(INVALID) {} |
|
887 |
|
888 /// Constructor. |
|
889 |
|
890 /// This constructor requires some parameters, |
|
891 /// listed in the parameters list. |
|
892 /// Others are initiated to 0. |
|
893 /// \param g is the initial value of \ref _g |
|
894 /// \param s is the initial value of \ref _source |
|
895 DfsWizardBase(const GR &g, Node s=INVALID) : |
|
896 _g((void *)&g), _reached(0), _processed(0), _pred(0), |
|
897 // _predNode(0), |
|
898 _dist(0), _source(s) {} |
|
899 |
|
900 }; |
|
901 |
|
902 /// A class to make the usage of Dfs algorithm easier |
|
903 |
|
904 /// This class is created to make it easier to use Dfs algorithm. |
|
905 /// It uses the functions and features of the plain \ref Dfs, |
|
906 /// but it is much simpler to use it. |
|
907 /// |
|
908 /// Simplicity means that the way to change the types defined |
|
909 /// in the traits class is based on functions that returns the new class |
|
910 /// and not on templatable built-in classes. |
|
911 /// When using the plain \ref Dfs |
|
912 /// the new class with the modified type comes from |
|
913 /// the original class by using the :: |
|
914 /// operator. In the case of \ref DfsWizard only |
|
915 /// a function have to be called and it will |
|
916 /// return the needed class. |
|
917 /// |
|
918 /// It does not have own \ref run method. When its \ref run method is called |
|
919 /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run |
|
920 /// method of it. |
|
921 template<class TR> |
|
922 class DfsWizard : public TR |
|
923 { |
|
924 typedef TR Base; |
|
925 |
|
926 ///The type of the underlying graph. |
|
927 typedef typename TR::Graph Graph; |
|
928 //\e |
|
929 typedef typename Graph::Node Node; |
|
930 //\e |
|
931 typedef typename Graph::NodeIt NodeIt; |
|
932 //\e |
|
933 typedef typename Graph::Edge Edge; |
|
934 //\e |
|
935 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
936 |
|
937 ///\brief The type of the map that stores |
|
938 ///the reached nodes |
|
939 typedef typename TR::ReachedMap ReachedMap; |
|
940 ///\brief The type of the map that stores |
|
941 ///the processed nodes |
|
942 typedef typename TR::ProcessedMap ProcessedMap; |
|
943 ///\brief The type of the map that stores the last |
|
944 ///edges of the %DFS paths. |
|
945 typedef typename TR::PredMap PredMap; |
|
946 // ///\brief The type of the map that stores the last but one |
|
947 // ///nodes of the %DFS paths. |
|
948 // typedef typename TR::PredNodeMap PredNodeMap; |
|
949 ///The type of the map that stores the dists of the nodes. |
|
950 typedef typename TR::DistMap DistMap; |
|
951 |
|
952 public: |
|
953 /// Constructor. |
|
954 DfsWizard() : TR() {} |
|
955 |
|
956 /// Constructor that requires parameters. |
|
957 |
|
958 /// Constructor that requires parameters. |
|
959 /// These parameters will be the default values for the traits class. |
|
960 DfsWizard(const Graph &g, Node s=INVALID) : |
|
961 TR(g,s) {} |
|
962 |
|
963 ///Copy constructor |
|
964 DfsWizard(const TR &b) : TR(b) {} |
|
965 |
|
966 ~DfsWizard() {} |
|
967 |
|
968 ///Runs Dfs algorithm from a given node. |
|
969 |
|
970 ///Runs Dfs algorithm from a given node. |
|
971 ///The node can be given by the \ref source function. |
|
972 void run() |
|
973 { |
|
974 if(Base::_source==INVALID) throw UninitializedParameter(); |
|
975 Dfs<Graph,TR> alg(*(Graph*)Base::_g); |
|
976 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached); |
|
977 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); |
|
978 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); |
|
979 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode); |
|
980 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); |
|
981 alg.run(Base::_source); |
|
982 } |
|
983 |
|
984 ///Runs Dfs algorithm from the given node. |
|
985 |
|
986 ///Runs Dfs algorithm from the given node. |
|
987 ///\param s is the given source. |
|
988 void run(Node s) |
|
989 { |
|
990 Base::_source=s; |
|
991 run(); |
|
992 } |
|
993 |
|
994 template<class T> |
|
995 struct DefPredMapBase : public Base { |
|
996 typedef T PredMap; |
|
997 static PredMap *createPredMap(const Graph &) { return 0; }; |
|
998 DefPredMapBase(const TR &b) : TR(b) {} |
|
999 }; |
|
1000 |
|
1001 ///\brief \ref named-templ-param "Named parameter" |
|
1002 ///function for setting PredMap type |
|
1003 /// |
|
1004 /// \ref named-templ-param "Named parameter" |
|
1005 ///function for setting PredMap type |
|
1006 /// |
|
1007 template<class T> |
|
1008 DfsWizard<DefPredMapBase<T> > predMap(const T &t) |
|
1009 { |
|
1010 Base::_pred=(void *)&t; |
|
1011 return DfsWizard<DefPredMapBase<T> >(*this); |
|
1012 } |
|
1013 |
|
1014 |
|
1015 template<class T> |
|
1016 struct DefReachedMapBase : public Base { |
|
1017 typedef T ReachedMap; |
|
1018 static ReachedMap *createReachedMap(const Graph &) { return 0; }; |
|
1019 DefReachedMapBase(const TR &b) : TR(b) {} |
|
1020 }; |
|
1021 |
|
1022 ///\brief \ref named-templ-param "Named parameter" |
|
1023 ///function for setting ReachedMap |
|
1024 /// |
|
1025 /// \ref named-templ-param "Named parameter" |
|
1026 ///function for setting ReachedMap |
|
1027 /// |
|
1028 template<class T> |
|
1029 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
|
1030 { |
|
1031 Base::_pred=(void *)&t; |
|
1032 return DfsWizard<DefReachedMapBase<T> >(*this); |
|
1033 } |
|
1034 |
|
1035 |
|
1036 template<class T> |
|
1037 struct DefProcessedMapBase : public Base { |
|
1038 typedef T ProcessedMap; |
|
1039 static ProcessedMap *createProcessedMap(const Graph &) { return 0; }; |
|
1040 DefProcessedMapBase(const TR &b) : TR(b) {} |
|
1041 }; |
|
1042 |
|
1043 ///\brief \ref named-templ-param "Named parameter" |
|
1044 ///function for setting ProcessedMap |
|
1045 /// |
|
1046 /// \ref named-templ-param "Named parameter" |
|
1047 ///function for setting ProcessedMap |
|
1048 /// |
|
1049 template<class T> |
|
1050 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
|
1051 { |
|
1052 Base::_pred=(void *)&t; |
|
1053 return DfsWizard<DefProcessedMapBase<T> >(*this); |
|
1054 } |
|
1055 |
|
1056 |
|
1057 // template<class T> |
|
1058 // struct DefPredNodeMapBase : public Base { |
|
1059 // typedef T PredNodeMap; |
|
1060 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; |
|
1061 // DefPredNodeMapBase(const TR &b) : TR(b) {} |
|
1062 // }; |
|
1063 |
|
1064 // ///\brief \ref named-templ-param "Named parameter" |
|
1065 // ///function for setting PredNodeMap type |
|
1066 // /// |
|
1067 // /// \ref named-templ-param "Named parameter" |
|
1068 // ///function for setting PredNodeMap type |
|
1069 // /// |
|
1070 // template<class T> |
|
1071 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) |
|
1072 // { |
|
1073 // Base::_predNode=(void *)&t; |
|
1074 // return DfsWizard<DefPredNodeMapBase<T> >(*this); |
|
1075 // } |
|
1076 |
|
1077 template<class T> |
|
1078 struct DefDistMapBase : public Base { |
|
1079 typedef T DistMap; |
|
1080 static DistMap *createDistMap(const Graph &) { return 0; }; |
|
1081 DefDistMapBase(const TR &b) : TR(b) {} |
|
1082 }; |
|
1083 |
|
1084 ///\brief \ref named-templ-param "Named parameter" |
|
1085 ///function for setting DistMap type |
|
1086 /// |
|
1087 /// \ref named-templ-param "Named parameter" |
|
1088 ///function for setting DistMap type |
|
1089 /// |
|
1090 template<class T> |
|
1091 DfsWizard<DefDistMapBase<T> > distMap(const T &t) |
|
1092 { |
|
1093 Base::_dist=(void *)&t; |
|
1094 return DfsWizard<DefDistMapBase<T> >(*this); |
|
1095 } |
|
1096 |
|
1097 /// Sets the source node, from which the Dfs algorithm runs. |
|
1098 |
|
1099 /// Sets the source node, from which the Dfs algorithm runs. |
|
1100 /// \param s is the source node. |
|
1101 DfsWizard<TR> &source(Node s) |
|
1102 { |
|
1103 Base::_source=s; |
|
1104 return *this; |
|
1105 } |
|
1106 |
|
1107 }; |
|
1108 |
|
1109 ///Function type interface for Dfs algorithm. |
|
1110 |
|
1111 /// \ingroup flowalgs |
|
1112 ///Function type interface for Dfs algorithm. |
|
1113 /// |
|
1114 ///This function also has several |
|
1115 ///\ref named-templ-func-param "named parameters", |
|
1116 ///they are declared as the members of class \ref DfsWizard. |
|
1117 ///The following |
|
1118 ///example shows how to use these parameters. |
|
1119 ///\code |
|
1120 /// dfs(g,source).predMap(preds).run(); |
|
1121 ///\endcode |
|
1122 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" |
|
1123 ///to the end of the parameter list. |
|
1124 ///\sa DfsWizard |
|
1125 ///\sa Dfs |
|
1126 template<class GR> |
|
1127 DfsWizard<DfsWizardBase<GR> > |
|
1128 dfs(const GR &g,typename GR::Node s=INVALID) |
|
1129 { |
|
1130 return DfsWizard<DfsWizardBase<GR> >(g,s); |
|
1131 } |
|
1132 |
|
1133 } //END OF NAMESPACE LEMON |
|
1134 |
|
1135 #endif |
|
1136 |
|