Changes in lemon/bfs.h [247:f1158744a112:329:d900fd1e760f] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r247 r329 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/path.h> 31 32 32 33 namespace lemon { … … 49 50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 50 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 51 ///Instantiates a \refPredMap.52 53 ///This function instantiates a \ref PredMap.52 ///Instantiates a PredMap. 53 54 ///This function instantiates a PredMap. 54 55 ///\param g is the digraph, to which we would like to define the 55 ///\ref PredMap. 56 ///\todo The digraph alone may be insufficient to initialize 56 ///PredMap. 57 57 static PredMap *createPredMap(const Digraph &g) 58 58 { … … 64 64 ///The type of the map that indicates which nodes are processed. 65 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default it is a NullMap.67 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 68 ///Instantiates a \refProcessedMap.69 70 ///This function instantiates a \refProcessedMap.67 ///Instantiates a ProcessedMap. 68 69 ///This function instantiates a ProcessedMap. 71 70 ///\param g is the digraph, to which 72 ///we would like to define the \refProcessedMap71 ///we would like to define the ProcessedMap 73 72 #ifdef DOXYGEN 74 73 static ProcessedMap *createProcessedMap(const Digraph &g) … … 82 81 ///The type of the map that indicates which nodes are reached. 83 82 84 ///The type of the map that indicates which nodes are reached. 85 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 83 ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 86 84 typedef typename Digraph::template NodeMap<bool> ReachedMap; 87 ///Instantiates a \refReachedMap.88 89 ///This function instantiates a \refReachedMap.85 ///Instantiates a ReachedMap. 86 87 ///This function instantiates a ReachedMap. 90 88 ///\param g is the digraph, to which 91 ///we would like to define the \refReachedMap.89 ///we would like to define the ReachedMap. 92 90 static ReachedMap *createReachedMap(const Digraph &g) 93 91 { … … 100 98 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 101 99 typedef typename Digraph::template NodeMap<int> DistMap; 102 ///Instantiates a \refDistMap.103 104 ///This function instantiates a \refDistMap.100 ///Instantiates a DistMap. 101 102 ///This function instantiates a DistMap. 105 103 ///\param g is the digraph, to which we would like to define the 106 /// \refDistMap.104 ///DistMap. 107 105 static DistMap *createDistMap(const Digraph &g) 108 106 { … … 116 114 ///This class provides an efficient implementation of the %BFS algorithm. 117 115 /// 118 ///There is also a \ref bfs() "function 116 ///There is also a \ref bfs() "function-type interface" for the BFS 119 117 ///algorithm, which is convenient in the simplier cases and it can be 120 118 ///used easier. … … 137 135 class Bfs { 138 136 public: 139 ///\ref Exception for uninitialized parameters.140 141 ///This error represents problems in the initialization of the142 ///parameters of the algorithm.143 class UninitializedParameter : public lemon::UninitializedParameter {144 public:145 virtual const char* what() const throw() {146 return "lemon::Bfs::UninitializedParameter";147 }148 };149 137 150 138 ///The type of the digraph the algorithm runs on. … … 196 184 int _curr_dist; 197 185 198 ///Creates the maps if necessary. 199 ///\todo Better memory allocation (instead of new). 186 //Creates the maps if necessary. 200 187 void create_maps() 201 188 { … … 231 218 232 219 template <class T> 233 struct DefPredMapTraits : public Traits {220 struct SetPredMapTraits : public Traits { 234 221 typedef T PredMap; 235 222 static PredMap *createPredMap(const Digraph &) 236 223 { 237 throw UninitializedParameter(); 224 LEMON_ASSERT(false, "PredMap is not initialized"); 225 return 0; // ignore warnings 238 226 } 239 227 }; 240 228 ///\brief \ref named-templ-param "Named parameter" for setting 241 /// \refPredMap type.229 ///PredMap type. 242 230 /// 243 231 ///\ref named-templ-param "Named parameter" for setting 244 /// \refPredMap type.232 ///PredMap type. 245 233 template <class T> 246 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {247 typedef Bfs< Digraph, DefPredMapTraits<T> > Create;234 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { 235 typedef Bfs< Digraph, SetPredMapTraits<T> > Create; 248 236 }; 249 237 250 238 template <class T> 251 struct DefDistMapTraits : public Traits {239 struct SetDistMapTraits : public Traits { 252 240 typedef T DistMap; 253 241 static DistMap *createDistMap(const Digraph &) 254 242 { 255 throw UninitializedParameter(); 243 LEMON_ASSERT(false, "DistMap is not initialized"); 244 return 0; // ignore warnings 256 245 } 257 246 }; 258 247 ///\brief \ref named-templ-param "Named parameter" for setting 259 /// \refDistMap type.248 ///DistMap type. 260 249 /// 261 250 ///\ref named-templ-param "Named parameter" for setting 262 /// \refDistMap type.251 ///DistMap type. 263 252 template <class T> 264 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {265 typedef Bfs< Digraph, DefDistMapTraits<T> > Create;253 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { 254 typedef Bfs< Digraph, SetDistMapTraits<T> > Create; 266 255 }; 267 256 268 257 template <class T> 269 struct DefReachedMapTraits : public Traits {258 struct SetReachedMapTraits : public Traits { 270 259 typedef T ReachedMap; 271 260 static ReachedMap *createReachedMap(const Digraph &) 272 261 { 273 throw UninitializedParameter(); 262 LEMON_ASSERT(false, "ReachedMap is not initialized"); 263 return 0; // ignore warnings 274 264 } 275 265 }; 276 266 ///\brief \ref named-templ-param "Named parameter" for setting 277 /// \refReachedMap type.267 ///ReachedMap type. 278 268 /// 279 269 ///\ref named-templ-param "Named parameter" for setting 280 /// \refReachedMap type.270 ///ReachedMap type. 281 271 template <class T> 282 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {283 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;272 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { 273 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create; 284 274 }; 285 275 286 276 template <class T> 287 struct DefProcessedMapTraits : public Traits {277 struct SetProcessedMapTraits : public Traits { 288 278 typedef T ProcessedMap; 289 279 static ProcessedMap *createProcessedMap(const Digraph &) 290 280 { 291 throw UninitializedParameter(); 281 LEMON_ASSERT(false, "ProcessedMap is not initialized"); 282 return 0; // ignore warnings 292 283 } 293 284 }; 294 285 ///\brief \ref named-templ-param "Named parameter" for setting 295 /// \refProcessedMap type.286 ///ProcessedMap type. 296 287 /// 297 288 ///\ref named-templ-param "Named parameter" for setting 298 /// \refProcessedMap type.289 ///ProcessedMap type. 299 290 template <class T> 300 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {301 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;291 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { 292 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create; 302 293 }; 303 294 304 struct DefDigraphProcessedMapTraits : public Traits {295 struct SetStandardProcessedMapTraits : public Traits { 305 296 typedef typename Digraph::template NodeMap<bool> ProcessedMap; 306 297 static ProcessedMap *createProcessedMap(const Digraph &g) 307 298 { 308 299 return new ProcessedMap(g); 300 return 0; // ignore warnings 309 301 } 310 302 }; 311 303 ///\brief \ref named-templ-param "Named parameter" for setting 312 /// \refProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.304 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 313 305 /// 314 306 ///\ref named-templ-param "Named parameter" for setting 315 /// \refProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.307 ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. 316 308 ///If you don't set it explicitly, it will be automatically allocated. 317 template <class T> 318 struct DefProcessedMapToBeDefaultMap : 319 public Bfs< Digraph, DefDigraphProcessedMapTraits> { 320 typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create; 309 struct SetStandardProcessedMap : 310 public Bfs< Digraph, SetStandardProcessedMapTraits > { 311 typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create; 321 312 }; 322 313 … … 608 599 /// 609 600 ///This method runs the %BFS algorithm from the root node(s) 610 ///in order to compute the shortest path to \c dest.601 ///in order to compute the shortest path to \c t. 611 602 /// 612 603 ///The algorithm computes 613 ///- the shortest path to \c dest,614 ///- the distance of \c dest from the root(s).604 ///- the shortest path to \c t, 605 ///- the distance of \c t from the root(s). 615 606 /// 616 607 ///\pre init() must be called and at least one root node should be … … 624 615 /// } 625 616 ///\endcode 626 void start(Node dest)617 void start(Node t) 627 618 { 628 619 bool reach = false; 629 while ( !emptyQueue() && !reach ) processNextNode( dest, reach);620 while ( !emptyQueue() && !reach ) processNextNode(t, reach); 630 621 } 631 622 … … 665 656 } 666 657 667 ///Runs the algorithm from the given node.658 ///Runs the algorithm from the given source node. 668 659 669 660 ///This method runs the %BFS algorithm from node \c s … … 689 680 690 681 ///This method runs the %BFS algorithm from node \c s 691 ///in order to compute the shortest path to \c t.692 /// 693 /// \return The length of the shortest <tt>s</tt>--<tt>t</tt> path,694 /// if \c t is reachable form \c s, \c 0 otherwise.682 ///in order to compute the shortest path to node \c t 683 ///(it stops searching when \c t is processed). 684 /// 685 ///\return \c true if \c t is reachable form \c s. 695 686 /// 696 687 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a … … 701 692 /// b.start(t); 702 693 ///\endcode 703 intrun(Node s,Node t) {694 bool run(Node s,Node t) { 704 695 init(); 705 696 addSource(s); 706 697 start(t); 707 return reached(t) ? _curr_dist : 0;698 return reached(t); 708 699 } 709 700 … … 843 834 ///arcs of the shortest paths. 844 835 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 845 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;846 ///Instantiates a \refPredMap.847 848 ///This function instantiates a \refPredMap.836 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 837 ///Instantiates a PredMap. 838 839 ///This function instantiates a PredMap. 849 840 ///\param g is the digraph, to which we would like to define the 850 ///\ref PredMap. 851 ///\todo The digraph alone may be insufficient to initialize 852 #ifdef DOXYGEN 841 ///PredMap. 853 842 static PredMap *createPredMap(const Digraph &g) 854 #else 855 static PredMap *createPredMap(const Digraph &) 856 #endif 857 { 858 return new PredMap(); 843 { 844 return new PredMap(g); 859 845 } 860 846 … … 863 849 ///The type of the map that indicates which nodes are processed. 864 850 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 851 ///By default it is a NullMap. 865 852 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 866 ///Instantiates a \refProcessedMap.867 868 ///This function instantiates a \refProcessedMap.853 ///Instantiates a ProcessedMap. 854 855 ///This function instantiates a ProcessedMap. 869 856 ///\param g is the digraph, to which 870 ///we would like to define the \refProcessedMap.857 ///we would like to define the ProcessedMap. 871 858 #ifdef DOXYGEN 872 859 static ProcessedMap *createProcessedMap(const Digraph &g) … … 883 870 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 884 871 typedef typename Digraph::template NodeMap<bool> ReachedMap; 885 ///Instantiates a \refReachedMap.886 887 ///This function instantiates a \refReachedMap.872 ///Instantiates a ReachedMap. 873 874 ///This function instantiates a ReachedMap. 888 875 ///\param g is the digraph, to which 889 ///we would like to define the \refReachedMap.876 ///we would like to define the ReachedMap. 890 877 static ReachedMap *createReachedMap(const Digraph &g) 891 878 { … … 897 884 ///The type of the map that stores the distances of the nodes. 898 885 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 899 /// 900 typedef NullMap<typename Digraph::Node,int> DistMap; 901 ///Instantiates a \ref DistMap. 902 903 ///This function instantiates a \ref DistMap. 886 typedef typename Digraph::template NodeMap<int> DistMap; 887 ///Instantiates a DistMap. 888 889 ///This function instantiates a DistMap. 904 890 ///\param g is the digraph, to which we would like to define 905 ///the \ref DistMap 906 #ifdef DOXYGEN 891 ///the DistMap 907 892 static DistMap *createDistMap(const Digraph &g) 908 #else 909 static DistMap *createDistMap(const Digraph &) 910 #endif 911 { 912 return new DistMap(); 913 } 893 { 894 return new DistMap(g); 895 } 896 897 ///The type of the shortest paths. 898 899 ///The type of the shortest paths. 900 ///It must meet the \ref concepts::Path "Path" concept. 901 typedef lemon::Path<Digraph> Path; 914 902 }; 915 903 916 /// Default traits class used by \refBfsWizard904 /// Default traits class used by BfsWizard 917 905 918 906 /// To make it easier to use Bfs algorithm … … 941 929 //Pointer to the map of distances. 942 930 void *_dist; 943 //Pointer to the source node. 944 Node _source; 931 //Pointer to the shortest path to the target node. 932 void *_path; 933 //Pointer to the distance of the target node. 934 int *_di; 945 935 946 936 public: … … 948 938 949 939 /// This constructor does not require parameters, therefore it initiates 950 /// all of the attributes to default values (0, INVALID).940 /// all of the attributes to \c 0. 951 941 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 952 _dist(0), _ source(INVALID) {}942 _dist(0), _path(0), _di(0) {} 953 943 954 944 /// Constructor. 955 945 956 /// This constructor requires some parameters, 957 /// listed in the parameters list. 958 /// Others are initiated to 0. 946 /// This constructor requires one parameter, 947 /// others are initiated to \c 0. 959 948 /// \param g The digraph the algorithm runs on. 960 /// \param s The source node. 961 BfsWizardBase(const GR &g, Node s=INVALID) : 949 BfsWizardBase(const GR &g) : 962 950 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 963 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}951 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 964 952 965 953 }; 966 954 967 /// Auxiliary class for the function type interface of BFS algorithm. 968 969 /// This auxiliary class is created to implement the function type 970 /// interface of \ref Bfs algorithm. It uses the functions and features 971 /// of the plain \ref Bfs, but it is much simpler to use it. 972 /// It should only be used through the \ref bfs() function, which makes 973 /// it easier to use the algorithm. 955 /// Auxiliary class for the function-type interface of BFS algorithm. 956 957 /// This auxiliary class is created to implement the 958 /// \ref bfs() "function-type interface" of \ref Bfs algorithm. 959 /// It does not have own \ref run() method, it uses the functions 960 /// and features of the plain \ref Bfs. 974 961 /// 975 /// Simplicity means that the way to change the types defined 976 /// in the traits class is based on functions that returns the new class 977 /// and not on templatable built-in classes. 978 /// When using the plain \ref Bfs 979 /// the new class with the modified type comes from 980 /// the original class by using the :: 981 /// operator. In the case of \ref BfsWizard only 982 /// a function have to be called, and it will 983 /// return the needed class. 984 /// 985 /// It does not have own \ref run() method. When its \ref run() method 986 /// is called, it initiates a plain \ref Bfs object, and calls the 987 /// \ref Bfs::run() method of it. 962 /// This class should only be used through the \ref bfs() function, 963 /// which makes it easier to use the algorithm. 988 964 template<class TR> 989 965 class BfsWizard : public TR … … 1008 984 ///\brief The type of the map that indicates which nodes are processed. 1009 985 typedef typename TR::ProcessedMap ProcessedMap; 986 ///The type of the shortest paths 987 typedef typename TR::Path Path; 1010 988 1011 989 public: … … 1018 996 /// Constructor that requires parameters. 1019 997 /// These parameters will be the default values for the traits class. 1020 BfsWizard(const Digraph &g, Node s=INVALID) : 1021 TR(g,s) {} 998 /// \param g The digraph the algorithm runs on. 999 BfsWizard(const Digraph &g) : 1000 TR(g) {} 1022 1001 1023 1002 ///Copy constructor … … 1026 1005 ~BfsWizard() {} 1027 1006 1028 ///Runs BFS algorithm from a source node. 1029 1030 ///Runs BFS algorithm from a source node. 1031 ///The node can be given with the \ref source() function. 1007 ///Runs BFS algorithm from the given source node. 1008 1009 ///This method runs BFS algorithm from node \c s 1010 ///in order to compute the shortest path to each node. 1011 void run(Node s) 1012 { 1013 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1014 if (Base::_pred) 1015 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1016 if (Base::_dist) 1017 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1018 if (Base::_reached) 1019 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1020 if (Base::_processed) 1021 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1022 if (s!=INVALID) 1023 alg.run(s); 1024 else 1025 alg.run(); 1026 } 1027 1028 ///Finds the shortest path between \c s and \c t. 1029 1030 ///This method runs BFS algorithm from node \c s 1031 ///in order to compute the shortest path to node \c t 1032 ///(it stops searching when \c t is processed). 1033 /// 1034 ///\return \c true if \c t is reachable form \c s. 1035 bool run(Node s, Node t) 1036 { 1037 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1038 if (Base::_pred) 1039 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1040 if (Base::_dist) 1041 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1042 if (Base::_reached) 1043 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1044 if (Base::_processed) 1045 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1046 alg.run(s,t); 1047 if (Base::_path) 1048 *reinterpret_cast<Path*>(Base::_path) = alg.path(t); 1049 if (Base::_di) 1050 *Base::_di = alg.dist(t); 1051 return alg.reached(t); 1052 } 1053 1054 ///Runs BFS algorithm to visit all nodes in the digraph. 1055 1056 ///This method runs BFS algorithm in order to compute 1057 ///the shortest path to each node. 1032 1058 void run() 1033 1059 { 1034 if(Base::_source==INVALID) throw UninitializedParameter(); 1035 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1036 if(Base::_reached) 1037 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1038 if(Base::_processed) 1039 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1040 if(Base::_pred) 1041 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1042 if(Base::_dist) 1043 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1044 alg.run(Base::_source); 1045 } 1046 1047 ///Runs BFS algorithm from the given node. 1048 1049 ///Runs BFS algorithm from the given node. 1050 ///\param s is the given source. 1051 void run(Node s) 1052 { 1053 Base::_source=s; 1054 run(); 1055 } 1056 1057 /// Sets the source node, from which the Bfs algorithm runs. 1058 1059 /// Sets the source node, from which the Bfs algorithm runs. 1060 /// \param s is the source node. 1061 BfsWizard<TR> &source(Node s) 1062 { 1063 Base::_source=s; 1064 return *this; 1060 run(INVALID); 1065 1061 } 1066 1062 1067 1063 template<class T> 1068 struct DefPredMapBase : public Base {1064 struct SetPredMapBase : public Base { 1069 1065 typedef T PredMap; 1070 1066 static PredMap *createPredMap(const Digraph &) { return 0; }; 1071 DefPredMapBase(const TR &b) : TR(b) {}1067 SetPredMapBase(const TR &b) : TR(b) {} 1072 1068 }; 1073 ///\brief \ref named- templ-param "Named parameter"1074 ///for setting \refPredMap object.1075 /// 1076 /// \ref named-templ-param "Named parameter"1077 ///for setting \refPredMap object.1069 ///\brief \ref named-func-param "Named parameter" 1070 ///for setting PredMap object. 1071 /// 1072 ///\ref named-func-param "Named parameter" 1073 ///for setting PredMap object. 1078 1074 template<class T> 1079 BfsWizard< DefPredMapBase<T> > predMap(const T &t)1075 BfsWizard<SetPredMapBase<T> > predMap(const T &t) 1080 1076 { 1081 1077 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 1082 return BfsWizard< DefPredMapBase<T> >(*this);1078 return BfsWizard<SetPredMapBase<T> >(*this); 1083 1079 } 1084 1080 1085 1081 template<class T> 1086 struct DefReachedMapBase : public Base {1082 struct SetReachedMapBase : public Base { 1087 1083 typedef T ReachedMap; 1088 1084 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; 1089 DefReachedMapBase(const TR &b) : TR(b) {}1085 SetReachedMapBase(const TR &b) : TR(b) {} 1090 1086 }; 1091 ///\brief \ref named- templ-param "Named parameter"1092 ///for setting \refReachedMap object.1093 /// 1094 /// \ref named- templ-param "Named parameter"1095 ///for setting \refReachedMap object.1087 ///\brief \ref named-func-param "Named parameter" 1088 ///for setting ReachedMap object. 1089 /// 1090 /// \ref named-func-param "Named parameter" 1091 ///for setting ReachedMap object. 1096 1092 template<class T> 1097 BfsWizard< DefReachedMapBase<T> > reachedMap(const T &t)1093 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) 1098 1094 { 1099 1095 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1100 return BfsWizard< DefReachedMapBase<T> >(*this);1096 return BfsWizard<SetReachedMapBase<T> >(*this); 1101 1097 } 1102 1098 1103 1099 template<class T> 1104 struct DefProcessedMapBase : public Base { 1100 struct SetDistMapBase : public Base { 1101 typedef T DistMap; 1102 static DistMap *createDistMap(const Digraph &) { return 0; }; 1103 SetDistMapBase(const TR &b) : TR(b) {} 1104 }; 1105 ///\brief \ref named-func-param "Named parameter" 1106 ///for setting DistMap object. 1107 /// 1108 /// \ref named-func-param "Named parameter" 1109 ///for setting DistMap object. 1110 template<class T> 1111 BfsWizard<SetDistMapBase<T> > distMap(const T &t) 1112 { 1113 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1114 return BfsWizard<SetDistMapBase<T> >(*this); 1115 } 1116 1117 template<class T> 1118 struct SetProcessedMapBase : public Base { 1105 1119 typedef T ProcessedMap; 1106 1120 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; 1107 DefProcessedMapBase(const TR &b) : TR(b) {}1121 SetProcessedMapBase(const TR &b) : TR(b) {} 1108 1122 }; 1109 ///\brief \ref named- templ-param "Named parameter"1110 ///for setting \refProcessedMap object.1111 /// 1112 /// \ref named- templ-param "Named parameter"1113 ///for setting \refProcessedMap object.1123 ///\brief \ref named-func-param "Named parameter" 1124 ///for setting ProcessedMap object. 1125 /// 1126 /// \ref named-func-param "Named parameter" 1127 ///for setting ProcessedMap object. 1114 1128 template<class T> 1115 BfsWizard< DefProcessedMapBase<T> > processedMap(const T &t)1129 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) 1116 1130 { 1117 1131 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); 1118 return BfsWizard< DefProcessedMapBase<T> >(*this);1132 return BfsWizard<SetProcessedMapBase<T> >(*this); 1119 1133 } 1120 1134 1121 1135 template<class T> 1122 struct DefDistMapBase : public Base { 1123 typedef T DistMap; 1124 static DistMap *createDistMap(const Digraph &) { return 0; }; 1125 DefDistMapBase(const TR &b) : TR(b) {} 1136 struct SetPathBase : public Base { 1137 typedef T Path; 1138 SetPathBase(const TR &b) : TR(b) {} 1126 1139 }; 1127 ///\brief \ref named- templ-param "Named parameter"1128 ///for setting \ref DistMap object.1129 /// 1130 /// \ref named-templ-param "Named parameter"1131 ///for setting \ref DistMap object.1140 ///\brief \ref named-func-param "Named parameter" 1141 ///for getting the shortest path to the target node. 1142 /// 1143 ///\ref named-func-param "Named parameter" 1144 ///for getting the shortest path to the target node. 1132 1145 template<class T> 1133 BfsWizard<DefDistMapBase<T> > distMap(const T &t) 1134 { 1135 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1136 return BfsWizard<DefDistMapBase<T> >(*this); 1146 BfsWizard<SetPathBase<T> > path(const T &t) 1147 { 1148 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); 1149 return BfsWizard<SetPathBase<T> >(*this); 1150 } 1151 1152 ///\brief \ref named-func-param "Named parameter" 1153 ///for getting the distance of the target node. 1154 /// 1155 ///\ref named-func-param "Named parameter" 1156 ///for getting the distance of the target node. 1157 BfsWizard dist(const int &d) 1158 { 1159 Base::_di=const_cast<int*>(&d); 1160 return *this; 1137 1161 } 1138 1162 1139 1163 }; 1140 1164 1141 ///Function type interface for Bfsalgorithm.1165 ///Function-type interface for BFS algorithm. 1142 1166 1143 1167 /// \ingroup search 1144 ///Function type interface for Bfsalgorithm.1168 ///Function-type interface for BFS algorithm. 1145 1169 /// 1146 ///This function also has several 1147 ///\ref named-templ-func-param "named parameters", 1170 ///This function also has several \ref named-func-param "named parameters", 1148 1171 ///they are declared as the members of class \ref BfsWizard. 1149 ///The following 1150 ///example shows how to use these parameters. 1172 ///The following examples show how to use these parameters. 1151 1173 ///\code 1152 /// bfs(g,source).predMap(preds).run(); 1174 /// // Compute shortest path from node s to each node 1175 /// bfs(g).predMap(preds).distMap(dists).run(s); 1176 /// 1177 /// // Compute shortest path from s to t 1178 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1153 1179 ///\endcode 1154 1180 ///\warning Don't forget to put the \ref BfsWizard::run() "run()" … … 1158 1184 template<class GR> 1159 1185 BfsWizard<BfsWizardBase<GR> > 1160 bfs(const GR & g,typename GR::Node s=INVALID)1186 bfs(const GR &digraph) 1161 1187 { 1162 return BfsWizard<BfsWizardBase<GR> >( g,s);1188 return BfsWizard<BfsWizardBase<GR> >(digraph); 1163 1189 } 1164 1190 … … 1241 1267 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1242 1268 1243 /// \brief Instantiates a \refReachedMap.1244 /// 1245 /// This function instantiates a \refReachedMap.1269 /// \brief Instantiates a ReachedMap. 1270 /// 1271 /// This function instantiates a ReachedMap. 1246 1272 /// \param digraph is the digraph, to which 1247 /// we would like to define the \refReachedMap.1273 /// we would like to define the ReachedMap. 1248 1274 static ReachedMap *createReachedMap(const Digraph &digraph) { 1249 1275 return new ReachedMap(digraph); … … 1262 1288 /// class. It works with callback mechanism, the BfsVisit object calls 1263 1289 /// the member functions of the \c Visitor class on every BFS event. 1290 /// 1291 /// This interface of the BFS algorithm should be used in special cases 1292 /// when extra actions have to be performed in connection with certain 1293 /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs() 1294 /// instead. 1264 1295 /// 1265 1296 /// \tparam _Digraph The type of the digraph the algorithm runs on. … … 1281 1312 template <typename _Digraph = ListDigraph, 1282 1313 typename _Visitor = BfsVisitor<_Digraph>, 1283 typename _Traits = Bfs DefaultTraits<_Digraph> >1314 typename _Traits = BfsVisitDefaultTraits<_Digraph> > 1284 1315 #endif 1285 1316 class BfsVisit { 1286 1317 public: 1287 1288 /// \brief \ref Exception for uninitialized parameters.1289 ///1290 /// This error represents problems in the initialization1291 /// of the parameters of the algorithm.1292 class UninitializedParameter : public lemon::UninitializedParameter {1293 public:1294 virtual const char* what() const throw()1295 {1296 return "lemon::BfsVisit::UninitializedParameter";1297 }1298 };1299 1318 1300 1319 ///The traits class. … … 1329 1348 int _list_front, _list_back; 1330 1349 1331 ///Creates the maps if necessary. 1332 ///\todo Better memory allocation (instead of new). 1350 //Creates the maps if necessary. 1333 1351 void create_maps() { 1334 1352 if(!_reached) { … … 1350 1368 ///@{ 1351 1369 template <class T> 1352 struct DefReachedMapTraits : public Traits {1370 struct SetReachedMapTraits : public Traits { 1353 1371 typedef T ReachedMap; 1354 1372 static ReachedMap *createReachedMap(const Digraph &digraph) { 1355 throw UninitializedParameter(); 1373 LEMON_ASSERT(false, "ReachedMap is not initialized"); 1374 return 0; // ignore warnings 1356 1375 } 1357 1376 }; … … 1361 1380 /// \ref named-templ-param "Named parameter" for setting ReachedMap type. 1362 1381 template <class T> 1363 struct DefReachedMap : public BfsVisit< Digraph, Visitor,1364 DefReachedMapTraits<T> > {1365 typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;1382 struct SetReachedMap : public BfsVisit< Digraph, Visitor, 1383 SetReachedMapTraits<T> > { 1384 typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create; 1366 1385 }; 1367 1386 ///@} … … 1580 1599 /// 1581 1600 /// This method runs the %BFS algorithm from the root node(s) 1582 /// in order to compute the shortest path to \c dest.1601 /// in order to compute the shortest path to \c t. 1583 1602 /// 1584 1603 /// The algorithm computes 1585 /// - the shortest path to \c dest,1586 /// - the distance of \c dest from the root(s).1604 /// - the shortest path to \c t, 1605 /// - the distance of \c t from the root(s). 1587 1606 /// 1588 1607 /// \pre init() must be called and at least one root node should be … … 1596 1615 /// } 1597 1616 /// \endcode 1598 void start(Node dest) {1617 void start(Node t) { 1599 1618 bool reach = false; 1600 while ( !emptyQueue() && !reach ) processNextNode( dest, reach);1619 while ( !emptyQueue() && !reach ) processNextNode(t, reach); 1601 1620 } 1602 1621 … … 1636 1655 } 1637 1656 1638 /// \brief Runs the algorithm from the given node.1657 /// \brief Runs the algorithm from the given source node. 1639 1658 /// 1640 1659 /// This method runs the %BFS algorithm from node \c s … … 1655 1674 addSource(s); 1656 1675 start(); 1676 } 1677 1678 /// \brief Finds the shortest path between \c s and \c t. 1679 /// 1680 /// This method runs the %BFS algorithm from node \c s 1681 /// in order to compute the shortest path to node \c t 1682 /// (it stops searching when \c t is processed). 1683 /// 1684 /// \return \c true if \c t is reachable form \c s. 1685 /// 1686 /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a 1687 /// shortcut of the following code. 1688 ///\code 1689 /// b.init(); 1690 /// b.addSource(s); 1691 /// b.start(t); 1692 ///\endcode 1693 bool run(Node s,Node t) { 1694 init(); 1695 addSource(s); 1696 start(t); 1697 return reached(t); 1657 1698 } 1658 1699
Note: See TracChangeset
for help on using the changeset viewer.