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

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bfs.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 … … 34 34 35 35 36 36 37 37 ///Default traits class of Bfs class. 38 38 … … 42 42 struct BfsDefaultTraits 43 43 { 44 ///The digraph type the algorithm runs on. 44 ///The digraph type the algorithm runs on. 45 45 typedef GR Digraph; 46 46 ///\brief The type of the map that stores the last 47 47 ///arcs of the shortest paths. 48 /// 48 /// 49 49 ///The type of the map that stores the last 50 50 ///arcs of the shortest paths. … … 53 53 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; 54 54 ///Instantiates a PredMap. 55 56 ///This function instantiates a \ref PredMap. 55 56 ///This function instantiates a \ref PredMap. 57 57 ///\param G is the digraph, to which we would like to define the PredMap. 58 58 ///\todo The digraph alone may be insufficient to initialize 59 static PredMap *createPredMap(const GR &G) 59 static PredMap *createPredMap(const GR &G) 60 60 { 61 61 return new PredMap(G); 62 62 } 63 63 ///The type of the map that indicates which nodes are processed. 64 64 65 65 ///The type of the map that indicates which nodes are processed. 66 66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 68 68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 69 69 ///Instantiates a ProcessedMap. 70 71 ///This function instantiates a \ref ProcessedMap. 70 71 ///This function instantiates a \ref ProcessedMap. 72 72 ///\param g is the digraph, to which 73 73 ///we would like to define the \ref ProcessedMap … … 81 81 } 82 82 ///The type of the map that indicates which nodes are reached. 83 83 84 84 ///The type of the map that indicates which nodes are reached. 85 85 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 87 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 88 88 ///Instantiates a ReachedMap. 89 90 ///This function instantiates a \ref ReachedMap. 89 90 ///This function instantiates a \ref ReachedMap. 91 91 ///\param G is the digraph, to which 92 92 ///we would like to define the \ref ReachedMap. … … 96 96 } 97 97 ///The type of the map that stores the dists of the nodes. 98 98 99 99 ///The type of the map that stores the dists of the nodes. 100 100 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 102 102 typedef typename Digraph::template NodeMap<int> DistMap; 103 103 ///Instantiates a DistMap. 104 105 ///This function instantiates a \ref DistMap. 104 105 ///This function instantiates a \ref DistMap. 106 106 ///\param G is the digraph, to which we would like to define the \ref DistMap 107 107 static DistMap *createDistMap(const GR &G) … … 110 110 } 111 111 }; 112 112 113 113 ///%BFS algorithm class. 114 114 115 115 ///\ingroup search 116 116 ///This class provides an efficient implementation of the %BFS algorithm. … … 127 127 #ifdef DOXYGEN 128 128 template <typename GR, 129 129 typename TR> 130 130 #else 131 131 template <typename GR=ListDigraph, 132 132 typename TR=BfsDefaultTraits<GR> > 133 133 #endif 134 134 class Bfs { … … 143 143 public: 144 144 virtual const char* what() const throw() { 145 145 return "lemon::Bfs::UninitializedParameter"; 146 146 } 147 147 }; … … 150 150 ///The type of the underlying digraph. 151 151 typedef typename TR::Digraph Digraph; 152 152 153 153 ///\brief The type of the map that stores the last 154 154 ///arcs of the shortest paths. … … 191 191 192 192 ///Creates the maps if necessary. 193 193 194 194 ///\todo Better memory allocation (instead of new). 195 void create_maps() 195 void create_maps() 196 196 { 197 197 if(!_pred) { 198 199 198 local_pred = true; 199 _pred = Traits::createPredMap(*G); 200 200 } 201 201 if(!_dist) { 202 203 202 local_dist = true; 203 _dist = Traits::createDistMap(*G); 204 204 } 205 205 if(!_reached) { 206 207 206 local_reached = true; 207 _reached = Traits::createReachedMap(*G); 208 208 } 209 209 if(!_processed) { 210 211 210 local_processed = true; 211 _processed = Traits::createProcessedMap(*G); 212 212 } 213 213 } 214 214 215 215 protected: 216 216 217 217 Bfs() {} 218 218 219 219 public: 220 220 221 221 typedef Bfs Create; 222 222 … … 228 228 struct DefPredMapTraits : public Traits { 229 229 typedef T PredMap; 230 static PredMap *createPredMap(const Digraph &) 230 static PredMap *createPredMap(const Digraph &) 231 231 { 232 232 throw UninitializedParameter(); 233 233 } 234 234 }; … … 239 239 /// 240 240 template <class T> 241 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > { 241 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > { 242 242 typedef Bfs< Digraph, DefPredMapTraits<T> > Create; 243 243 }; 244 244 245 245 template <class T> 246 246 struct DefDistMapTraits : public Traits { 247 247 typedef T DistMap; 248 static DistMap *createDistMap(const Digraph &) 248 static DistMap *createDistMap(const Digraph &) 249 249 { 250 250 throw UninitializedParameter(); 251 251 } 252 252 }; … … 257 257 /// 258 258 template <class T> 259 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > { 259 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > { 260 260 typedef Bfs< Digraph, DefDistMapTraits<T> > Create; 261 261 }; 262 262 263 263 template <class T> 264 264 struct DefReachedMapTraits : public Traits { 265 265 typedef T ReachedMap; 266 static ReachedMap *createReachedMap(const Digraph &) 266 static ReachedMap *createReachedMap(const Digraph &) 267 267 { 268 268 throw UninitializedParameter(); 269 269 } 270 270 }; … … 275 275 /// 276 276 template <class T> 277 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > { 277 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > { 278 278 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create; 279 279 }; 280 280 281 281 template <class T> 282 282 struct DefProcessedMapTraits : public Traits { 283 283 typedef T ProcessedMap; 284 static ProcessedMap *createProcessedMap(const Digraph &) 284 static ProcessedMap *createProcessedMap(const Digraph &) 285 285 { 286 286 throw UninitializedParameter(); 287 287 } 288 288 }; … … 296 296 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create; 297 297 }; 298 298 299 299 struct DefDigraphProcessedMapTraits : public Traits { 300 300 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 301 static ProcessedMap *createProcessedMap(const Digraph &G) 301 static ProcessedMap *createProcessedMap(const Digraph &G) 302 302 { 303 303 return new ProcessedMap(G); 304 304 } 305 305 }; … … 312 312 template <class T> 313 313 struct DefProcessedMapToBeDefaultMap : 314 public Bfs< Digraph, DefDigraphProcessedMapTraits> { 314 public Bfs< Digraph, DefDigraphProcessedMapTraits> { 315 315 typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create; 316 316 }; 317 317 318 318 ///@} 319 319 320 public: 321 320 public: 321 322 322 ///Constructor. 323 323 324 324 ///\param _G the digraph the algorithm will run on. 325 325 /// … … 331 331 _processed(NULL), local_processed(false) 332 332 { } 333 333 334 334 ///Destructor. 335 ~Bfs() 335 ~Bfs() 336 336 { 337 337 if(local_pred) delete _pred; … … 348 348 ///automatically allocated map, of course. 349 349 ///\return <tt> (*this) </tt> 350 Bfs &predMap(PredMap &m) 350 Bfs &predMap(PredMap &m) 351 351 { 352 352 if(local_pred) { 353 354 353 delete _pred; 354 local_pred=false; 355 355 } 356 356 _pred = &m; … … 365 365 ///automatically allocated map, of course. 366 366 ///\return <tt> (*this) </tt> 367 Bfs &reachedMap(ReachedMap &m) 367 Bfs &reachedMap(ReachedMap &m) 368 368 { 369 369 if(local_reached) { 370 371 370 delete _reached; 371 local_reached=false; 372 372 } 373 373 _reached = &m; … … 382 382 ///automatically allocated map, of course. 383 383 ///\return <tt> (*this) </tt> 384 Bfs &processedMap(ProcessedMap &m) 384 Bfs &processedMap(ProcessedMap &m) 385 385 { 386 386 if(local_processed) { 387 388 387 delete _processed; 388 local_processed=false; 389 389 } 390 390 _processed = &m; … … 399 399 ///automatically allocated map, of course. 400 400 ///\return <tt> (*this) </tt> 401 Bfs &distMap(DistMap &m) 401 Bfs &distMap(DistMap &m) 402 402 { 403 403 if(local_dist) { 404 405 404 delete _dist; 405 local_dist=false; 406 406 } 407 407 _dist = &m; … … 433 433 _curr_dist=1; 434 434 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 435 436 437 438 } 439 } 440 435 _pred>set(u,INVALID); 436 _reached>set(u,false); 437 _processed>set(u,false); 438 } 439 } 440 441 441 ///Adds a new source node. 442 442 … … 446 446 { 447 447 if(!(*_reached)[s]) 448 449 450 451 452 453 454 455 } 456 448 { 449 _reached>set(s,true); 450 _pred>set(s,INVALID); 451 _dist>set(s,0); 452 _queue[_queue_head++]=s; 453 _queue_next_dist=_queue_head; 454 } 455 } 456 457 457 ///Processes the next node. 458 458 … … 465 465 { 466 466 if(_queue_tail==_queue_next_dist) { 467 468 467 _curr_dist++; 468 _queue_next_dist=_queue_head; 469 469 } 470 470 Node n=_queue[_queue_tail++]; … … 472 472 Node m; 473 473 for(OutArcIt e(*G,n);e!=INVALID;++e) 474 475 476 477 478 479 474 if(!(*_reached)[m=G>target(e)]) { 475 _queue[_queue_head++]=m; 476 _reached>set(m,true); 477 _pred>set(m,e); 478 _dist>set(m,_curr_dist); 479 } 480 480 return n; 481 481 } … … 496 496 { 497 497 if(_queue_tail==_queue_next_dist) { 498 499 498 _curr_dist++; 499 _queue_next_dist=_queue_head; 500 500 } 501 501 Node n=_queue[_queue_tail++]; … … 503 503 Node m; 504 504 for(OutArcIt e(*G,n);e!=INVALID;++e) 505 506 507 508 509 505 if(!(*_reached)[m=G>target(e)]) { 506 _queue[_queue_head++]=m; 507 _reached>set(m,true); 508 _pred>set(m,e); 509 _dist>set(m,_curr_dist); 510 510 reach = reach  (target == m); 511 511 } 512 512 return n; 513 513 } … … 529 529 { 530 530 if(_queue_tail==_queue_next_dist) { 531 532 531 _curr_dist++; 532 _queue_next_dist=_queue_head; 533 533 } 534 534 Node n=_queue[_queue_tail++]; … … 536 536 Node m; 537 537 for(OutArcIt e(*G,n);e!=INVALID;++e) 538 539 540 541 542 543 544 538 if(!(*_reached)[m=G>target(e)]) { 539 _queue[_queue_head++]=m; 540 _reached>set(m,true); 541 _pred>set(m,e); 542 _dist>set(m,_curr_dist); 543 if (nm[m] && rnode == INVALID) rnode = m; 544 } 545 545 return n; 546 546 } 547 547 548 548 ///Next node to be processed. 549 549 … … 553 553 /// empty. 554 554 Node nextNode() 555 { 555 { 556 556 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; 557 557 } 558 558 559 559 ///\brief Returns \c false if there are nodes 560 560 ///to be processed in the queue … … 564 564 bool emptyQueue() { return _queue_tail==_queue_head; } 565 565 ///Returns the number of the nodes to be processed. 566 566 567 567 ///Returns the number of the nodes to be processed in the queue. 568 568 int queueSize() { return _queue_head_queue_tail; } 569 569 570 570 ///Executes the algorithm. 571 571 … … 585 585 while ( !emptyQueue() ) processNextNode(); 586 586 } 587 587 588 588 ///Executes the algorithm until \c dest is reached. 589 589 … … 603 603 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); 604 604 } 605 605 606 606 ///Executes the algorithm until a condition is met. 607 607 … … 622 622 Node rnode = INVALID; 623 623 while ( !emptyQueue() && rnode == INVALID ) { 624 624 processNextNode(nm, rnode); 625 625 } 626 626 return rnode; 627 627 } 628 628 629 629 ///Runs %BFS algorithm from node \c s. 630 630 631 631 ///This method runs the %BFS algorithm from a root node \c s 632 632 ///in order to … … 647 647 start(); 648 648 } 649 649 650 650 ///Finds the shortest path between \c s and \c t. 651 651 652 652 ///Finds the shortest path between \c s and \c t. 653 653 /// … … 667 667 return reached(t) ? _curr_dist : 0; 668 668 } 669 669 670 670 ///@} 671 671 … … 675 675 ///Before the use of these functions, 676 676 ///either run() or start() must be calleb. 677 677 678 678 ///@{ 679 679 … … 681 681 682 682 ///Gives back the shortest path. 683 683 684 684 ///Gives back the shortest path. 685 685 ///\pre The \c t should be reachable from the source. 686 Path path(Node t) 686 Path path(Node t) 687 687 { 688 688 return Path(*G, *_pred, t); … … 723 723 ///using this function. 724 724 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 725 726 725 G>source((*_pred)[v]); } 726 727 727 ///Returns a reference to the NodeMap of distances. 728 728 … … 731 731 ///be called before using this function. 732 732 const DistMap &distMap() const { return *_dist;} 733 733 734 734 ///Returns a reference to the shortest path tree map. 735 735 … … 739 739 ///must be called before using this function. 740 740 const PredMap &predMap() const { return *_pred;} 741 741 742 742 ///Checks if a node is reachable from the root. 743 743 … … 748 748 /// 749 749 bool reached(Node v) { return (*_reached)[v]; } 750 750 751 751 ///@} 752 752 }; … … 759 759 struct BfsWizardDefaultTraits 760 760 { 761 ///The digraph type the algorithm runs on. 761 ///The digraph type the algorithm runs on. 762 762 typedef GR Digraph; 763 763 ///\brief The type of the map that stores the last 764 764 ///arcs of the shortest paths. 765 /// 765 /// 766 766 ///The type of the map that stores the last 767 767 ///arcs of the shortest paths. … … 770 770 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; 771 771 ///Instantiates a PredMap. 772 773 ///This function instantiates a \ref PredMap. 772 773 ///This function instantiates a \ref PredMap. 774 774 ///\param g is the digraph, to which we would like to define the PredMap. 775 775 ///\todo The digraph alone may be insufficient to initialize 776 776 #ifdef DOXYGEN 777 static PredMap *createPredMap(const GR &g) 777 static PredMap *createPredMap(const GR &g) 778 778 #else 779 static PredMap *createPredMap(const GR &) 779 static PredMap *createPredMap(const GR &) 780 780 #endif 781 781 { … … 784 784 785 785 ///The type of the map that indicates which nodes are processed. 786 786 787 787 ///The type of the map that indicates which nodes are processed. 788 788 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 790 790 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 791 791 ///Instantiates a ProcessedMap. 792 793 ///This function instantiates a \ref ProcessedMap. 792 793 ///This function instantiates a \ref ProcessedMap. 794 794 ///\param g is the digraph, to which 795 795 ///we would like to define the \ref ProcessedMap … … 803 803 } 804 804 ///The type of the map that indicates which nodes are reached. 805 805 806 806 ///The type of the map that indicates which nodes are reached. 807 807 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 809 809 typedef typename Digraph::template NodeMap<bool> ReachedMap; 810 810 ///Instantiates a ReachedMap. 811 812 ///This function instantiates a \ref ReachedMap. 811 812 ///This function instantiates a \ref ReachedMap. 813 813 ///\param G is the digraph, to which 814 814 ///we would like to define the \ref ReachedMap. … … 818 818 } 819 819 ///The type of the map that stores the dists of the nodes. 820 820 821 821 ///The type of the map that stores the dists of the nodes. 822 822 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 824 824 typedef NullMap<typename Digraph::Node,int> DistMap; 825 825 ///Instantiates a DistMap. 826 827 ///This function instantiates a \ref DistMap. 826 827 ///This function instantiates a \ref DistMap. 828 828 ///\param g is the digraph, to which we would like to define the \ref DistMap 829 829 #ifdef DOXYGEN … … 836 836 } 837 837 }; 838 838 839 839 /// Default traits used by \ref BfsWizard 840 840 … … 866 866 ///Pointer to the source node. 867 867 Node _source; 868 868 869 869 public: 870 870 /// Constructor. 871 871 872 872 /// This constructor does not require parameters, therefore it initiates 873 873 /// all of the attributes to default values (0, INVALID). 874 874 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 875 875 _dist(0), _source(INVALID) {} 876 876 877 877 /// Constructor. 878 878 879 879 /// This constructor requires some parameters, 880 880 /// listed in the parameters list. … … 883 883 /// \param s is the initial value of \ref _source 884 884 BfsWizardBase(const GR &g, Node s=INVALID) : 885 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 885 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 886 886 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} 887 887 888 888 }; 889 889 890 890 /// A class to make the usage of Bfs algorithm easier 891 891 … … 922 922 //\e 923 923 typedef typename Digraph::OutArcIt OutArcIt; 924 924 925 925 ///\brief The type of the map that stores 926 926 ///the reached nodes … … 952 952 953 953 ///Runs Bfs algorithm from a given node. 954 954 955 955 ///Runs Bfs algorithm from a given node. 956 956 ///The node can be given by the \ref source function. … … 960 960 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 961 961 if(Base::_reached) 962 963 if(Base::_processed) 962 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 963 if(Base::_processed) 964 964 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 965 if(Base::_pred) 965 if(Base::_pred) 966 966 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 967 if(Base::_dist) 967 if(Base::_dist) 968 968 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 969 969 alg.run(Base::_source); … … 986 986 DefPredMapBase(const TR &b) : TR(b) {} 987 987 }; 988 988 989 989 ///\brief \ref namedtemplparam "Named parameter" 990 990 ///function for setting PredMap … … 994 994 /// 995 995 template<class T> 996 BfsWizard<DefPredMapBase<T> > predMap(const T &t) 996 BfsWizard<DefPredMapBase<T> > predMap(const T &t) 997 997 { 998 998 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 999 999 return BfsWizard<DefPredMapBase<T> >(*this); 1000 1000 } 1001 1002 1001 1002 1003 1003 template<class T> 1004 1004 struct DefReachedMapBase : public Base { … … 1007 1007 DefReachedMapBase(const TR &b) : TR(b) {} 1008 1008 }; 1009 1009 1010 1010 ///\brief \ref namedtemplparam "Named parameter" 1011 1011 ///function for setting ReachedMap … … 1015 1015 /// 1016 1016 template<class T> 1017 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 1017 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 1018 1018 { 1019 1019 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1020 1020 return BfsWizard<DefReachedMapBase<T> >(*this); 1021 1021 } 1022 1022 1023 1023 1024 1024 template<class T> … … 1028 1028 DefProcessedMapBase(const TR &b) : TR(b) {} 1029 1029 }; 1030 1030 1031 1031 ///\brief \ref namedtemplparam "Named parameter" 1032 1032 ///function for setting ProcessedMap … … 1036 1036 /// 1037 1037 template<class T> 1038 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 1038 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 1039 1039 { 1040 1040 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); 1041 1041 return BfsWizard<DefProcessedMapBase<T> >(*this); 1042 1042 } 1043 1044 1043 1044 1045 1045 template<class T> 1046 1046 struct DefDistMapBase : public Base { … … 1049 1049 DefDistMapBase(const TR &b) : TR(b) {} 1050 1050 }; 1051 1051 1052 1052 ///\brief \ref namedtemplparam "Named parameter" 1053 1053 ///function for setting DistMap type … … 1057 1057 /// 1058 1058 template<class T> 1059 BfsWizard<DefDistMapBase<T> > distMap(const T &t) 1059 BfsWizard<DefDistMapBase<T> > distMap(const T &t) 1060 1060 { 1061 1061 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1062 1062 return BfsWizard<DefDistMapBase<T> >(*this); 1063 1063 } 1064 1064 1065 1065 /// Sets the source node, from which the Bfs algorithm runs. 1066 1066 1067 1067 /// Sets the source node, from which the Bfs algorithm runs. 1068 1068 /// \param s is the source node. 1069 BfsWizard<TR> &source(Node s) 1069 BfsWizard<TR> &source(Node s) 1070 1070 { 1071 1071 Base::_source=s; 1072 1072 return *this; 1073 1073 } 1074 1074 1075 1075 }; 1076 1076 1077 1077 ///Function type interface for Bfs algorithm. 1078 1078 … … 1101 1101 #ifdef DOXYGEN 1102 1102 /// \brief Visitor class for bfs. 1103 /// 1103 /// 1104 1104 /// This class defines the interface of the BfsVisit events, and 1105 1105 /// it could be the base of a real Visitor class. … … 1110 1110 typedef typename Digraph::Node Node; 1111 1111 /// \brief Called when the arc reach a node. 1112 /// 1112 /// 1113 1113 /// It is called when the bfs find an arc which target is not 1114 1114 /// reached yet. 1115 1115 void discover(const Arc& arc) {} 1116 1116 /// \brief Called when the node reached first time. 1117 /// 1117 /// 1118 1118 /// It is Called when the node reached first time. 1119 1119 void reach(const Node& node) {} 1120 /// \brief Called when the arc examined but target of the arc 1120 /// \brief Called when the arc examined but target of the arc 1121 1121 /// already discovered. 1122 /// 1123 /// It called when the arc examined but the target of the arc 1122 /// 1123 /// It called when the arc examined but the target of the arc 1124 1124 /// already discovered. 1125 1125 void examine(const Arc& arc) {} 1126 1126 /// \brief Called for the source node of the bfs. 1127 /// 1127 /// 1128 1128 /// It is called for the source node of the bfs. 1129 1129 void start(const Node& node) {} 1130 1130 /// \brief Called when the node processed. 1131 /// 1131 /// 1132 1132 /// It is Called when the node processed. 1133 1133 void process(const Node& node) {} … … 1148 1148 struct Constraints { 1149 1149 void constraints() { 1150 1151 1152 1153 1154 1155 1150 Arc arc; 1151 Node node; 1152 visitor.discover(arc); 1153 visitor.reach(node); 1154 visitor.examine(arc); 1155 visitor.start(node); 1156 1156 visitor.process(node); 1157 1157 } … … 1168 1168 struct BfsVisitDefaultTraits { 1169 1169 1170 /// \brief The digraph type the algorithm runs on. 1170 /// \brief The digraph type the algorithm runs on. 1171 1171 typedef _Digraph Digraph; 1172 1172 1173 1173 /// \brief The type of the map that indicates which nodes are reached. 1174 /// 1174 /// 1175 1175 /// The type of the map that indicates which nodes are reached. 1176 1176 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 1180 1180 /// \brief Instantiates a ReachedMap. 1181 1181 /// 1182 /// This function instantiates a \ref ReachedMap. 1182 /// This function instantiates a \ref ReachedMap. 1183 1183 /// \param digraph is the digraph, to which 1184 1184 /// we would like to define the \ref ReachedMap. … … 1190 1190 1191 1191 /// \ingroup search 1192 /// 1192 /// 1193 1193 /// \brief %BFS Visit algorithm class. 1194 /// 1194 /// 1195 1195 /// This class provides an efficient implementation of the %BFS algorithm 1196 1196 /// with visitor interface. … … 1198 1198 /// The %BfsVisit class provides an alternative interface to the Bfs 1199 1199 /// class. It works with callback mechanism, the BfsVisit object calls 1200 /// on every bfs event the \c Visitor class member functions. 1200 /// on every bfs event the \c Visitor class member functions. 1201 1201 /// 1202 1202 /// \tparam _Digraph The digraph type the algorithm runs on. The default value is 1203 1203 /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it 1204 1204 /// is only passed to \ref BfsDefaultTraits. 1205 /// \tparam _Visitor The Visitor object for the algorithm. The 1205 /// \tparam _Visitor The Visitor object for the algorithm. The 1206 1206 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which 1207 1207 /// does not observe the Bfs events. If you want to observe the bfs 1208 1208 /// events you should implement your own Visitor class. 1209 /// \tparam _Traits Traits class to set various data types used by the 1209 /// \tparam _Traits Traits class to set various data types used by the 1210 1210 /// algorithm. The default traits class is 1211 1211 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". … … 1216 1216 #else 1217 1217 template <typename _Digraph = ListDigraph, 1218 1219 1218 typename _Visitor = BfsVisitor<_Digraph>, 1219 typename _Traits = BfsDefaultTraits<_Digraph> > 1220 1220 #endif 1221 1221 class BfsVisit { 1222 1222 public: 1223 1223 1224 1224 /// \brief \ref Exception for uninitialized parameters. 1225 1225 /// … … 1228 1228 class UninitializedParameter : public lemon::UninitializedParameter { 1229 1229 public: 1230 virtual const char* what() const throw() 1230 virtual const char* what() const throw() 1231 1231 { 1232 1232 return "lemon::BfsVisit::UninitializedParameter"; 1233 1233 } 1234 1234 }; … … 1267 1267 void create_maps() { 1268 1268 if(!_reached) { 1269 1270 1269 local_reached = true; 1270 _reached = Traits::createReachedMap(*_digraph); 1271 1271 } 1272 1272 } … … 1275 1275 1276 1276 BfsVisit() {} 1277 1277 1278 1278 public: 1279 1279 … … 1287 1287 typedef T ReachedMap; 1288 1288 static ReachedMap *createReachedMap(const Digraph &digraph) { 1289 1290 } 1291 }; 1292 /// \brief \ref namedtemplparam "Named parameter" for setting 1289 throw UninitializedParameter(); 1290 } 1291 }; 1292 /// \brief \ref namedtemplparam "Named parameter" for setting 1293 1293 /// ReachedMap type 1294 1294 /// … … 1296 1296 template <class T> 1297 1297 struct DefReachedMap : public BfsVisit< Digraph, Visitor, 1298 1298 DefReachedMapTraits<T> > { 1299 1299 typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create; 1300 1300 }; 1301 1301 ///@} 1302 1302 1303 public: 1304 1303 public: 1304 1305 1305 /// \brief Constructor. 1306 1306 /// … … 1310 1310 /// \param visitor The visitor of the algorithm. 1311 1311 /// 1312 BfsVisit(const Digraph& digraph, Visitor& visitor) 1312 BfsVisit(const Digraph& digraph, Visitor& visitor) 1313 1313 : _digraph(&digraph), _visitor(&visitor), 1314 1315 1314 _reached(0), local_reached(false) {} 1315 1316 1316 /// \brief Destructor. 1317 1317 /// … … 1330 1330 BfsVisit &reachedMap(ReachedMap &m) { 1331 1331 if(local_reached) { 1332 1333 1332 delete _reached; 1333 local_reached = false; 1334 1334 } 1335 1335 _reached = &m; … … 1358 1358 _list_front = _list_back = 1; 1359 1359 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { 1360 1361 } 1362 } 1363 1360 _reached>set(u, false); 1361 } 1362 } 1363 1364 1364 /// \brief Adds a new source node. 1365 1365 /// … … 1367 1367 void addSource(Node s) { 1368 1368 if(!(*_reached)[s]) { 1369 1370 1371 1369 _reached>set(s,true); 1370 _visitor>start(s); 1371 _visitor>reach(s); 1372 1372 _list[++_list_back] = s; 1373 1374 } 1375 1373 } 1374 } 1375 1376 1376 /// \brief Processes the next node. 1377 1377 /// … … 1381 1381 /// 1382 1382 /// \pre The queue must not be empty! 1383 Node processNextNode() { 1383 Node processNextNode() { 1384 1384 Node n = _list[++_list_front]; 1385 1385 _visitor>process(n); … … 1468 1468 /// \return The next node to be processed or INVALID if the stack is 1469 1469 /// empty. 1470 Node nextNode() { 1470 Node nextNode() { 1471 1471 return _list_front != _list_back ? _list[_list_front + 1] : INVALID; 1472 1472 } … … 1483 1483 /// Returns the number of the nodes to be processed in the queue. 1484 1484 int queueSize() { return _list_back  _list_front; } 1485 1485 1486 1486 /// \brief Executes the algorithm. 1487 1487 /// … … 1493 1493 while ( !emptyQueue() ) processNextNode(); 1494 1494 } 1495 1495 1496 1496 /// \brief Executes the algorithm until \c dest is reached. 1497 1497 /// … … 1504 1504 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); 1505 1505 } 1506 1506 1507 1507 /// \brief Executes the algorithm until a condition is met. 1508 1508 /// … … 1522 1522 Node rnode = INVALID; 1523 1523 while ( !emptyQueue() && rnode == INVALID ) { 1524 1524 processNextNode(nm, rnode); 1525 1525 } 1526 1526 return rnode; … … 1543 1543 1544 1544 /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph. 1545 /// 1545 /// 1546 1546 /// This method runs the %BFS algorithm in order to 1547 1547 /// compute the %BFS path to each node. The algorithm computes
Note: See TracChangeset
for help on using the changeset viewer.