Changeset 1218:5331168bbb18 in lemon0.x for src/lemon/dfs.h
 Timestamp:
 03/16/05 08:56:25 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1638
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/dfs.h
r1164 r1218 20 20 ///\ingroup flowalgs 21 21 ///\file 22 ///\brief %DFS algorithm. 23 /// 24 ///\todo Revise Manual. 25 22 ///\brief Dfs algorithm. 23 24 #include <lemon/list_graph.h> 26 25 #include <lemon/graph_utils.h> 27 26 #include <lemon/invalid.h> 27 #include <lemon/error.h> 28 #include <lemon/maps.h> 28 29 29 30 namespace lemon { 30 31 31 /// \addtogroup flowalgs 32 /// @{ 33 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 &G) 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 34 124 ///%DFS algorithm class. 35 36 ///This class provides an efficient implementation of %DFS algorithm. 125 126 ///\ingroup flowalgs 127 ///This class provides an efficient implementation of the %DFS algorithm. 37 128 /// 38 ///\param GR The graph type the algorithm runs on. 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. 39 137 /// 40 ///\author Alpar Juttner 138 ///\author Jacint Szabo and Alpar Juttner 139 ///\todo A compare object would be nice. 41 140 42 141 #ifdef DOXYGEN 43 template <typename GR> 142 template <typename GR, 143 typename TR> 44 144 #else 45 template <typename GR> 145 template <typename GR=ListGraph, 146 typename TR=DfsDefaultTraits<GR> > 46 147 #endif 47 class Dfs {148 class Dfs { 48 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; 49 164 ///The type of the underlying graph. 50 typedef GRGraph;165 typedef typename TR::Graph Graph; 51 166 ///\e 52 167 typedef typename Graph::Node Node; … … 59 174 60 175 ///\brief The type of the map that stores the last 61 ///edges of the paths on the %DFS tree. 62 typedef typename Graph::template NodeMap<Edge> PredMap; 63 ///\brief The type of the map that stores the last but one 64 ///nodes of the paths on the %DFS tree. 65 typedef typename Graph::template NodeMap<Node> PredNodeMap; 66 ///The type of the map that stores the dists of the nodes on the %DFS tree. 67 typedef typename Graph::template NodeMap<int> DistMap; 68 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; 69 187 private: 70 188 /// Pointer to the underlying graph. 71 189 const Graph *G; 72 190 ///Pointer to the map of predecessors edges. 73 PredMap * predecessor;74 ///Indicates if \ref predecessoris locally allocated (\c true) or not.75 bool local_pred ecessor;76 ///Pointer to the map of predecessors nodes.77 PredNodeMap *pred_node;78 ///Indicates if \ref pred_node is locally allocated (\c true) or not.79 bool local_pred_node;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; 80 198 ///Pointer to the map of distances. 81 DistMap *distance; 82 ///Indicates if \ref distance is locally allocated (\c true) or not. 83 bool local_distance; 84 85 ///The source node of the last execution. 86 Node source; 87 88 89 ///Initializes the maps. 90 void init_maps() 91 { 92 if(!predecessor) { 93 local_predecessor = true; 94 predecessor = new PredMap(*G); 95 } 96 if(!pred_node) { 97 local_pred_node = true; 98 pred_node = new PredNodeMap(*G); 99 } 100 if(!distance) { 101 local_distance = true; 102 distance = new DistMap(*G); 103 } 104 } 105 106 public : 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 namedtemplparam "Named parameter" for setting PredMap type 259 260 ///\ref namedtemplparam "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 namedtemplparam "Named parameter" for setting PredNodeMap type 275 276 // ///\ref namedtemplparam "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 namedtemplparam "Named parameter" for setting DistMap type 292 293 ///\ref namedtemplparam "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 namedtemplparam "Named parameter" for setting ReachedMap type 308 309 ///\ref namedtemplparam "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 namedtemplparam "Named parameter" for setting ProcessedMap type 331 332 ///\ref namedtemplparam "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 namedtemplparam "Named parameter" 346 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>. 347 /// 348 ///\ref namedtemplparam "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 107 360 ///Constructor. 108 361 … … 111 364 Dfs(const Graph& _G) : 112 365 G(&_G), 113 predecessor(NULL), local_predecessor(false), 114 pred_node(NULL), local_pred_node(false), 115 distance(NULL), local_distance(false) 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) 116 371 { } 117 372 … … 119 374 ~Dfs() 120 375 { 121 if(local_predecessor) delete predecessor; 122 if(local_pred_node) delete pred_node; 123 if(local_distance) delete distance; 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; 124 381 } 125 382 … … 131 388 ///automatically allocated map, of course. 132 389 ///\return <tt> (*this) </tt> 133 Dfs & setPredMap(PredMap &m)134 { 135 if(local_pred ecessor) {136 delete predecessor;137 local_pred ecessor=false;138 } 139 predecessor= &m;390 Dfs &predMap(PredMap &m) 391 { 392 if(local_pred) { 393 delete _pred; 394 local_pred=false; 395 } 396 _pred = &m; 140 397 return *this; 141 398 } 142 399 143 ///Sets the map storing the predecessor nodes.144 145 ///Sets the map storing the predecessor nodes.146 ///If you don't use this function before calling \ref run(),147 ///it will allocate one. The destuctor deallocates this148 ///automatically allocated map, of course.149 ///\return <tt> (*this) </tt>150 Dfs &setPredNodeMap(PredNodeMap &m)151 {152 if(local_pred_node) {153 delete pred_node;154 local_pred_node=false;155 }156 pred_node = &m;157 return *this;158 }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 // } 159 416 160 417 ///Sets the map storing the distances calculated by the algorithm. … … 165 422 ///automatically allocated map, of course. 166 423 ///\return <tt> (*this) </tt> 167 Dfs & setDistMap(DistMap &m)168 { 169 if(local_dist ance) {170 delete distance;171 local_dist ance=false;172 } 173 distance= &m;424 Dfs &distMap(DistMap &m) 425 { 426 if(local_dist) { 427 delete _dist; 428 local_dist=false; 429 } 430 _dist = &m; 174 431 return *this; 175 432 } 176 177 ///Runs %DFS algorithm from node \c s. 178 179 ///This method runs the %DFS algorithm from a root node \c s 180 ///in order to 181 ///compute 182 /// a %DFS tree and 183 /// the distance of each node from the root on this tree. 184 433 434 public: 435 ///\name Execution control 436 ///The simplest way to execute the algorithm is to use 437 ///one of the member functions called \c run(...). 438 ///\n 439 ///If you need more control on the execution, 440 ///first you must call \ref init(), then you can add several source nodes 441 ///with \ref addSource(). 442 ///Finally \ref start() will perform the actual path 443 ///computation. 444 445 ///@{ 446 447 ///Initializes the internal data structures. 448 449 ///Initializes the internal data structures. 450 /// 451 void init() 452 { 453 create_maps(); 454 _stack.resize(countNodes(*G)); 455 _stack_head=1; 456 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 457 _pred>set(u,INVALID); 458 // _predNode>set(u,INVALID); 459 _reached>set(u,false); 460 _processed>set(u,false); 461 } 462 } 463 464 ///Adds a new source node. 465 466 ///Adds a new source node to the set of nodes to be processed. 467 /// 468 ///\bug dist's are wrong (or at least strange) in case of multiple sources. 469 void addSource(Node s) 470 { 471 if(!(*_reached)[s]) 472 { 473 _reached>set(s,true); 474 _pred>set(s,INVALID); 475 // _predNode>set(u,INVALID); 476 _stack[++_stack_head]=OutEdgeIt(*G,s); 477 _dist>set(s,_stack_head); 478 } 479 } 480 481 ///Processes the next node. 482 483 ///Processes the next node. 484 /// 485 ///\warning The stack must not be empty! 486 void processNextEdge() 487 { 488 Node m; 489 Edge e=_stack[_stack_head]; 490 if(!(*_reached)[m=G>target(e)]) { 491 _pred>set(m,e); 492 _reached>set(m,true); 493 // _pred_node>set(m,G>source(e)); 494 _stack[++_stack_head] = OutEdgeIt(*G, m); 495 _dist>set(m,_stack_head); 496 } 497 else { 498 Node n; 499 while(_stack_head>=0 && 500 (n=G>source(_stack[_stack_head]), 501 ++_stack[_stack_head]==INVALID)) 502 { 503 _processed>set(n,true); 504 _stack_head; 505 } 506 } 507 } 508 509 ///\brief Returns \c false if there are nodes 510 ///to be processed in the queue 511 /// 512 ///Returns \c false if there are nodes 513 ///to be processed in the queue 514 bool emptyQueue() { return _stack_head<0; } 515 ///Returns the number of the nodes to be processed. 516 517 ///Returns the number of the nodes to be processed in the queue. 518 /// 519 int queueSize() { return _stack_head+1; } 520 521 ///Executes the algorithm. 522 523 ///Executes the algorithm. 524 /// 525 ///\pre init() must be called and at least one node should be added 526 ///with addSource() before using this function. 527 /// 528 ///This method runs the %DFS algorithm from the root node(s) 529 ///in order to 530 ///compute the 531 ///%DFS path to each node. The algorithm computes 532 /// The %DFS tree. 533 /// The distance of each node from the root(s). 534 /// 535 void start() 536 { 537 while ( !emptyQueue() ) processNextEdge(); 538 } 539 540 ///Executes the algorithm until \c dest is reached. 541 542 ///Executes the algorithm until \c dest is reached. 543 /// 544 ///\pre init() must be called and at least one node should be added 545 ///with addSource() before using this function. 546 /// 547 ///This method runs the %DFS algorithm from the root node(s) 548 ///in order to 549 ///compute the 550 ///%DFS path to \c dest. The algorithm computes 551 /// The %DFS path to \c dest. 552 /// The distance of \c dest from the root(s). 553 /// 554 void start(Node dest) 555 { 556 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge(); 557 } 558 559 ///Executes the algorithm until a condition is met. 560 561 ///Executes the algorithm until a condition is met. 562 /// 563 ///\pre init() must be called and at least one node should be added 564 ///with addSource() before using this function. 565 /// 566 ///\param nm must be a bool (or convertible) node map. The algorithm 567 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. 568 template<class NM> 569 void start(const NM &nm) 570 { 571 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge(); 572 } 573 574 ///Runs %DFS algorithm from node \c s. 575 576 ///This method runs the %DFS algorithm from a root node \c s 577 ///in order to 578 ///compute the 579 ///%DFS path to each node. The algorithm computes 580 /// The %DFS tree. 581 /// The distance of each node from the root. 582 /// 583 ///\note d.run(s) is just a shortcut of the following code. 584 ///\code 585 /// d.init(); 586 /// d.addSource(s); 587 /// d.start(); 588 ///\endcode 185 589 void run(Node s) { 186 187 init_maps();188 189 source = s;190 191 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {192 predecessor>set(u,INVALID); 193 pred_node>set(u,INVALID); 194 }195 196 int N = countNodes(*G);197 std::vector<typename Graph::OutEdgeIt> Q(N);198 199 int Qh=0;200 201 Q[Qh] = OutEdgeIt(*G,s);202 distance>set(s, 0);203 204 Node n=s;205 Node m;206 OutEdgeIt e;207 do {208 if((e=Q[Qh])!=INVALID) 209 if((m=G>target(e))!=s && (*predecessor)[m=G>target(e)]==INVALID) { 210 predecessor>set(m,e); 211 pred_node>set(m,n); 212 Q[++Qh] = OutEdgeIt(*G, m); 213 distance>set(m,Qh); 214 n=m; 215 } 216 else ++Q[Qh]; 217 else if(Qh>=0) n=G>source(Q[Qh]); 218 } while(Qh>=0);219 }220 221 ///The distance of a node from the root on the %DFS tree.222 223 ///Returns the distance of a node from the root on the %DFS tree.590 init(); 591 addSource(s); 592 start(); 593 } 594 595 ///Finds the %DFS path between \c s and \c t. 596 597 ///Finds the %DFS path between \c s and \c t. 598 /// 599 ///\return The length of the %DFS st path if there exists one, 600 ///0 otherwise. 601 ///\note Apart from the return value, d.run(s) is 602 ///just a shortcut of the following code. 603 ///\code 604 /// d.init(); 605 /// d.addSource(s); 606 /// d.start(t); 607 ///\endcode 608 int run(Node s,Node t) { 609 init(); 610 addSource(s); 611 start(t); 612 return reached(t)?_curr_dist1+(_queue_tail==_queue_next_dist):0; 613 } 614 615 ///@} 616 617 ///\name Query Functions 618 ///The result of the %DFS algorithm can be obtained using these 619 ///functions.\n 620 ///Before the use of these functions, 621 ///either run() or start() must be called. 622 623 ///@{ 624 625 ///The distance of a node from the root(s). 626 627 ///Returns the distance of a node from the root(s). 224 628 ///\pre \ref run() must be called before using this function. 225 ///\warning If node \c v in unreachable from the root the return value629 ///\warning If node \c v in unreachable from the root(s) the return value 226 630 ///of this funcion is undefined. 227 int dist(Node v) const { return (*distance)[v]; } 228 229 ///Returns the 'previous edge' of the %DFS path tree. 230 231 ///For a node \c v it returns the last edge of the path on the %DFS tree 232 ///from the root to \c 631 int dist(Node v) const { return (*_dist)[v]; } 632 633 ///Returns the 'previous edge' of the %DFS tree. 634 635 ///For a node \c v it returns the 'previous edge' 636 ///of the %DFS path, 637 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c 233 638 ///v. It is \ref INVALID 234 ///if \c v is unreachable from the root or if \c v=s. The639 ///if \c v is unreachable from the root(s) or \c v is a root. The 235 640 ///%DFS tree used here is equal to the %DFS tree used in 236 ///\ref predNode(Node v). \pre \ref run() must be called before using 641 ///\ref predNode(Node v). 642 ///\pre Either \ref run() or \ref start() must be called before using 237 643 ///this function. 238 Edge pred(Node v) const { return (*predecessor)[v]; } 644 ///\todo predEdge could be a better name. 645 Edge pred(Node v) const { return (*_pred)[v];} 239 646 240 647 ///Returns the 'previous node' of the %DFS tree. 241 648 242 ///For a node \c v it returns the 'previous node' on the %DFS tree, 243 ///i.e. it returns the last but one node of the path from the 244 ///root to \c /v on the %DFS tree. 245 ///It is INVALID if \c v is unreachable from the root or if 246 ///\c v=s. 247 ///\pre \ref run() must be called before 649 ///For a node \c v it returns the 'previous node' 650 ///of the %DFS tree, 651 ///i.e. it returns the last but one node from a %DFS path from the 652 ///root(a) to \c /v. 653 ///It is INVALID if \c v is unreachable from the root(s) or 654 ///if \c v itself a root. 655 ///The %DFS tree used here is equal to the %DFS 656 ///tree used in \ref pred(Node v). 657 ///\pre Either \ref run() or \ref start() must be called before 248 658 ///using this function. 249 Node predNode(Node v) const { return (*pred_node)[v]; } 250 251 ///Returns a reference to the NodeMap of distances on the %DFS tree. 252 253 ///Returns a reference to the NodeMap of distances on the %DFS tree. 254 ///\pre \ref run() must 659 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 660 G>source((*_pred)[v]); } 661 662 ///Returns a reference to the NodeMap of distances. 663 664 ///Returns a reference to the NodeMap of distances. 665 ///\pre Either \ref run() or \ref init() must 255 666 ///be called before using this function. 256 const DistMap &distMap() const { return * distance;}257 258 ///Returns a reference to the %DFS tree map.667 const DistMap &distMap() const { return *_dist;} 668 669 ///Returns a reference to the %DFS edgetree map. 259 670 260 671 ///Returns a reference to the NodeMap of the edges of the 261 672 ///%DFS tree. 262 ///\pre \ref run() must be called before using this function.263 const PredMap &predMap() const { return *predecessor;}264 265 ///Returns a reference to the map of last but one nodes of the %DFS tree.266 267 ///Returns a reference to the NodeMap of the last but one nodes of the paths 268 ///onthe269 ///%DFS tree.270 ///\pre \ref run() must be called before using this function.271 const PredNodeMap &predNodeMap() const { return *pred_node;}673 ///\pre Either \ref run() or \ref init() 674 ///must be called before using this function. 675 const PredMap &predMap() const { return *_pred;} 676 677 // ///Returns a reference to the map of nodes of %DFS paths. 678 679 // ///Returns a reference to the NodeMap of the last but one nodes of the 680 // ///%DFS tree. 681 // ///\pre \ref run() must be called before using this function. 682 // const PredNodeMap &predNodeMap() const { return *_predNode;} 272 683 273 684 ///Checks if a node is reachable from the root. 274 685 275 686 ///Returns \c true if \c v is reachable from the root. 276 ///\note The root node is reported to be reached! 277 /// 278 ///\pre \ref run() must be called before using this function. 279 /// 280 bool reached(Node v) { return v==source  (*predecessor)[v]!=INVALID; } 281 687 ///\warning The source nodes are inditated as unreached. 688 ///\pre Either \ref run() or \ref start() 689 ///must be called before using this function. 690 /// 691 bool reached(Node v) { return (*_reached)[v]; } 692 693 ///@} 694 }; 695 696 ///Default traits class of Dfs function. 697 698 ///Default traits class of Dfs function. 699 ///\param GR Graph type. 700 template<class GR> 701 struct DfsWizardDefaultTraits 702 { 703 ///The graph type the algorithm runs on. 704 typedef GR Graph; 705 ///\brief The type of the map that stores the last 706 ///edges of the %DFS paths. 707 /// 708 ///The type of the map that stores the last 709 ///edges of the %DFS paths. 710 ///It must meet the \ref concept::WriteMap "WriteMap" concept. 711 /// 712 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap; 713 ///Instantiates a PredMap. 714 715 ///This function instantiates a \ref PredMap. 716 ///\param G is the graph, to which we would like to define the PredMap. 717 ///\todo The graph alone may be insufficient to initialize 718 static PredMap *createPredMap(const GR &G) 719 { 720 return new PredMap(); 721 } 722 // ///\brief The type of the map that stores the last but one 723 // ///nodes of the %DFS paths. 724 // /// 725 // ///The type of the map that stores the last but one 726 // ///nodes of the %DFS paths. 727 // ///It must meet the \ref concept::WriteMap "WriteMap" concept. 728 // /// 729 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap; 730 // ///Instantiates a PredNodeMap. 731 732 // ///This function instantiates a \ref PredNodeMap. 733 // ///\param G is the graph, to which 734 // ///we would like to define the \ref PredNodeMap 735 // static PredNodeMap *createPredNodeMap(const GR &G) 736 // { 737 // return new PredNodeMap(); 738 // } 739 740 ///The type of the map that indicates which nodes are processed. 741 742 ///The type of the map that indicates which nodes are processed. 743 ///It must meet the \ref concept::WriteMap "WriteMap" concept. 744 ///\todo named parameter to set this type, function to read and write. 745 typedef NullMap<typename Graph::Node,bool> ProcessedMap; 746 ///Instantiates a ProcessedMap. 747 748 ///This function instantiates a \ref ProcessedMap. 749 ///\param G is the graph, to which 750 ///we would like to define the \ref ProcessedMap 751 static ProcessedMap *createProcessedMap(const GR &G) 752 { 753 return new ProcessedMap(); 754 } 755 ///The type of the map that indicates which nodes are reached. 756 757 ///The type of the map that indicates which nodes are reached. 758 ///It must meet the \ref concept::WriteMap "WriteMap" concept. 759 ///\todo named parameter to set this type, function to read and write. 760 typedef typename Graph::template NodeMap<bool> ReachedMap; 761 ///Instantiates a ReachedMap. 762 763 ///This function instantiates a \ref ReachedMap. 764 ///\param G is the graph, to which 765 ///we would like to define the \ref ReachedMap. 766 static ReachedMap *createReachedMap(const GR &G) 767 { 768 return new ReachedMap(G); 769 } 770 ///The type of the map that stores the dists of the nodes. 771 772 ///The type of the map that stores the dists of the nodes. 773 ///It must meet the \ref concept::WriteMap "WriteMap" concept. 774 /// 775 typedef NullMap<typename Graph::Node,int> DistMap; 776 ///Instantiates a DistMap. 777 778 ///This function instantiates a \ref DistMap. 779 ///\param G is the graph, to which we would like to define the \ref DistMap 780 static DistMap *createDistMap(const GR &G) 781 { 782 return new DistMap(); 783 } 282 784 }; 283 785 284 /// @} 786 /// Default traits used by \ref DfsWizard 787 788 /// To make it easier to use Dfs algorithm 789 ///we have created a wizard class. 790 /// This \ref DfsWizard class needs default traits, 791 ///as well as the \ref Dfs class. 792 /// The \ref DfsWizardBase is a class to be the default traits of the 793 /// \ref DfsWizard class. 794 template<class GR> 795 class DfsWizardBase : public DfsWizardDefaultTraits<GR> 796 { 797 798 typedef DfsWizardDefaultTraits<GR> Base; 799 protected: 800 /// Type of the nodes in the graph. 801 typedef typename Base::Graph::Node Node; 802 803 /// Pointer to the underlying graph. 804 void *_g; 805 ///Pointer to the map of reached nodes. 806 void *_reached; 807 ///Pointer to the map of processed nodes. 808 void *_processed; 809 ///Pointer to the map of predecessors edges. 810 void *_pred; 811 // ///Pointer to the map of predecessors nodes. 812 // void *_predNode; 813 ///Pointer to the map of distances. 814 void *_dist; 815 ///Pointer to the source node. 816 Node _source; 817 818 public: 819 /// Constructor. 820 821 /// This constructor does not require parameters, therefore it initiates 822 /// all of the attributes to default values (0, INVALID). 823 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 824 // _predNode(0), 825 _dist(0), _source(INVALID) {} 826 827 /// Constructor. 828 829 /// This constructor requires some parameters, 830 /// listed in the parameters list. 831 /// Others are initiated to 0. 832 /// \param g is the initial value of \ref _g 833 /// \param s is the initial value of \ref _source 834 DfsWizardBase(const GR &g, Node s=INVALID) : 835 _g((void *)&g), _reached(0), _processed(0), _pred(0), 836 // _predNode(0), 837 _dist(0), _source(s) {} 838 839 }; 285 840 841 /// A class to make the usage of Dfs algorithm easier 842 843 /// This class is created to make it easier to use Dfs algorithm. 844 /// It uses the functions and features of the plain \ref Dfs, 845 /// but it is much simpler to use it. 846 /// 847 /// Simplicity means that the way to change the types defined 848 /// in the traits class is based on functions that returns the new class 849 /// and not on templatable builtin classes. 850 /// When using the plain \ref Dfs 851 /// the new class with the modified type comes from 852 /// the original class by using the :: 853 /// operator. In the case of \ref DfsWizard only 854 /// a function have to be called and it will 855 /// return the needed class. 856 /// 857 /// It does not have own \ref run method. When its \ref run method is called 858 /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run 859 /// method of it. 860 template<class TR> 861 class DfsWizard : public TR 862 { 863 typedef TR Base; 864 865 ///The type of the underlying graph. 866 typedef typename TR::Graph Graph; 867 //\e 868 typedef typename Graph::Node Node; 869 //\e 870 typedef typename Graph::NodeIt NodeIt; 871 //\e 872 typedef typename Graph::Edge Edge; 873 //\e 874 typedef typename Graph::OutEdgeIt OutEdgeIt; 875 876 ///\brief The type of the map that stores 877 ///the reached nodes 878 typedef typename TR::ReachedMap ReachedMap; 879 ///\brief The type of the map that stores 880 ///the processed nodes 881 typedef typename TR::ProcessedMap ProcessedMap; 882 ///\brief The type of the map that stores the last 883 ///edges of the %DFS paths. 884 typedef typename TR::PredMap PredMap; 885 // ///\brief The type of the map that stores the last but one 886 // ///nodes of the %DFS paths. 887 // typedef typename TR::PredNodeMap PredNodeMap; 888 ///The type of the map that stores the dists of the nodes. 889 typedef typename TR::DistMap DistMap; 890 891 public: 892 /// Constructor. 893 DfsWizard() : TR() {} 894 895 /// Constructor that requires parameters. 896 897 /// Constructor that requires parameters. 898 /// These parameters will be the default values for the traits class. 899 DfsWizard(const Graph &g, Node s=INVALID) : 900 TR(g,s) {} 901 902 ///Copy constructor 903 DfsWizard(const TR &b) : TR(b) {} 904 905 ~DfsWizard() {} 906 907 ///Runs Dfs algorithm from a given node. 908 909 ///Runs Dfs algorithm from a given node. 910 ///The node can be given by the \ref source function. 911 void run() 912 { 913 if(Base::_source==INVALID) throw UninitializedParameter(); 914 Dfs<Graph,TR> alg(*(Graph*)Base::_g); 915 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached); 916 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed); 917 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred); 918 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode); 919 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist); 920 alg.run(Base::_source); 921 } 922 923 ///Runs Dfs algorithm from the given node. 924 925 ///Runs Dfs algorithm from the given node. 926 ///\param s is the given source. 927 void run(Node s) 928 { 929 Base::_source=s; 930 run(); 931 } 932 933 template<class T> 934 struct DefPredMapBase : public Base { 935 typedef T PredMap; 936 static PredMap *createPredMap(const Graph &G) { return 0; }; 937 DefPredMapBase(const Base &b) : Base(b) {} 938 }; 939 940 ///\brief \ref namedtemplparam "Named parameter" 941 ///function for setting PredMap type 942 /// 943 /// \ref namedtemplparam "Named parameter" 944 ///function for setting PredMap type 945 /// 946 template<class T> 947 DfsWizard<DefPredMapBase<T> > predMap(const T &t) 948 { 949 Base::_pred=(void *)&t; 950 return DfsWizard<DefPredMapBase<T> >(*this); 951 } 952 953 954 template<class T> 955 struct DefReachedMapBase : public Base { 956 typedef T ReachedMap; 957 static ReachedMap *createReachedMap(const Graph &G) { return 0; }; 958 DefReachedMapBase(const Base &b) : Base(b) {} 959 }; 960 961 ///\brief \ref namedtemplparam "Named parameter" 962 ///function for setting ReachedMap 963 /// 964 /// \ref namedtemplparam "Named parameter" 965 ///function for setting ReachedMap 966 /// 967 template<class T> 968 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 969 { 970 Base::_pred=(void *)&t; 971 return DfsWizard<DefReachedMapBase<T> >(*this); 972 } 973 974 975 template<class T> 976 struct DefProcessedMapBase : public Base { 977 typedef T ProcessedMap; 978 static ProcessedMap *createProcessedMap(const Graph &G) { return 0; }; 979 DefProcessedMapBase(const Base &b) : Base(b) {} 980 }; 981 982 ///\brief \ref namedtemplparam "Named parameter" 983 ///function for setting ProcessedMap 984 /// 985 /// \ref namedtemplparam "Named parameter" 986 ///function for setting ProcessedMap 987 /// 988 template<class T> 989 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 990 { 991 Base::_pred=(void *)&t; 992 return DfsWizard<DefProcessedMapBase<T> >(*this); 993 } 994 995 996 // template<class T> 997 // struct DefPredNodeMapBase : public Base { 998 // typedef T PredNodeMap; 999 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; 1000 // DefPredNodeMapBase(const Base &b) : Base(b) {} 1001 // }; 1002 1003 // ///\brief \ref namedtemplparam "Named parameter" 1004 // ///function for setting PredNodeMap type 1005 // /// 1006 // /// \ref namedtemplparam "Named parameter" 1007 // ///function for setting PredNodeMap type 1008 // /// 1009 // template<class T> 1010 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 1011 // { 1012 // Base::_predNode=(void *)&t; 1013 // return DfsWizard<DefPredNodeMapBase<T> >(*this); 1014 // } 1015 1016 template<class T> 1017 struct DefDistMapBase : public Base { 1018 typedef T DistMap; 1019 static DistMap *createDistMap(const Graph &G) { return 0; }; 1020 DefDistMapBase(const Base &b) : Base(b) {} 1021 }; 1022 1023 ///\brief \ref namedtemplparam "Named parameter" 1024 ///function for setting DistMap type 1025 /// 1026 /// \ref namedtemplparam "Named parameter" 1027 ///function for setting DistMap type 1028 /// 1029 template<class T> 1030 DfsWizard<DefDistMapBase<T> > distMap(const T &t) 1031 { 1032 Base::_dist=(void *)&t; 1033 return DfsWizard<DefDistMapBase<T> >(*this); 1034 } 1035 1036 /// Sets the source node, from which the Dfs algorithm runs. 1037 1038 /// Sets the source node, from which the Dfs algorithm runs. 1039 /// \param s is the source node. 1040 DfsWizard<TR> &source(Node s) 1041 { 1042 Base::_source=s; 1043 return *this; 1044 } 1045 1046 }; 1047 1048 ///Function type interface for Dfs algorithm. 1049 1050 /// \ingroup flowalgs 1051 ///Function type interface for Dfs algorithm. 1052 /// 1053 ///This function also has several 1054 ///\ref namedtemplfuncparam "named parameters", 1055 ///they are declared as the members of class \ref DfsWizard. 1056 ///The following 1057 ///example shows how to use these parameters. 1058 ///\code 1059 /// dfs(g,source).predMap(preds).run(); 1060 ///\endcode 1061 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" 1062 ///to the end of the parameter list. 1063 ///\sa DfsWizard 1064 ///\sa Dfs 1065 template<class GR> 1066 DfsWizard<DfsWizardBase<GR> > 1067 dfs(const GR &g,typename GR::Node s=INVALID) 1068 { 1069 return DfsWizard<DfsWizardBase<GR> >(g,s); 1070 } 1071 286 1072 } //END OF NAMESPACE LEMON 287 1073 288 1074 #endif 289 1075 290
Note: See TracChangeset
for help on using the changeset viewer.