Changeset 209:765619b7cbb2 in lemon1.2 for lemon/dfs.h
 Timestamp:
 07/13/08 20:51:02 (16 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dfs.h
r158 r209 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 35 35 namespace lemon { 36 36 37 37 38 38 ///Default traits class of Dfs class. 39 39 … … 43 43 struct DfsDefaultTraits 44 44 { 45 ///The digraph type the algorithm runs on. 45 ///The digraph type the algorithm runs on. 46 46 typedef GR Digraph; 47 47 ///\brief The type of the map that stores the last 48 48 ///arcs of the %DFS paths. 49 /// 49 /// 50 50 ///The type of the map that stores the last 51 51 ///arcs of the %DFS paths. … … 54 54 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; 55 55 ///Instantiates a PredMap. 56 57 ///This function instantiates a \ref PredMap. 56 57 ///This function instantiates a \ref PredMap. 58 58 ///\param G is the digraph, to which we would like to define the PredMap. 59 59 ///\todo The digraph alone may be insufficient to initialize 60 static PredMap *createPredMap(const GR &G) 60 static PredMap *createPredMap(const GR &G) 61 61 { 62 62 return new PredMap(G); … … 64 64 65 65 ///The type of the map that indicates which nodes are processed. 66 66 67 67 ///The type of the map that indicates which nodes are processed. 68 68 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 70 70 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 71 71 ///Instantiates a ProcessedMap. 72 73 ///This function instantiates a \ref ProcessedMap. 72 73 ///This function instantiates a \ref ProcessedMap. 74 74 ///\param g is the digraph, to which 75 75 ///we would like to define the \ref ProcessedMap … … 83 83 } 84 84 ///The type of the map that indicates which nodes are reached. 85 85 86 86 ///The type of the map that indicates which nodes are reached. 87 87 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 89 89 typedef typename Digraph::template NodeMap<bool> ReachedMap; 90 90 ///Instantiates a ReachedMap. 91 92 ///This function instantiates a \ref ReachedMap. 91 92 ///This function instantiates a \ref ReachedMap. 93 93 ///\param G is the digraph, to which 94 94 ///we would like to define the \ref ReachedMap. … … 98 98 } 99 99 ///The type of the map that stores the dists of the nodes. 100 100 101 101 ///The type of the map that stores the dists of the nodes. 102 102 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 104 104 typedef typename Digraph::template NodeMap<int> DistMap; 105 105 ///Instantiates a DistMap. 106 107 ///This function instantiates a \ref DistMap. 106 107 ///This function instantiates a \ref DistMap. 108 108 ///\param G is the digraph, to which we would like to define the \ref DistMap 109 109 static DistMap *createDistMap(const GR &G) … … 112 112 } 113 113 }; 114 114 115 115 ///%DFS algorithm class. 116 116 117 117 ///\ingroup search 118 118 ///This class provides an efficient implementation of the %DFS algorithm. … … 128 128 #ifdef DOXYGEN 129 129 template <typename GR, 130 130 typename TR> 131 131 #else 132 132 template <typename GR=ListDigraph, 133 133 typename TR=DfsDefaultTraits<GR> > 134 134 #endif 135 135 class Dfs { … … 144 144 public: 145 145 virtual const char* what() const throw() { 146 146 return "lemon::Dfs::UninitializedParameter"; 147 147 } 148 148 }; … … 159 159 ///\e 160 160 typedef typename Digraph::OutArcIt OutArcIt; 161 161 162 162 ///\brief The type of the map that stores the last 163 163 ///arcs of the %DFS paths. … … 193 193 194 194 ///Creates the maps if necessary. 195 195 196 196 ///\todo Better memory allocation (instead of new). 197 void create_maps() 197 void create_maps() 198 198 { 199 199 if(!_pred) { 200 201 200 local_pred = true; 201 _pred = Traits::createPredMap(*G); 202 202 } 203 203 if(!_dist) { 204 205 204 local_dist = true; 205 _dist = Traits::createDistMap(*G); 206 206 } 207 207 if(!_reached) { 208 209 208 local_reached = true; 209 _reached = Traits::createReachedMap(*G); 210 210 } 211 211 if(!_processed) { 212 213 212 local_processed = true; 213 _processed = Traits::createProcessedMap(*G); 214 214 } 215 215 } … … 218 218 219 219 Dfs() {} 220 220 221 221 public: 222 222 … … 230 230 struct DefPredMapTraits : public Traits { 231 231 typedef T PredMap; 232 static PredMap *createPredMap(const Digraph &G) 232 static PredMap *createPredMap(const Digraph &G) 233 233 { 234 234 throw UninitializedParameter(); 235 235 } 236 236 }; … … 244 244 typedef Dfs<Digraph, DefPredMapTraits<T> > Create; 245 245 }; 246 247 246 247 248 248 template <class T> 249 249 struct DefDistMapTraits : public Traits { 250 250 typedef T DistMap; 251 static DistMap *createDistMap(const Digraph &) 251 static DistMap *createDistMap(const Digraph &) 252 252 { 253 253 throw UninitializedParameter(); 254 254 } 255 255 }; … … 263 263 typedef Dfs<Digraph, DefDistMapTraits<T> > Create; 264 264 }; 265 265 266 266 template <class T> 267 267 struct DefReachedMapTraits : public Traits { 268 268 typedef T ReachedMap; 269 static ReachedMap *createReachedMap(const Digraph &) 269 static ReachedMap *createReachedMap(const Digraph &) 270 270 { 271 271 throw UninitializedParameter(); 272 272 } 273 273 }; … … 285 285 struct DefProcessedMapTraits : public Traits { 286 286 typedef T ProcessedMap; 287 static ProcessedMap *createProcessedMap(const Digraph &) 287 static ProcessedMap *createProcessedMap(const Digraph &) 288 288 { 289 289 throw UninitializedParameter(); 290 290 } 291 291 }; … … 296 296 /// 297 297 template <class T> 298 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { 298 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { 299 299 typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create; 300 300 }; 301 301 302 302 struct DefDigraphProcessedMapTraits : public Traits { 303 303 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 304 static ProcessedMap *createProcessedMap(const Digraph &G) 304 static ProcessedMap *createProcessedMap(const Digraph &G) 305 305 { 306 306 return new ProcessedMap(G); 307 307 } 308 308 }; … … 315 315 template <class T> 316 316 class DefProcessedMapToBeDefaultMap : 317 public Dfs< Digraph, DefDigraphProcessedMapTraits> { 317 public Dfs< Digraph, DefDigraphProcessedMapTraits> { 318 318 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create; 319 319 }; 320 320 321 321 ///@} 322 322 323 public: 324 323 public: 324 325 325 ///Constructor. 326 326 327 327 ///\param _G the digraph the algorithm will run on. 328 328 /// … … 334 334 _processed(NULL), local_processed(false) 335 335 { } 336 336 337 337 ///Destructor. 338 ~Dfs() 338 ~Dfs() 339 339 { 340 340 if(local_pred) delete _pred; … … 351 351 ///automatically allocated map, of course. 352 352 ///\return <tt> (*this) </tt> 353 Dfs &predMap(PredMap &m) 353 Dfs &predMap(PredMap &m) 354 354 { 355 355 if(local_pred) { 356 357 356 delete _pred; 357 local_pred=false; 358 358 } 359 359 _pred = &m; … … 368 368 ///automatically allocated map, of course. 369 369 ///\return <tt> (*this) </tt> 370 Dfs &distMap(DistMap &m) 370 Dfs &distMap(DistMap &m) 371 371 { 372 372 if(local_dist) { 373 374 373 delete _dist; 374 local_dist=false; 375 375 } 376 376 _dist = &m; … … 385 385 ///automatically allocated map, of course. 386 386 ///\return <tt> (*this) </tt> 387 Dfs &reachedMap(ReachedMap &m) 387 Dfs &reachedMap(ReachedMap &m) 388 388 { 389 389 if(local_reached) { 390 391 390 delete _reached; 391 local_reached=false; 392 392 } 393 393 _reached = &m; … … 402 402 ///automatically allocated map, of course. 403 403 ///\return <tt> (*this) </tt> 404 Dfs &processedMap(ProcessedMap &m) 404 Dfs &processedMap(ProcessedMap &m) 405 405 { 406 406 if(local_processed) { 407 408 407 delete _processed; 408 local_processed=false; 409 409 } 410 410 _processed = &m; … … 435 435 _stack_head=1; 436 436 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 437 438 439 440 441 } 442 } 443 437 _pred>set(u,INVALID); 438 // _predNode>set(u,INVALID); 439 _reached>set(u,false); 440 _processed>set(u,false); 441 } 442 } 443 444 444 ///Adds a new source node. 445 445 … … 451 451 { 452 452 if(!(*_reached)[s]) 453 454 455 456 457 458 459 460 461 462 463 464 465 466 } 467 453 { 454 _reached>set(s,true); 455 _pred>set(s,INVALID); 456 OutArcIt e(*G,s); 457 if(e!=INVALID) { 458 _stack[++_stack_head]=e; 459 _dist>set(s,_stack_head); 460 } 461 else { 462 _processed>set(s,true); 463 _dist>set(s,0); 464 } 465 } 466 } 467 468 468 ///Processes the next arc. 469 469 … … 474 474 ///\pre The stack must not be empty! 475 475 Arc processNextArc() 476 { 476 { 477 477 Node m; 478 478 Arc e=_stack[_stack_head]; 479 479 if(!(*_reached)[m=G>target(e)]) { 480 481 482 483 484 480 _pred>set(m,e); 481 _reached>set(m,true); 482 ++_stack_head; 483 _stack[_stack_head] = OutArcIt(*G, m); 484 _dist>set(m,_stack_head); 485 485 } 486 486 else { 487 488 487 m=G>source(e); 488 ++_stack[_stack_head]; 489 489 } 490 490 while(_stack_head>=0 && _stack[_stack_head]==INVALID) { 491 492 493 494 495 496 491 _processed>set(m,true); 492 _stack_head; 493 if(_stack_head>=0) { 494 m=G>source(_stack[_stack_head]); 495 ++_stack[_stack_head]; 496 } 497 497 } 498 498 return e; … … 505 505 /// empty. 506 506 OutArcIt nextArc() 507 { 507 { 508 508 return _stack_head>=0?_stack[_stack_head]:INVALID; 509 509 } … … 516 516 bool emptyQueue() { return _stack_head<0; } 517 517 ///Returns the number of the nodes to be processed. 518 518 519 519 ///Returns the number of the nodes to be processed in the queue. 520 520 int queueSize() { return _stack_head+1; } 521 521 522 522 ///Executes the algorithm. 523 523 … … 538 538 while ( !emptyQueue() ) processNextArc(); 539 539 } 540 540 541 541 ///Executes the algorithm until \c dest is reached. 542 542 … … 555 555 void start(Node dest) 556 556 { 557 while ( !emptyQueue() && G>target(_stack[_stack_head])!=dest ) 558 559 } 560 557 while ( !emptyQueue() && G>target(_stack[_stack_head])!=dest ) 558 processNextArc(); 559 } 560 561 561 ///Executes the algorithm until a condition is met. 562 562 … … 583 583 584 584 ///Runs %DFS algorithm to visit all nodes in the digraph. 585 585 586 586 ///This method runs the %DFS algorithm in order to 587 587 ///compute the … … 611 611 612 612 ///Runs %DFS algorithm from node \c s. 613 613 614 614 ///This method runs the %DFS algorithm from a root node \c s 615 615 ///in order to … … 630 630 start(); 631 631 } 632 632 633 633 ///Finds the %DFS path between \c s and \c t. 634 634 635 635 ///Finds the %DFS path between \c s and \c t. 636 636 /// … … 650 650 return reached(t)?_stack_head+1:0; 651 651 } 652 652 653 653 ///@} 654 654 … … 658 658 ///Before the use of these functions, 659 659 ///either run() or start() must be called. 660 660 661 661 ///@{ 662 662 … … 664 664 665 665 ///Gives back the shortest path. 666 666 667 667 ///Gives back the shortest path. 668 668 ///\pre The \c t should be reachable from the source. 669 Path path(Node t) 669 Path path(Node t) 670 670 { 671 671 return Path(*G, *_pred, t); … … 676 676 ///Returns the distance of a node from the root(s). 677 677 ///\pre \ref run() must be called before using this function. 678 ///\warning If node \c v is unreachable from the root(s) then the return 678 ///\warning If node \c v is unreachable from the root(s) then the return 679 679 ///value of this funcion is undefined. 680 680 int dist(Node v) const { return (*_dist)[v]; } … … 706 706 ///using this function. 707 707 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 708 709 708 G>source((*_pred)[v]); } 709 710 710 ///Returns a reference to the NodeMap of distances. 711 711 … … 714 714 ///be called before using this function. 715 715 const DistMap &distMap() const { return *_dist;} 716 716 717 717 ///Returns a reference to the %DFS arctree map. 718 718 … … 722 722 ///must be called before using this function. 723 723 const PredMap &predMap() const { return *_pred;} 724 724 725 725 ///Checks if a node is reachable from the root. 726 726 … … 731 731 /// 732 732 bool reached(Node v) { return (*_reached)[v]; } 733 733 734 734 ///@} 735 735 }; … … 742 742 struct DfsWizardDefaultTraits 743 743 { 744 ///The digraph type the algorithm runs on. 744 ///The digraph type the algorithm runs on. 745 745 typedef GR Digraph; 746 746 ///\brief The type of the map that stores the last 747 747 ///arcs of the %DFS paths. 748 /// 748 /// 749 749 ///The type of the map that stores the last 750 750 ///arcs of the %DFS paths. … … 753 753 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; 754 754 ///Instantiates a PredMap. 755 756 ///This function instantiates a \ref PredMap. 755 756 ///This function instantiates a \ref PredMap. 757 757 ///\param g is the digraph, to which we would like to define the PredMap. 758 758 ///\todo The digraph alone may be insufficient to initialize 759 759 #ifdef DOXYGEN 760 static PredMap *createPredMap(const GR &g) 760 static PredMap *createPredMap(const GR &g) 761 761 #else 762 static PredMap *createPredMap(const GR &) 762 static PredMap *createPredMap(const GR &) 763 763 #endif 764 764 { … … 767 767 768 768 ///The type of the map that indicates which nodes are processed. 769 769 770 770 ///The type of the map that indicates which nodes are processed. 771 771 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 773 773 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 774 774 ///Instantiates a ProcessedMap. 775 776 ///This function instantiates a \ref ProcessedMap. 775 776 ///This function instantiates a \ref ProcessedMap. 777 777 ///\param g is the digraph, to which 778 778 ///we would like to define the \ref ProcessedMap … … 786 786 } 787 787 ///The type of the map that indicates which nodes are reached. 788 788 789 789 ///The type of the map that indicates which nodes are reached. 790 790 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 792 792 typedef typename Digraph::template NodeMap<bool> ReachedMap; 793 793 ///Instantiates a ReachedMap. 794 795 ///This function instantiates a \ref ReachedMap. 794 795 ///This function instantiates a \ref ReachedMap. 796 796 ///\param G is the digraph, to which 797 797 ///we would like to define the \ref ReachedMap. … … 801 801 } 802 802 ///The type of the map that stores the dists of the nodes. 803 803 804 804 ///The type of the map that stores the dists of the nodes. 805 805 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 807 807 typedef NullMap<typename Digraph::Node,int> DistMap; 808 808 ///Instantiates a DistMap. 809 810 ///This function instantiates a \ref DistMap. 809 810 ///This function instantiates a \ref DistMap. 811 811 ///\param g is the digraph, to which we would like to define the \ref DistMap 812 812 #ifdef DOXYGEN … … 819 819 } 820 820 }; 821 821 822 822 /// Default traits used by \ref DfsWizard 823 823 … … 849 849 ///Pointer to the source node. 850 850 Node _source; 851 851 852 852 public: 853 853 /// Constructor. 854 854 855 855 /// This constructor does not require parameters, therefore it initiates 856 856 /// all of the attributes to default values (0, INVALID). 857 857 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 858 858 _dist(0), _source(INVALID) {} 859 859 860 860 /// Constructor. 861 861 862 862 /// This constructor requires some parameters, 863 863 /// listed in the parameters list. … … 866 866 /// \param s is the initial value of \ref _source 867 867 DfsWizardBase(const GR &g, Node s=INVALID) : 868 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 868 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 869 869 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} 870 870 871 871 }; 872 872 873 873 /// A class to make the usage of the Dfs algorithm easier 874 874 … … 905 905 //\e 906 906 typedef typename Digraph::OutArcIt OutArcIt; 907 907 908 908 ///\brief The type of the map that stores 909 909 ///the reached nodes … … 935 935 936 936 ///Runs Dfs algorithm from a given node. 937 937 938 938 ///Runs Dfs algorithm from a given node. 939 939 ///The node can be given by the \ref source function. … … 942 942 if(Base::_source==INVALID) throw UninitializedParameter(); 943 943 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 944 if(Base::_reached) 944 if(Base::_reached) 945 945 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 946 if(Base::_processed) 946 if(Base::_processed) 947 947 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 948 if(Base::_pred) 948 if(Base::_pred) 949 949 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 950 if(Base::_dist) 950 if(Base::_dist) 951 951 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 952 952 alg.run(Base::_source); … … 969 969 DefPredMapBase(const TR &b) : TR(b) {} 970 970 }; 971 971 972 972 ///\brief \ref namedtemplparam "Named parameter" 973 973 ///function for setting PredMap type … … 977 977 /// 978 978 template<class T> 979 DfsWizard<DefPredMapBase<T> > predMap(const T &t) 979 DfsWizard<DefPredMapBase<T> > predMap(const T &t) 980 980 { 981 981 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 982 982 return DfsWizard<DefPredMapBase<T> >(*this); 983 983 } 984 985 984 985 986 986 template<class T> 987 987 struct DefReachedMapBase : public Base { … … 990 990 DefReachedMapBase(const TR &b) : TR(b) {} 991 991 }; 992 992 993 993 ///\brief \ref namedtemplparam "Named parameter" 994 994 ///function for setting ReachedMap … … 998 998 /// 999 999 template<class T> 1000 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 1000 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 1001 1001 { 1002 1002 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1003 1003 return DfsWizard<DefReachedMapBase<T> >(*this); 1004 1004 } 1005 1005 1006 1006 1007 1007 template<class T> … … 1011 1011 DefProcessedMapBase(const TR &b) : TR(b) {} 1012 1012 }; 1013 1013 1014 1014 ///\brief \ref namedtemplparam "Named parameter" 1015 1015 ///function for setting ProcessedMap … … 1019 1019 /// 1020 1020 template<class T> 1021 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 1021 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 1022 1022 { 1023 1023 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); 1024 1024 return DfsWizard<DefProcessedMapBase<T> >(*this); 1025 1025 } 1026 1026 1027 1027 template<class T> 1028 1028 struct DefDistMapBase : public Base { … … 1031 1031 DefDistMapBase(const TR &b) : TR(b) {} 1032 1032 }; 1033 1033 1034 1034 ///\brief \ref namedtemplparam "Named parameter" 1035 1035 ///function for setting DistMap type … … 1039 1039 /// 1040 1040 template<class T> 1041 DfsWizard<DefDistMapBase<T> > distMap(const T &t) 1041 DfsWizard<DefDistMapBase<T> > distMap(const T &t) 1042 1042 { 1043 1043 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1044 1044 return DfsWizard<DefDistMapBase<T> >(*this); 1045 1045 } 1046 1046 1047 1047 /// Sets the source node, from which the Dfs algorithm runs. 1048 1048 1049 1049 /// Sets the source node, from which the Dfs algorithm runs. 1050 1050 /// \param s is the source node. 1051 DfsWizard<TR> &source(Node s) 1051 DfsWizard<TR> &source(Node s) 1052 1052 { 1053 1053 Base::_source=s; 1054 1054 return *this; 1055 1055 } 1056 1056 1057 1057 }; 1058 1058 1059 1059 ///Function type interface for Dfs algorithm. 1060 1060 … … 1083 1083 #ifdef DOXYGEN 1084 1084 /// \brief Visitor class for dfs. 1085 /// 1086 /// It gives a simple interface for a functional interface for dfs 1087 /// traversal. The traversal on a linear data structure. 1085 /// 1086 /// It gives a simple interface for a functional interface for dfs 1087 /// traversal. The traversal on a linear data structure. 1088 1088 template <typename _Digraph> 1089 1089 struct DfsVisitor { … … 1092 1092 typedef typename Digraph::Node Node; 1093 1093 /// \brief Called when the arc reach a node. 1094 /// 1094 /// 1095 1095 /// It is called when the dfs find an arc which target is not 1096 1096 /// reached yet. 1097 1097 void discover(const Arc& arc) {} 1098 1098 /// \brief Called when the node reached first time. 1099 /// 1099 /// 1100 1100 /// It is Called when the node reached first time. 1101 1101 void reach(const Node& node) {} 1102 1102 /// \brief Called when we step back on an arc. 1103 /// 1103 /// 1104 1104 /// It is called when the dfs should step back on the arc. 1105 1105 void backtrack(const Arc& arc) {} 1106 1106 /// \brief Called when we step back from the node. 1107 /// 1107 /// 1108 1108 /// It is called when we step back from the node. 1109 1109 void leave(const Node& node) {} 1110 /// \brief Called when the arc examined but target of the arc 1110 /// \brief Called when the arc examined but target of the arc 1111 1111 /// already discovered. 1112 /// 1113 /// It called when the arc examined but the target of the arc 1112 /// 1113 /// It called when the arc examined but the target of the arc 1114 1114 /// already discovered. 1115 1115 void examine(const Arc& arc) {} 1116 1116 /// \brief Called for the source node of the dfs. 1117 /// 1117 /// 1118 1118 /// It is called for the source node of the dfs. 1119 1119 void start(const Node& node) {} 1120 1120 /// \brief Called when we leave the source node of the dfs. 1121 /// 1121 /// 1122 1122 /// It is called when we leave the source node of the dfs. 1123 1123 void stop(const Node& node) {} … … 1141 1141 struct Constraints { 1142 1142 void constraints() { 1143 1144 1145 1146 1147 1148 1149 1150 1151 1143 Arc arc; 1144 Node node; 1145 visitor.discover(arc); 1146 visitor.reach(node); 1147 visitor.backtrack(arc); 1148 visitor.leave(node); 1149 visitor.examine(arc); 1150 visitor.start(node); 1151 visitor.stop(arc); 1152 1152 } 1153 1153 _Visitor& visitor; … … 1163 1163 struct DfsVisitDefaultTraits { 1164 1164 1165 /// \brief The digraph type the algorithm runs on. 1165 /// \brief The digraph type the algorithm runs on. 1166 1166 typedef _Digraph Digraph; 1167 1167 1168 1168 /// \brief The type of the map that indicates which nodes are reached. 1169 /// 1169 /// 1170 1170 /// The type of the map that indicates which nodes are reached. 1171 1171 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 1175 1175 /// \brief Instantiates a ReachedMap. 1176 1176 /// 1177 /// This function instantiates a \ref ReachedMap. 1177 /// This function instantiates a \ref ReachedMap. 1178 1178 /// \param digraph is the digraph, to which 1179 1179 /// we would like to define the \ref ReachedMap. … … 1183 1183 1184 1184 }; 1185 1185 1186 1186 /// %DFS Visit algorithm class. 1187 1187 1188 1188 /// \ingroup search 1189 1189 /// This class provides an efficient implementation of the %DFS algorithm … … 1192 1192 /// The %DfsVisit class provides an alternative interface to the Dfs 1193 1193 /// class. It works with callback mechanism, the DfsVisit object calls 1194 /// on every dfs event the \c Visitor class member functions. 1194 /// on every dfs event the \c Visitor class member functions. 1195 1195 /// 1196 1196 /// \tparam _Digraph The digraph type the algorithm runs on. The default value is 1197 1197 /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it 1198 1198 /// is only passed to \ref DfsDefaultTraits. 1199 /// \tparam _Visitor The Visitor object for the algorithm. The 1199 /// \tparam _Visitor The Visitor object for the algorithm. The 1200 1200 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which 1201 1201 /// does not observe the Dfs events. If you want to observe the dfs 1202 1202 /// events you should implement your own Visitor class. 1203 /// \tparam _Traits Traits class to set various data types used by the 1203 /// \tparam _Traits Traits class to set various data types used by the 1204 1204 /// algorithm. The default traits class is 1205 1205 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". … … 1212 1212 #else 1213 1213 template <typename _Digraph = ListDigraph, 1214 1215 1214 typename _Visitor = DfsVisitor<_Digraph>, 1215 typename _Traits = DfsDefaultTraits<_Digraph> > 1216 1216 #endif 1217 1217 class DfsVisit { 1218 1218 public: 1219 1219 1220 1220 /// \brief \ref Exception for uninitialized parameters. 1221 1221 /// … … 1224 1224 class UninitializedParameter : public lemon::UninitializedParameter { 1225 1225 public: 1226 virtual const char* what() const throw() 1226 virtual const char* what() const throw() 1227 1227 { 1228 1228 return "lemon::DfsVisit::UninitializedParameter"; 1229 1229 } 1230 1230 }; … … 1263 1263 void create_maps() { 1264 1264 if(!_reached) { 1265 1266 1265 local_reached = true; 1266 _reached = Traits::createReachedMap(*_digraph); 1267 1267 } 1268 1268 } … … 1271 1271 1272 1272 DfsVisit() {} 1273 1273 1274 1274 public: 1275 1275 … … 1283 1283 typedef T ReachedMap; 1284 1284 static ReachedMap *createReachedMap(const Digraph &digraph) { 1285 1286 } 1287 }; 1288 /// \brief \ref namedtemplparam "Named parameter" for setting 1285 throw UninitializedParameter(); 1286 } 1287 }; 1288 /// \brief \ref namedtemplparam "Named parameter" for setting 1289 1289 /// ReachedMap type 1290 1290 /// … … 1292 1292 template <class T> 1293 1293 struct DefReachedMap : public DfsVisit< Digraph, Visitor, 1294 1294 DefReachedMapTraits<T> > { 1295 1295 typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create; 1296 1296 }; 1297 1297 ///@} 1298 1298 1299 public: 1300 1299 public: 1300 1301 1301 /// \brief Constructor. 1302 1302 /// … … 1306 1306 /// \param visitor The visitor of the algorithm. 1307 1307 /// 1308 DfsVisit(const Digraph& digraph, Visitor& visitor) 1308 DfsVisit(const Digraph& digraph, Visitor& visitor) 1309 1309 : _digraph(&digraph), _visitor(&visitor), 1310 1311 1310 _reached(0), local_reached(false) {} 1311 1312 1312 /// \brief Destructor. 1313 1313 /// … … 1326 1326 DfsVisit &reachedMap(ReachedMap &m) { 1327 1327 if(local_reached) { 1328 1329 1328 delete _reached; 1329 local_reached=false; 1330 1330 } 1331 1331 _reached = &m; … … 1354 1354 _stack_head = 1; 1355 1355 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { 1356 1357 } 1358 } 1359 1356 _reached>set(u, false); 1357 } 1358 } 1359 1360 1360 /// \brief Adds a new source node. 1361 1361 /// … … 1363 1363 void addSource(Node s) { 1364 1364 if(!(*_reached)[s]) { 1365 1366 1367 1368 Arc e; 1369 1370 1371 1372 1373 1374 1375 1376 } 1377 1365 _reached>set(s,true); 1366 _visitor>start(s); 1367 _visitor>reach(s); 1368 Arc e; 1369 _digraph>firstOut(e, s); 1370 if (e != INVALID) { 1371 _stack[++_stack_head] = e; 1372 } else { 1373 _visitor>leave(s); 1374 } 1375 } 1376 } 1377 1378 1378 /// \brief Processes the next arc. 1379 1379 /// … … 1383 1383 /// 1384 1384 /// \pre The stack must not be empty! 1385 Arc processNextArc() { 1385 Arc processNextArc() { 1386 1386 Arc e = _stack[_stack_head]; 1387 1387 Node m = _digraph>target(e); 1388 1388 if(!(*_reached)[m]) { 1389 1390 1391 1392 1389 _visitor>discover(e); 1390 _visitor>reach(m); 1391 _reached>set(m, true); 1392 _digraph>firstOut(_stack[++_stack_head], m); 1393 1393 } else { 1394 1395 1396 1394 _visitor>examine(e); 1395 m = _digraph>source(e); 1396 _digraph>nextOut(_stack[_stack_head]); 1397 1397 } 1398 1398 while (_stack_head>=0 && _stack[_stack_head] == INVALID) { 1399 1400 1401 1402 1403 1404 1405 1406 _visitor>stop(m); 1407 1399 _visitor>leave(m); 1400 _stack_head; 1401 if (_stack_head >= 0) { 1402 _visitor>backtrack(_stack[_stack_head]); 1403 m = _digraph>source(_stack[_stack_head]); 1404 _digraph>nextOut(_stack[_stack_head]); 1405 } else { 1406 _visitor>stop(m); 1407 } 1408 1408 } 1409 1409 return e; … … 1416 1416 /// \return The next arc to be processed or INVALID if the stack is 1417 1417 /// empty. 1418 Arc nextArc() { 1418 Arc nextArc() { 1419 1419 return _stack_head >= 0 ? _stack[_stack_head] : INVALID; 1420 1420 } … … 1431 1431 /// Returns the number of the nodes to be processed in the queue. 1432 1432 int queueSize() { return _stack_head + 1; } 1433 1433 1434 1434 /// \brief Executes the algorithm. 1435 1435 /// … … 1441 1441 while ( !emptyQueue() ) processNextArc(); 1442 1442 } 1443 1443 1444 1444 /// \brief Executes the algorithm until \c dest is reached. 1445 1445 /// … … 1449 1449 /// with addSource() before using this function. 1450 1450 void start(Node dest) { 1451 while ( !emptyQueue() && _digraph>target(_stack[_stack_head]) != dest ) 1452 1453 } 1454 1451 while ( !emptyQueue() && _digraph>target(_stack[_stack_head]) != dest ) 1452 processNextArc(); 1453 } 1454 1455 1455 /// \brief Executes the algorithm until a condition is met. 1456 1456 /// … … 1491 1491 1492 1492 /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph. 1493 1493 1494 1494 /// This method runs the %DFS algorithm in order to 1495 1495 /// compute the %DFS path to each node. The algorithm computes
Note: See TracChangeset
for help on using the changeset viewer.