Changeset 281:e9b4fbe163f5 in lemon for lemon/bfs.h
 Timestamp:
 09/26/08 09:52:28 (12 years ago)
 Branch:
 default
 Parents:
 280:e7f8647ce760 (diff), 279:6307bbbf285b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bfs.h
r278 r281 55 55 ///\param g is the digraph, to which we would like to define the 56 56 ///\ref PredMap. 57 ///\todo The digraph alone may be insufficient to initialize58 57 static PredMap *createPredMap(const Digraph &g) 59 58 { … … 65 64 ///The type of the map that indicates which nodes are processed. 66 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 67 ///By default it is a NullMap.68 66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 69 67 ///Instantiates a \ref ProcessedMap. … … 197 195 int _curr_dist; 198 196 199 ///Creates the maps if necessary. 200 ///\todo Better memory allocation (instead of new). 197 //Creates the maps if necessary. 201 198 void create_maps() 202 199 { … … 849 846 ///\param g is the digraph, to which we would like to define the 850 847 ///\ref PredMap. 851 ///\todo The digraph alone may be insufficient to initialize852 848 static PredMap *createPredMap(const Digraph &g) 853 849 { … … 1371 1367 int _list_front, _list_back; 1372 1368 1373 ///Creates the maps if necessary. 1374 ///\todo Better memory allocation (instead of new). 1369 //Creates the maps if necessary. 1375 1370 void create_maps() { 1376 1371 if(!_reached) { 
lemon/bfs.h
r280 r281 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/path.h> 31 32 32 33 namespace lemon { … … 114 115 ///This class provides an efficient implementation of the %BFS algorithm. 115 116 /// 116 ///There is also a \ref bfs() "function 117 ///There is also a \ref bfs() "functiontype interface" for the BFS 117 118 ///algorithm, which is convenient in the simplier cases and it can be 118 119 ///used easier. … … 839 840 ///arcs of the shortest paths. 840 841 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 841 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;842 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 842 843 ///Instantiates a \ref PredMap. 843 844 … … 845 846 ///\param g is the digraph, to which we would like to define the 846 847 ///\ref PredMap. 847 #ifdef DOXYGEN848 848 static PredMap *createPredMap(const Digraph &g) 849 #else 850 static PredMap *createPredMap(const Digraph &) 851 #endif 852 { 853 return new PredMap(); 849 { 850 return new PredMap(g); 854 851 } 855 852 … … 858 855 ///The type of the map that indicates which nodes are processed. 859 856 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 857 ///By default it is a NullMap. 860 858 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 861 859 ///Instantiates a \ref ProcessedMap. … … 892 890 ///The type of the map that stores the distances of the nodes. 893 891 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 894 /// 895 typedef NullMap<typename Digraph::Node,int> DistMap; 892 typedef typename Digraph::template NodeMap<int> DistMap; 896 893 ///Instantiates a \ref DistMap. 897 894 … … 899 896 ///\param g is the digraph, to which we would like to define 900 897 ///the \ref DistMap 901 #ifdef DOXYGEN902 898 static DistMap *createDistMap(const Digraph &g) 903 #else 904 static DistMap *createDistMap(const Digraph &) 905 #endif 906 { 907 return new DistMap(); 908 } 899 { 900 return new DistMap(g); 901 } 902 903 ///The type of the shortest paths. 904 905 ///The type of the shortest paths. 906 ///It must meet the \ref concepts::Path "Path" concept. 907 typedef lemon::Path<Digraph> Path; 909 908 }; 910 909 … … 936 935 //Pointer to the map of distances. 937 936 void *_dist; 938 //Pointer to the source node. 939 Node _source; 937 //Pointer to the shortest path to the target node. 938 void *_path; 939 //Pointer to the distance of the target node. 940 int *_di; 940 941 941 942 public: … … 943 944 944 945 /// This constructor does not require parameters, therefore it initiates 945 /// all of the attributes to default values (0, INVALID).946 /// all of the attributes to \c 0. 946 947 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 947 _dist(0), _ source(INVALID) {}948 _dist(0), _path(0), _di(0) {} 948 949 949 950 /// Constructor. 950 951 951 /// This constructor requires some parameters, 952 /// listed in the parameters list. 953 /// Others are initiated to 0. 952 /// This constructor requires one parameter, 953 /// others are initiated to \c 0. 954 954 /// \param g The digraph the algorithm runs on. 955 /// \param s The source node. 956 BfsWizardBase(const GR &g, Node s=INVALID) : 955 BfsWizardBase(const GR &g) : 957 956 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 958 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}957 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 959 958 960 959 }; 961 960 962 /// Auxiliary class for the function type interface of BFS algorithm. 963 964 /// This auxiliary class is created to implement the function type 965 /// interface of \ref Bfs algorithm. It uses the functions and features 966 /// of the plain \ref Bfs, but it is much simpler to use it. 967 /// It should only be used through the \ref bfs() function, which makes 968 /// it easier to use the algorithm. 961 /// Auxiliary class for the functiontype interface of BFS algorithm. 962 963 /// This auxiliary class is created to implement the 964 /// \ref bfs() "functiontype interface" of \ref Bfs algorithm. 965 /// It does not have own \ref run() method, it uses the functions 966 /// and features of the plain \ref Bfs. 969 967 /// 970 /// Simplicity means that the way to change the types defined 971 /// in the traits class is based on functions that returns the new class 972 /// and not on templatable builtin classes. 973 /// When using the plain \ref Bfs 974 /// the new class with the modified type comes from 975 /// the original class by using the :: 976 /// operator. In the case of \ref BfsWizard only 977 /// a function have to be called, and it will 978 /// return the needed class. 979 /// 980 /// It does not have own \ref run() method. When its \ref run() method 981 /// is called, it initiates a plain \ref Bfs object, and calls the 982 /// \ref Bfs::run() method of it. 968 /// This class should only be used through the \ref bfs() function, 969 /// which makes it easier to use the algorithm. 983 970 template<class TR> 984 971 class BfsWizard : public TR … … 1003 990 ///\brief The type of the map that indicates which nodes are processed. 1004 991 typedef typename TR::ProcessedMap ProcessedMap; 992 ///The type of the shortest paths 993 typedef typename TR::Path Path; 1005 994 1006 995 public: … … 1013 1002 /// Constructor that requires parameters. 1014 1003 /// These parameters will be the default values for the traits class. 1015 BfsWizard(const Digraph &g, Node s=INVALID) : 1016 TR(g,s) {} 1004 /// \param g The digraph the algorithm runs on. 1005 BfsWizard(const Digraph &g) : 1006 TR(g) {} 1017 1007 1018 1008 ///Copy constructor … … 1021 1011 ~BfsWizard() {} 1022 1012 1023 ///Runs BFS algorithm from a source node. 1024 1025 ///Runs BFS algorithm from a source node. 1026 ///The node can be given with the \ref source() function. 1013 ///Runs BFS algorithm from the given source node. 1014 1015 ///This method runs BFS algorithm from node \c s 1016 ///in order to compute the shortest path to each node. 1017 void run(Node s) 1018 { 1019 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1020 if (Base::_pred) 1021 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1022 if (Base::_dist) 1023 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1024 if (Base::_reached) 1025 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1026 if (Base::_processed) 1027 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1028 if (s!=INVALID) 1029 alg.run(s); 1030 else 1031 alg.run(); 1032 } 1033 1034 ///Finds the shortest path between \c s and \c t. 1035 1036 ///This method runs BFS algorithm from node \c s 1037 ///in order to compute the shortest path to node \c t 1038 ///(it stops searching when \c t is processed). 1039 /// 1040 ///\return \c true if \c t is reachable form \c s. 1041 bool run(Node s, Node t) 1042 { 1043 if (s==INVALID  t==INVALID) throw UninitializedParameter(); 1044 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1045 if (Base::_pred) 1046 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1047 if (Base::_dist) 1048 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1049 if (Base::_reached) 1050 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1051 if (Base::_processed) 1052 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1053 alg.run(s,t); 1054 if (Base::_path) 1055 *reinterpret_cast<Path*>(Base::_path) = alg.path(t); 1056 if (Base::_di) 1057 *Base::_di = alg.dist(t); 1058 return alg.reached(t); 1059 } 1060 1061 ///Runs BFS algorithm to visit all nodes in the digraph. 1062 1063 ///This method runs BFS algorithm in order to compute 1064 ///the shortest path to each node. 1027 1065 void run() 1028 1066 { 1029 if(Base::_source==INVALID) throw UninitializedParameter(); 1030 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1031 if(Base::_reached) 1032 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1033 if(Base::_processed) 1034 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1035 if(Base::_pred) 1036 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1037 if(Base::_dist) 1038 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1039 alg.run(Base::_source); 1040 } 1041 1042 ///Runs BFS algorithm from the given node. 1043 1044 ///Runs BFS algorithm from the given node. 1045 ///\param s is the given source. 1046 void run(Node s) 1047 { 1048 Base::_source=s; 1049 run(); 1050 } 1051 1052 /// Sets the source node, from which the Bfs algorithm runs. 1053 1054 /// Sets the source node, from which the Bfs algorithm runs. 1055 /// \param s is the source node. 1056 BfsWizard<TR> &source(Node s) 1057 { 1058 Base::_source=s; 1059 return *this; 1067 run(INVALID); 1060 1068 } 1061 1069 … … 1066 1074 SetPredMapBase(const TR &b) : TR(b) {} 1067 1075 }; 1068 ///\brief \ref named templparam "Named parameter"1076 ///\brief \ref namedfuncparam "Named parameter" 1069 1077 ///for setting \ref PredMap object. 1070 1078 /// 1071 /// \ref namedtemplparam "Named parameter"1079 ///\ref namedfuncparam "Named parameter" 1072 1080 ///for setting \ref PredMap object. 1073 1081 template<class T> … … 1084 1092 SetReachedMapBase(const TR &b) : TR(b) {} 1085 1093 }; 1086 ///\brief \ref named templparam "Named parameter"1094 ///\brief \ref namedfuncparam "Named parameter" 1087 1095 ///for setting \ref ReachedMap object. 1088 1096 /// 1089 /// \ref named templparam "Named parameter"1097 /// \ref namedfuncparam "Named parameter" 1090 1098 ///for setting \ref ReachedMap object. 1091 1099 template<class T> … … 1094 1102 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1095 1103 return BfsWizard<SetReachedMapBase<T> >(*this); 1104 } 1105 1106 template<class T> 1107 struct SetDistMapBase : public Base { 1108 typedef T DistMap; 1109 static DistMap *createDistMap(const Digraph &) { return 0; }; 1110 SetDistMapBase(const TR &b) : TR(b) {} 1111 }; 1112 ///\brief \ref namedfuncparam "Named parameter" 1113 ///for setting \ref DistMap object. 1114 /// 1115 /// \ref namedfuncparam "Named parameter" 1116 ///for setting \ref DistMap object. 1117 template<class T> 1118 BfsWizard<SetDistMapBase<T> > distMap(const T &t) 1119 { 1120 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1121 return BfsWizard<SetDistMapBase<T> >(*this); 1096 1122 } 1097 1123 … … 1102 1128 SetProcessedMapBase(const TR &b) : TR(b) {} 1103 1129 }; 1104 ///\brief \ref named templparam "Named parameter"1130 ///\brief \ref namedfuncparam "Named parameter" 1105 1131 ///for setting \ref ProcessedMap object. 1106 1132 /// 1107 /// \ref named templparam "Named parameter"1133 /// \ref namedfuncparam "Named parameter" 1108 1134 ///for setting \ref ProcessedMap object. 1109 1135 template<class T> … … 1115 1141 1116 1142 template<class T> 1117 struct SetDistMapBase : public Base { 1118 typedef T DistMap; 1119 static DistMap *createDistMap(const Digraph &) { return 0; }; 1120 SetDistMapBase(const TR &b) : TR(b) {} 1121 }; 1122 ///\brief \ref namedtemplparam "Named parameter" 1123 ///for setting \ref DistMap object. 1124 /// 1125 /// \ref namedtemplparam "Named parameter" 1126 ///for setting \ref DistMap object. 1143 struct SetPathBase : public Base { 1144 typedef T Path; 1145 SetPathBase(const TR &b) : TR(b) {} 1146 }; 1147 ///\brief \ref namedfuncparam "Named parameter" 1148 ///for getting the shortest path to the target node. 1149 /// 1150 ///\ref namedfuncparam "Named parameter" 1151 ///for getting the shortest path to the target node. 1127 1152 template<class T> 1128 BfsWizard<SetDistMapBase<T> > distMap(const T &t) 1129 { 1130 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1131 return BfsWizard<SetDistMapBase<T> >(*this); 1153 BfsWizard<SetPathBase<T> > path(const T &t) 1154 { 1155 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); 1156 return BfsWizard<SetPathBase<T> >(*this); 1157 } 1158 1159 ///\brief \ref namedfuncparam "Named parameter" 1160 ///for getting the distance of the target node. 1161 /// 1162 ///\ref namedfuncparam "Named parameter" 1163 ///for getting the distance of the target node. 1164 BfsWizard dist(const int &d) 1165 { 1166 Base::_di=const_cast<int*>(&d); 1167 return *this; 1132 1168 } 1133 1169 1134 1170 }; 1135 1171 1136 ///Function type interface for Bfsalgorithm.1172 ///Functiontype interface for BFS algorithm. 1137 1173 1138 1174 /// \ingroup search 1139 ///Function type interface for Bfsalgorithm.1175 ///Functiontype interface for BFS algorithm. 1140 1176 /// 1141 ///This function also has several 1142 ///\ref namedtemplfuncparam "named parameters", 1177 ///This function also has several \ref namedfuncparam "named parameters", 1143 1178 ///they are declared as the members of class \ref BfsWizard. 1144 ///The following 1145 ///example shows how to use these parameters. 1179 ///The following examples show how to use these parameters. 1146 1180 ///\code 1147 /// bfs(g,source).predMap(preds).run(); 1181 /// // Compute shortest path from node s to each node 1182 /// bfs(g).predMap(preds).distMap(dists).run(s); 1183 /// 1184 /// // Compute shortest path from s to t 1185 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1148 1186 ///\endcode 1149 1187 ///\warning Don't forget to put the \ref BfsWizard::run() "run()" … … 1153 1191 template<class GR> 1154 1192 BfsWizard<BfsWizardBase<GR> > 1155 bfs(const GR & g,typename GR::Node s=INVALID)1193 bfs(const GR &digraph) 1156 1194 { 1157 return BfsWizard<BfsWizardBase<GR> >( g,s);1195 return BfsWizard<BfsWizardBase<GR> >(digraph); 1158 1196 } 1159 1197
Note: See TracChangeset
for help on using the changeset viewer.