Changes in lemon/bfs.h [301:9db8964f0cf6:956:141f9c0db4a3] in lemon
- File:
-
- 1 edited
-
lemon/bfs.h (modified) (51 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r301 r956 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the shortest paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 ///Instantiates a PredMap.53 54 ///This function instantiates a PredMap.52 ///Instantiates a \c PredMap. 53 54 ///This function instantiates a \ref PredMap. 55 55 ///\param g is the digraph, to which we would like to define the 56 /// PredMap.56 ///\ref PredMap. 57 57 static PredMap *createPredMap(const Digraph &g) 58 58 { … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default, it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 ///Instantiates a ProcessedMap.68 69 ///This function instantiates a ProcessedMap.68 ///Instantiates a \c ProcessedMap. 69 70 ///This function instantiates a \ref ProcessedMap. 70 71 ///\param g is the digraph, to which 71 ///we would like to define the ProcessedMap72 ///we would like to define the \ref ProcessedMap 72 73 #ifdef DOXYGEN 73 74 static ProcessedMap *createProcessedMap(const Digraph &g) … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 ///It must conform to 86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 ///Instantiates a ReachedMap.87 88 ///This function instantiates a ReachedMap.88 ///Instantiates a \c ReachedMap. 89 90 ///This function instantiates a \ref ReachedMap. 89 91 ///\param g is the digraph, to which 90 ///we would like to define the ReachedMap.92 ///we would like to define the \ref ReachedMap. 91 93 static ReachedMap *createReachedMap(const Digraph &g) 92 94 { … … 97 99 98 100 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.101 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 102 typedef typename Digraph::template NodeMap<int> DistMap; 101 ///Instantiates a DistMap.102 103 ///This function instantiates a DistMap.103 ///Instantiates a \c DistMap. 104 105 ///This function instantiates a \ref DistMap. 104 106 ///\param g is the digraph, to which we would like to define the 105 /// DistMap.107 ///\ref DistMap. 106 108 static DistMap *createDistMap(const Digraph &g) 107 109 { … … 120 122 /// 121 123 ///\tparam GR The type of the digraph the algorithm runs on. 122 ///The default value is \ref ListDigraph. The value of GR is not used 123 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits. 124 ///\tparam TR Traits class to set various data types used by the algorithm. 125 ///The default traits class is 126 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>". 127 ///See \ref BfsDefaultTraits for the documentation of 128 ///a Bfs traits class. 124 ///The default type is \ref ListDigraph. 125 ///\tparam TR The traits class that defines various types used by the 126 ///algorithm. By default, it is \ref BfsDefaultTraits 127 ///"BfsDefaultTraits<GR>". 128 ///In most cases, this parameter should not be set directly, 129 ///consider to use the named template parameters instead. 129 130 #ifdef DOXYGEN 130 131 template <typename GR, … … 152 153 typedef PredMapPath<Digraph, PredMap> Path; 153 154 154 ///The traits class.155 ///The \ref BfsDefaultTraits "traits class" of the algorithm. 155 156 typedef TR Traits; 156 157 … … 214 215 typedef Bfs Create; 215 216 216 ///\name Named template parameters217 ///\name Named Template Parameters 217 218 218 219 ///@{ … … 228 229 }; 229 230 ///\brief \ref named-templ-param "Named parameter" for setting 230 /// PredMap type.231 ///\c PredMap type. 231 232 /// 232 233 ///\ref named-templ-param "Named parameter" for setting 233 ///PredMap type. 234 ///\c PredMap type. 235 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 234 236 template <class T> 235 237 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 247 249 }; 248 250 ///\brief \ref named-templ-param "Named parameter" for setting 249 /// DistMap type.251 ///\c DistMap type. 250 252 /// 251 253 ///\ref named-templ-param "Named parameter" for setting 252 ///DistMap type. 254 ///\c DistMap type. 255 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 253 256 template <class T> 254 257 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 269 }; 267 270 ///\brief \ref named-templ-param "Named parameter" for setting 268 /// ReachedMap type.271 ///\c ReachedMap type. 269 272 /// 270 273 ///\ref named-templ-param "Named parameter" for setting 271 ///ReachedMap type. 274 ///\c ReachedMap type. 275 ///It must conform to 276 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 272 277 template <class T> 273 278 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 285 290 }; 286 291 ///\brief \ref named-templ-param "Named parameter" for setting 287 /// ProcessedMap type.292 ///\c ProcessedMap type. 288 293 /// 289 294 ///\ref named-templ-param "Named parameter" for setting 290 ///ProcessedMap type. 295 ///\c ProcessedMap type. 296 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 291 297 template <class T> 292 298 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 303 309 }; 304 310 ///\brief \ref named-templ-param "Named parameter" for setting 305 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.311 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 306 312 /// 307 313 ///\ref named-templ-param "Named parameter" for setting 308 /// ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.314 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 309 315 ///If you don't set it explicitly, it will be automatically allocated. 310 316 struct SetStandardProcessedMap : … … 341 347 342 348 ///Sets the map that stores the predecessor arcs. 343 ///If you don't use this function before calling \ref run(), 344 ///it will allocate one. The destructor deallocates this 345 ///automatically allocated map, of course. 349 ///If you don't use this function before calling \ref run(Node) "run()" 350 ///or \ref init(), an instance will be allocated automatically. 351 ///The destructor deallocates this automatically allocated map, 352 ///of course. 346 353 ///\return <tt> (*this) </tt> 347 354 Bfs &predMap(PredMap &m) … … 358 365 359 366 ///Sets the map that indicates which nodes are reached. 360 ///If you don't use this function before calling \ref run(), 361 ///it will allocate one. The destructor deallocates this 362 ///automatically allocated map, of course. 367 ///If you don't use this function before calling \ref run(Node) "run()" 368 ///or \ref init(), an instance will be allocated automatically. 369 ///The destructor deallocates this automatically allocated map, 370 ///of course. 363 371 ///\return <tt> (*this) </tt> 364 372 Bfs &reachedMap(ReachedMap &m) … … 375 383 376 384 ///Sets the map that indicates which nodes are processed. 377 ///If you don't use this function before calling \ref run(), 378 ///it will allocate one. The destructor deallocates this 379 ///automatically allocated map, of course. 385 ///If you don't use this function before calling \ref run(Node) "run()" 386 ///or \ref init(), an instance will be allocated automatically. 387 ///The destructor deallocates this automatically allocated map, 388 ///of course. 380 389 ///\return <tt> (*this) </tt> 381 390 Bfs &processedMap(ProcessedMap &m) … … 393 402 ///Sets the map that stores the distances of the nodes calculated by 394 403 ///the algorithm. 395 ///If you don't use this function before calling \ref run(), 396 ///it will allocate one. The destructor deallocates this 397 ///automatically allocated map, of course. 404 ///If you don't use this function before calling \ref run(Node) "run()" 405 ///or \ref init(), an instance will be allocated automatically. 406 ///The destructor deallocates this automatically allocated map, 407 ///of course. 398 408 ///\return <tt> (*this) </tt> 399 409 Bfs &distMap(DistMap &m) … … 409 419 public: 410 420 411 ///\name Execution control 412 ///The simplest way to execute the algorithm is to use 413 ///one of the member functions called \ref lemon::Bfs::run() "run()". 414 ///\n 415 ///If you need more control on the execution, first you must call 416 ///\ref lemon::Bfs::init() "init()", then you can add several source 417 ///nodes with \ref lemon::Bfs::addSource() "addSource()". 418 ///Finally \ref lemon::Bfs::start() "start()" will perform the 419 ///actual path computation. 421 ///\name Execution Control 422 ///The simplest way to execute the BFS algorithm is to use one of the 423 ///member functions called \ref run(Node) "run()".\n 424 ///If you need better control on the execution, you have to call 425 ///\ref init() first, then you can add several source nodes with 426 ///\ref addSource(). Finally the actual path computation can be 427 ///performed with one of the \ref start() functions. 420 428 421 429 ///@{ 422 430 431 ///\brief Initializes the internal data structures. 432 /// 423 433 ///Initializes the internal data structures. 424 425 ///Initializes the internal data structures.426 ///427 434 void init() 428 435 { … … 558 565 } 559 566 560 ///\brief Returns \c false if there are nodes 561 ///to be processed. 562 /// 563 ///Returns \c false if there are nodes 564 ///to be processed in the queue. 567 ///Returns \c false if there are nodes to be processed. 568 569 ///Returns \c false if there are nodes to be processed 570 ///in the queue. 565 571 bool emptyQueue() const { return _queue_tail==_queue_head; } 566 572 567 573 ///Returns the number of the nodes to be processed. 568 574 569 ///Returns the number of the nodes to be processed in the queue. 575 ///Returns the number of the nodes to be processed 576 ///in the queue. 570 577 int queueSize() const { return _queue_head-_queue_tail; } 571 578 … … 702 709 ///Runs the algorithm to visit all nodes in the digraph. 703 710 704 ///This method runs the %BFS algorithm in order to 705 ///compute the shortest path to each node. 706 /// 707 ///The algorithm computes 708 ///- the shortest path tree (forest), 709 ///- the distance of each node from the root(s). 711 ///This method runs the %BFS algorithm in order to visit all nodes 712 ///in the digraph. 710 713 /// 711 714 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 732 735 733 736 ///\name Query Functions 734 ///The result of the %BFS algorithm can be obtained using these737 ///The results of the BFS algorithm can be obtained using these 735 738 ///functions.\n 736 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()737 /// "start()" must be calledbefore using them.739 ///Either \ref run(Node) "run()" or \ref start() should be called 740 ///before using them. 738 741 739 742 ///@{ 740 743 741 ///The shortest path to anode.742 743 ///Returns the shortest path to a node.744 /// 745 ///\warning \c t should be reach ablefrom the root(s).746 /// 747 ///\pre Either \ref run( ) or \ref start() must be called before748 /// using this function.744 ///The shortest path to the given node. 745 746 ///Returns the shortest path to the given node from the root(s). 747 /// 748 ///\warning \c t should be reached from the root(s). 749 /// 750 ///\pre Either \ref run(Node) "run()" or \ref init() 751 ///must be called before using this function. 749 752 Path path(Node t) const { return Path(*G, *_pred, t); } 750 753 751 ///The distance of anode from the root(s).752 753 ///Returns the distance of anode from the root(s).754 /// 755 ///\warning If node \c v is not reach ablefrom the root(s), then754 ///The distance of the given node from the root(s). 755 756 ///Returns the distance of the given node from the root(s). 757 /// 758 ///\warning If node \c v is not reached from the root(s), then 756 759 ///the return value of this function is undefined. 757 760 /// 758 ///\pre Either \ref run( ) or \ref start() must be called before759 /// using this function.761 ///\pre Either \ref run(Node) "run()" or \ref init() 762 ///must be called before using this function. 760 763 int dist(Node v) const { return (*_dist)[v]; } 761 764 762 ///Returns the 'previous arc' of the shortest path tree for a node. 763 765 ///\brief Returns the 'previous arc' of the shortest path tree for 766 ///the given node. 767 /// 764 768 ///This function returns the 'previous arc' of the shortest path 765 769 ///tree for the node \c v, i.e. it returns the last arc of a 766 ///shortest path from the root(s)to \c v. It is \c INVALID if \c v767 ///is not reach ablefrom the root(s) or if \c v is a root.770 ///shortest path from a root to \c v. It is \c INVALID if \c v 771 ///is not reached from the root(s) or if \c v is a root. 768 772 /// 769 773 ///The shortest path tree used here is equal to the shortest path 770 ///tree used in \ref predNode() .771 /// 772 ///\pre Either \ref run( ) or \ref start() must be called before773 /// using this function.774 ///tree used in \ref predNode() and \ref predMap(). 775 /// 776 ///\pre Either \ref run(Node) "run()" or \ref init() 777 ///must be called before using this function. 774 778 Arc predArc(Node v) const { return (*_pred)[v];} 775 779 776 ///Returns the 'previous node' of the shortest path tree for a node. 777 780 ///\brief Returns the 'previous node' of the shortest path tree for 781 ///the given node. 782 /// 778 783 ///This function returns the 'previous node' of the shortest path 779 784 ///tree for the node \c v, i.e. it returns the last but one node 780 /// from a shortest path from the root(s)to \c v. It is \c INVALID781 ///if \c v is not reach ablefrom the root(s) or if \c v is a root.785 ///of a shortest path from a root to \c v. It is \c INVALID 786 ///if \c v is not reached from the root(s) or if \c v is a root. 782 787 /// 783 788 ///The shortest path tree used here is equal to the shortest path 784 ///tree used in \ref predArc() .785 /// 786 ///\pre Either \ref run( ) or \ref start() must be called before787 /// using this function.789 ///tree used in \ref predArc() and \ref predMap(). 790 /// 791 ///\pre Either \ref run(Node) "run()" or \ref init() 792 ///must be called before using this function. 788 793 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 789 794 G->source((*_pred)[v]); } … … 795 800 ///of the nodes calculated by the algorithm. 796 801 /// 797 ///\pre Either \ref run( )or \ref init()802 ///\pre Either \ref run(Node) "run()" or \ref init() 798 803 ///must be called before using this function. 799 804 const DistMap &distMap() const { return *_dist;} … … 803 808 /// 804 809 ///Returns a const reference to the node map that stores the predecessor 805 ///arcs, which form the shortest path tree .806 /// 807 ///\pre Either \ref run( )or \ref init()810 ///arcs, which form the shortest path tree (forest). 811 /// 812 ///\pre Either \ref run(Node) "run()" or \ref init() 808 813 ///must be called before using this function. 809 814 const PredMap &predMap() const { return *_pred;} 810 815 811 ///Checks if a node is reachable from the root(s). 812 813 ///Returns \c true if \c v is reachable from the root(s). 814 ///\pre Either \ref run() or \ref start() 816 ///Checks if the given node is reached from the root(s). 817 818 ///Returns \c true if \c v is reached from the root(s). 819 /// 820 ///\pre Either \ref run(Node) "run()" or \ref init() 815 821 ///must be called before using this function. 816 822 bool reached(Node v) const { return (*_reached)[v]; } … … 834 840 ///The type of the map that stores the predecessor 835 841 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.842 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 843 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 844 ///Instantiates a PredMap. … … 849 855 850 856 ///The type of the map that indicates which nodes are processed. 851 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.852 ///By default it is a NullMap.857 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 858 ///By default, it is a NullMap. 853 859 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 854 860 ///Instantiates a ProcessedMap. … … 869 875 870 876 ///The type of the map that indicates which nodes are reached. 871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 877 ///It must conform to 878 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 879 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 880 ///Instantiates a ReachedMap. … … 884 891 885 892 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.893 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 894 typedef typename Digraph::template NodeMap<int> DistMap; 888 895 ///Instantiates a DistMap. … … 899 906 900 907 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.908 ///It must conform to the \ref concepts::Path "Path" concept. 902 909 typedef lemon::Path<Digraph> Path; 903 910 }; … … 905 912 /// Default traits class used by BfsWizard 906 913 907 /// To make it easier to use Bfs algorithm 908 /// we have created a wizard class. 909 /// This \ref BfsWizard class needs default traits, 910 /// as well as the \ref Bfs class. 911 /// The \ref BfsWizardBase is a class to be the default traits of the 912 /// \ref BfsWizard class. 914 /// Default traits class used by BfsWizard. 915 /// \tparam GR The type of the digraph. 913 916 template<class GR> 914 917 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 941 /// Constructor. 939 942 940 /// This constructor does not require parameters, thereforeit initiates943 /// This constructor does not require parameters, it initiates 941 944 /// all of the attributes to \c 0. 942 945 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 958 961 /// This auxiliary class is created to implement the 959 962 /// \ref bfs() "function-type interface" of \ref Bfs algorithm. 960 /// It does not have own \ref run( ) method, it uses the functions961 /// and features of the plain \ref Bfs.963 /// It does not have own \ref run(Node) "run()" method, it uses the 964 /// functions and features of the plain \ref Bfs. 962 965 /// 963 966 /// This class should only be used through the \ref bfs() function, 964 967 /// which makes it easier to use the algorithm. 968 /// 969 /// \tparam TR The traits class that defines various types used by the 970 /// algorithm. 965 971 template<class TR> 966 972 class BfsWizard : public TR … … 968 974 typedef TR Base; 969 975 970 ///The type of the digraph the algorithm runs on.971 976 typedef typename TR::Digraph Digraph; 972 977 … … 976 981 typedef typename Digraph::OutArcIt OutArcIt; 977 982 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 983 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 984 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 985 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 986 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 987 typedef typename TR::Path Path; 989 988 … … 1055 1054 ///Runs BFS algorithm to visit all nodes in the digraph. 1056 1055 1057 ///This method runs BFS algorithm in order to compute1058 /// the shortest path to each node.1056 ///This method runs BFS algorithm in order to visit all nodes 1057 ///in the digraph. 1059 1058 void run() 1060 1059 { … … 1068 1067 SetPredMapBase(const TR &b) : TR(b) {} 1069 1068 }; 1070 ///\brief \ref named-func-param "Named parameter" 1071 ///for setting PredMap object. 1072 /// 1073 ///\ref named-func-param "Named parameter" 1074 ///for setting PredMap object. 1069 1070 ///\brief \ref named-templ-param "Named parameter" for setting 1071 ///the predecessor map. 1072 /// 1073 ///\ref named-templ-param "Named parameter" function for setting 1074 ///the map that stores the predecessor arcs of the nodes. 1075 1075 template<class T> 1076 1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1086 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1087 }; 1088 ///\brief \ref named-func-param "Named parameter" 1089 ///for setting ReachedMap object. 1090 /// 1091 /// \ref named-func-param "Named parameter" 1092 ///for setting ReachedMap object. 1088 1089 ///\brief \ref named-templ-param "Named parameter" for setting 1090 ///the reached map. 1091 /// 1092 ///\ref named-templ-param "Named parameter" function for setting 1093 ///the map that indicates which nodes are reached. 1093 1094 template<class T> 1094 1095 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1105 SetDistMapBase(const TR &b) : TR(b) {} 1105 1106 }; 1106 ///\brief \ref named-func-param "Named parameter" 1107 ///for setting DistMap object. 1108 /// 1109 /// \ref named-func-param "Named parameter" 1110 ///for setting DistMap object. 1107 1108 ///\brief \ref named-templ-param "Named parameter" for setting 1109 ///the distance map. 1110 /// 1111 ///\ref named-templ-param "Named parameter" function for setting 1112 ///the map that stores the distances of the nodes calculated 1113 ///by the algorithm. 1111 1114 template<class T> 1112 1115 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1125 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1126 }; 1124 ///\brief \ref named-func-param "Named parameter" 1125 ///for setting ProcessedMap object. 1126 /// 1127 /// \ref named-func-param "Named parameter" 1128 ///for setting ProcessedMap object. 1127 1128 ///\brief \ref named-func-param "Named parameter" for setting 1129 ///the processed map. 1130 /// 1131 ///\ref named-templ-param "Named parameter" function for setting 1132 ///the map that indicates which nodes are processed. 1129 1133 template<class T> 1130 1134 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1179 1183 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1180 1184 ///\endcode 1181 ///\warning Don't forget to put the \ref BfsWizard::run( ) "run()"1185 ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()" 1182 1186 ///to the end of the parameter list. 1183 1187 ///\sa BfsWizard … … 1195 1199 /// This class defines the interface of the BfsVisit events, and 1196 1200 /// it could be the base of a real visitor class. 1197 template <typename _Digraph>1201 template <typename GR> 1198 1202 struct BfsVisitor { 1199 typedef _DigraphDigraph;1203 typedef GR Digraph; 1200 1204 typedef typename Digraph::Arc Arc; 1201 1205 typedef typename Digraph::Node Node; … … 1225 1229 }; 1226 1230 #else 1227 template <typename _Digraph>1231 template <typename GR> 1228 1232 struct BfsVisitor { 1229 typedef _DigraphDigraph;1233 typedef GR Digraph; 1230 1234 typedef typename Digraph::Arc Arc; 1231 1235 typedef typename Digraph::Node Node; … … 1255 1259 /// 1256 1260 /// Default traits class of BfsVisit class. 1257 /// \tparam _DigraphThe type of the digraph the algorithm runs on.1258 template<class _Digraph>1261 /// \tparam GR The type of the digraph the algorithm runs on. 1262 template<class GR> 1259 1263 struct BfsVisitDefaultTraits { 1260 1264 1261 1265 /// \brief The type of the digraph the algorithm runs on. 1262 typedef _DigraphDigraph;1266 typedef GR Digraph; 1263 1267 1264 1268 /// \brief The type of the map that indicates which nodes are reached. 1265 1269 /// 1266 1270 /// The type of the map that indicates which nodes are reached. 1267 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1271 /// It must conform to 1272 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1268 1273 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1269 1274 … … 1281 1286 /// \ingroup search 1282 1287 /// 1283 /// \brief %BFS algorithm class with visitor interface.1288 /// \brief BFS algorithm class with visitor interface. 1284 1289 /// 1285 /// This class provides an efficient implementation of the %BFS algorithm1290 /// This class provides an efficient implementation of the BFS algorithm 1286 1291 /// with visitor interface. 1287 1292 /// 1288 /// The %BfsVisit class provides an alternative interface to the Bfs1293 /// The BfsVisit class provides an alternative interface to the Bfs 1289 1294 /// class. It works with callback mechanism, the BfsVisit object calls 1290 1295 /// the member functions of the \c Visitor class on every BFS event. … … 1295 1300 /// instead. 1296 1301 /// 1297 /// \tparam _DigraphThe type of the digraph the algorithm runs on.1298 /// The default value is1299 /// \ref ListDigraph. The value of _Digraph is not used directly by1300 /// \ref BfsVisit,it is only passed to \ref BfsVisitDefaultTraits.1301 /// \tparam _VisitorThe Visitor type that is used by the algorithm.1302 /// \ref BfsVisitor "BfsVisitor< _Digraph>" is an empty visitor, which1302 /// \tparam GR The type of the digraph the algorithm runs on. 1303 /// The default type is \ref ListDigraph. 1304 /// The value of GR is not used directly by \ref BfsVisit, 1305 /// it is only passed to \ref BfsVisitDefaultTraits. 1306 /// \tparam VS The Visitor type that is used by the algorithm. 1307 /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which 1303 1308 /// does not observe the BFS events. If you want to observe the BFS 1304 1309 /// events, you should implement your own visitor class. 1305 /// \tparam _Traits Traits class to set various datatypes used by the1306 /// algorithm. The default traits class is1307 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".1308 /// See \ref BfsVisitDefaultTraits for the documentation of1309 /// a BFS visit traits class.1310 /// \tparam TR The traits class that defines various types used by the 1311 /// algorithm. By default, it is \ref BfsVisitDefaultTraits 1312 /// "BfsVisitDefaultTraits<GR>". 1313 /// In most cases, this parameter should not be set directly, 1314 /// consider to use the named template parameters instead. 1310 1315 #ifdef DOXYGEN 1311 template <typename _Digraph, typename _Visitor, typename _Traits>1316 template <typename GR, typename VS, typename TR> 1312 1317 #else 1313 template <typename _Digraph= ListDigraph,1314 typename _Visitor = BfsVisitor<_Digraph>,1315 typename _Traits = BfsVisitDefaultTraits<_Digraph> >1318 template <typename GR = ListDigraph, 1319 typename VS = BfsVisitor<GR>, 1320 typename TR = BfsVisitDefaultTraits<GR> > 1316 1321 #endif 1317 1322 class BfsVisit { … … 1319 1324 1320 1325 ///The traits class. 1321 typedef _TraitsTraits;1326 typedef TR Traits; 1322 1327 1323 1328 ///The type of the digraph the algorithm runs on. … … 1325 1330 1326 1331 ///The visitor type used by the algorithm. 1327 typedef _VisitorVisitor;1332 typedef VS Visitor; 1328 1333 1329 1334 ///The type of the map that indicates which nodes are reached. … … 1365 1370 typedef BfsVisit Create; 1366 1371 1367 /// \name Named template parameters1372 /// \name Named Template Parameters 1368 1373 1369 1374 ///@{ … … 1407 1412 /// 1408 1413 /// Sets the map that indicates which nodes are reached. 1409 /// If you don't use this function before calling \ref run(), 1410 /// it will allocate one. The destructor deallocates this 1411 /// automatically allocated map, of course. 1414 /// If you don't use this function before calling \ref run(Node) "run()" 1415 /// or \ref init(), an instance will be allocated automatically. 1416 /// The destructor deallocates this automatically allocated map, 1417 /// of course. 1412 1418 /// \return <tt> (*this) </tt> 1413 1419 BfsVisit &reachedMap(ReachedMap &m) { … … 1422 1428 public: 1423 1429 1424 /// \name Execution control 1425 /// The simplest way to execute the algorithm is to use 1426 /// one of the member functions called \ref lemon::BfsVisit::run() 1427 /// "run()". 1428 /// \n 1429 /// If you need more control on the execution, first you must call 1430 /// \ref lemon::BfsVisit::init() "init()", then you can add several 1431 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". 1432 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the 1433 /// actual path computation. 1430 /// \name Execution Control 1431 /// The simplest way to execute the BFS algorithm is to use one of the 1432 /// member functions called \ref run(Node) "run()".\n 1433 /// If you need better control on the execution, you have to call 1434 /// \ref init() first, then you can add several source nodes with 1435 /// \ref addSource(). Finally the actual path computation can be 1436 /// performed with one of the \ref start() functions. 1434 1437 1435 1438 /// @{ … … 1701 1704 /// \brief Runs the algorithm to visit all nodes in the digraph. 1702 1705 /// 1703 /// This method runs the %BFS algorithm in order to 1704 /// compute the shortest path to each node. 1705 /// 1706 /// The algorithm computes 1707 /// - the shortest path tree (forest), 1708 /// - the distance of each node from the root(s). 1706 /// This method runs the %BFS algorithm in order to visit all nodes 1707 /// in the digraph. 1709 1708 /// 1710 1709 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1731 1730 1732 1731 /// \name Query Functions 1733 /// The result of the %BFS algorithm can be obtained using these1732 /// The results of the BFS algorithm can be obtained using these 1734 1733 /// functions.\n 1735 /// Either \ref lemon::BfsVisit::run() "run()" or1736 /// \ref lemon::BfsVisit::start() "start()" must be called before1737 /// using them. 1734 /// Either \ref run(Node) "run()" or \ref start() should be called 1735 /// before using them. 1736 1738 1737 ///@{ 1739 1738 1740 /// \brief Checks if a node is reachable from the root(s). 1741 /// 1742 /// Returns \c true if \c v is reachable from the root(s). 1743 /// \pre Either \ref run() or \ref start() 1739 /// \brief Checks if the given node is reached from the root(s). 1740 /// 1741 /// Returns \c true if \c v is reached from the root(s). 1742 /// 1743 /// \pre Either \ref run(Node) "run()" or \ref init() 1744 1744 /// must be called before using this function. 1745 bool reached(Node v) { return (*_reached)[v]; }1745 bool reached(Node v) const { return (*_reached)[v]; } 1746 1746 1747 1747 ///@}
Note: See TracChangeset
for help on using the changeset viewer.
