Changes in lemon/bfs.h [278:931190050520:258:0310c8984732] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r278 r258 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/path.h>32 31 33 32 namespace lemon { … … 117 116 ///This class provides an efficient implementation of the %BFS algorithm. 118 117 /// 119 ///There is also a \ref bfs() "function -type interface" for the BFS118 ///There is also a \ref bfs() "function type interface" for the BFS 120 119 ///algorithm, which is convenient in the simplier cases and it can be 121 120 ///used easier. … … 843 842 ///arcs of the shortest paths. 844 843 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 845 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;844 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; 846 845 ///Instantiates a \ref PredMap. 847 846 … … 850 849 ///\ref PredMap. 851 850 ///\todo The digraph alone may be insufficient to initialize 851 #ifdef DOXYGEN 852 852 static PredMap *createPredMap(const Digraph &g) 853 { 854 return new PredMap(g); 853 #else 854 static PredMap *createPredMap(const Digraph &) 855 #endif 856 { 857 return new PredMap(); 855 858 } 856 859 … … 859 862 ///The type of the map that indicates which nodes are processed. 860 863 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 861 ///By default it is a NullMap.862 864 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 863 865 ///Instantiates a \ref ProcessedMap. … … 894 896 ///The type of the map that stores the distances of the nodes. 895 897 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 896 typedef typename Digraph::template NodeMap<int> DistMap; 898 /// 899 typedef NullMap<typename Digraph::Node,int> DistMap; 897 900 ///Instantiates a \ref DistMap. 898 901 … … 900 903 ///\param g is the digraph, to which we would like to define 901 904 ///the \ref DistMap 905 #ifdef DOXYGEN 902 906 static DistMap *createDistMap(const Digraph &g) 903 { 904 return new DistMap(g); 905 } 906 907 ///The type of the shortest paths. 908 909 ///The type of the shortest paths. 910 ///It must meet the \ref concepts::Path "Path" concept. 911 typedef lemon::Path<Digraph> Path; 907 #else 908 static DistMap *createDistMap(const Digraph &) 909 #endif 910 { 911 return new DistMap(); 912 } 912 913 }; 913 914 … … 939 940 //Pointer to the map of distances. 940 941 void *_dist; 941 //Pointer to the shortest path to the target node. 942 void *_path; 943 //Pointer to the distance of the target node. 944 int *_di; 942 //Pointer to the source node. 943 Node _source; 945 944 946 945 public: … … 948 947 949 948 /// This constructor does not require parameters, therefore it initiates 950 /// all of the attributes to \c 0.949 /// all of the attributes to default values (0, INVALID). 951 950 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 952 _dist(0), _ path(0), _di(0) {}951 _dist(0), _source(INVALID) {} 953 952 954 953 /// Constructor. 955 954 956 /// This constructor requires one parameter, 957 /// others are initiated to \c 0. 955 /// This constructor requires some parameters, 956 /// listed in the parameters list. 957 /// Others are initiated to 0. 958 958 /// \param g The digraph the algorithm runs on. 959 BfsWizardBase(const GR &g) : 959 /// \param s The source node. 960 BfsWizardBase(const GR &g, Node s=INVALID) : 960 961 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 961 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}962 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} 962 963 963 964 }; 964 965 965 /// Auxiliary class for the function-type interface of BFS algorithm. 966 967 /// This auxiliary class is created to implement the 968 /// \ref bfs() "function-type interface" of \ref Bfs algorithm. 969 /// It does not have own \ref run() method, it uses the functions 970 /// and features of the plain \ref Bfs. 966 /// Auxiliary class for the function type interface of BFS algorithm. 967 968 /// This auxiliary class is created to implement the function type 969 /// interface of \ref Bfs algorithm. It uses the functions and features 970 /// of the plain \ref Bfs, but it is much simpler to use it. 971 /// It should only be used through the \ref bfs() function, which makes 972 /// it easier to use the algorithm. 971 973 /// 972 /// This class should only be used through the \ref bfs() function, 973 /// which makes it easier to use the algorithm. 974 /// Simplicity means that the way to change the types defined 975 /// in the traits class is based on functions that returns the new class 976 /// and not on templatable built-in classes. 977 /// When using the plain \ref Bfs 978 /// the new class with the modified type comes from 979 /// the original class by using the :: 980 /// operator. In the case of \ref BfsWizard only 981 /// a function have to be called, and it will 982 /// return the needed class. 983 /// 984 /// It does not have own \ref run() method. When its \ref run() method 985 /// is called, it initiates a plain \ref Bfs object, and calls the 986 /// \ref Bfs::run() method of it. 974 987 template<class TR> 975 988 class BfsWizard : public TR … … 994 1007 ///\brief The type of the map that indicates which nodes are processed. 995 1008 typedef typename TR::ProcessedMap ProcessedMap; 996 ///The type of the shortest paths997 typedef typename TR::Path Path;998 1009 999 1010 public: … … 1006 1017 /// Constructor that requires parameters. 1007 1018 /// These parameters will be the default values for the traits class. 1008 /// \param g The digraph the algorithm runs on. 1009 BfsWizard(const Digraph &g) : 1010 TR(g) {} 1019 BfsWizard(const Digraph &g, Node s=INVALID) : 1020 TR(g,s) {} 1011 1021 1012 1022 ///Copy constructor … … 1015 1025 ~BfsWizard() {} 1016 1026 1017 ///Runs BFS algorithm from the given source node. 1018 1019 ///This method runs BFS algorithm from node \c s 1020 ///in order to compute the shortest path to each node. 1027 ///Runs BFS algorithm from a source node. 1028 1029 ///Runs BFS algorithm from a source node. 1030 ///The node can be given with the \ref source() function. 1031 void run() 1032 { 1033 if(Base::_source==INVALID) throw UninitializedParameter(); 1034 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1035 if(Base::_reached) 1036 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1037 if(Base::_processed) 1038 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1039 if(Base::_pred) 1040 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1041 if(Base::_dist) 1042 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1043 alg.run(Base::_source); 1044 } 1045 1046 ///Runs BFS algorithm from the given node. 1047 1048 ///Runs BFS algorithm from the given node. 1049 ///\param s is the given source. 1021 1050 void run(Node s) 1022 1051 { 1023 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1024 if (Base::_pred) 1025 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1026 if (Base::_dist) 1027 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1028 if (Base::_reached) 1029 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1030 if (Base::_processed) 1031 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1032 if (s!=INVALID) 1033 alg.run(s); 1034 else 1035 alg.run(); 1036 } 1037 1038 ///Finds the shortest path between \c s and \c t. 1039 1040 ///This method runs BFS algorithm from node \c s 1041 ///in order to compute the shortest path to node \c t 1042 ///(it stops searching when \c t is processed). 1043 /// 1044 ///\return \c true if \c t is reachable form \c s. 1045 bool run(Node s, Node t) 1046 { 1047 if (s==INVALID || t==INVALID) throw UninitializedParameter(); 1048 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1049 if (Base::_pred) 1050 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1051 if (Base::_dist) 1052 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1053 if (Base::_reached) 1054 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1055 if (Base::_processed) 1056 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1057 alg.run(s,t); 1058 if (Base::_path) 1059 *reinterpret_cast<Path*>(Base::_path) = alg.path(t); 1060 if (Base::_di) 1061 *Base::_di = alg.dist(t); 1062 return alg.reached(t); 1063 } 1064 1065 ///Runs BFS algorithm to visit all nodes in the digraph. 1066 1067 ///This method runs BFS algorithm in order to compute 1068 ///the shortest path to each node. 1069 void run() 1070 { 1071 run(INVALID); 1052 Base::_source=s; 1053 run(); 1054 } 1055 1056 /// Sets the source node, from which the Bfs algorithm runs. 1057 1058 /// Sets the source node, from which the Bfs algorithm runs. 1059 /// \param s is the source node. 1060 BfsWizard<TR> &source(Node s) 1061 { 1062 Base::_source=s; 1063 return *this; 1072 1064 } 1073 1065 … … 1078 1070 SetPredMapBase(const TR &b) : TR(b) {} 1079 1071 }; 1080 ///\brief \ref named- func-param "Named parameter"1072 ///\brief \ref named-templ-param "Named parameter" 1081 1073 ///for setting \ref PredMap object. 1082 1074 /// 1083 /// \ref named-func-param "Named parameter"1075 /// \ref named-templ-param "Named parameter" 1084 1076 ///for setting \ref PredMap object. 1085 1077 template<class T> … … 1096 1088 SetReachedMapBase(const TR &b) : TR(b) {} 1097 1089 }; 1098 ///\brief \ref named- func-param "Named parameter"1090 ///\brief \ref named-templ-param "Named parameter" 1099 1091 ///for setting \ref ReachedMap object. 1100 1092 /// 1101 /// \ref named- func-param "Named parameter"1093 /// \ref named-templ-param "Named parameter" 1102 1094 ///for setting \ref ReachedMap object. 1103 1095 template<class T> … … 1106 1098 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1107 1099 return BfsWizard<SetReachedMapBase<T> >(*this); 1100 } 1101 1102 template<class T> 1103 struct SetProcessedMapBase : public Base { 1104 typedef T ProcessedMap; 1105 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; 1106 SetProcessedMapBase(const TR &b) : TR(b) {} 1107 }; 1108 ///\brief \ref named-templ-param "Named parameter" 1109 ///for setting \ref ProcessedMap object. 1110 /// 1111 /// \ref named-templ-param "Named parameter" 1112 ///for setting \ref ProcessedMap object. 1113 template<class T> 1114 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) 1115 { 1116 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); 1117 return BfsWizard<SetProcessedMapBase<T> >(*this); 1108 1118 } 1109 1119 … … 1114 1124 SetDistMapBase(const TR &b) : TR(b) {} 1115 1125 }; 1116 ///\brief \ref named- func-param "Named parameter"1126 ///\brief \ref named-templ-param "Named parameter" 1117 1127 ///for setting \ref DistMap object. 1118 1128 /// 1119 /// \ref named- func-param "Named parameter"1129 /// \ref named-templ-param "Named parameter" 1120 1130 ///for setting \ref DistMap object. 1121 1131 template<class T> … … 1126 1136 } 1127 1137 1128 template<class T>1129 struct SetProcessedMapBase : public Base {1130 typedef T ProcessedMap;1131 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };1132 SetProcessedMapBase(const TR &b) : TR(b) {}1133 };1134 ///\brief \ref named-func-param "Named parameter"1135 ///for setting \ref ProcessedMap object.1136 ///1137 /// \ref named-func-param "Named parameter"1138 ///for setting \ref ProcessedMap object.1139 template<class T>1140 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)1141 {1142 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));1143 return BfsWizard<SetProcessedMapBase<T> >(*this);1144 }1145 1146 template<class T>1147 struct SetPathBase : public Base {1148 typedef T Path;1149 SetPathBase(const TR &b) : TR(b) {}1150 };1151 ///\brief \ref named-func-param "Named parameter"1152 ///for getting the shortest path to the target node.1153 ///1154 ///\ref named-func-param "Named parameter"1155 ///for getting the shortest path to the target node.1156 template<class T>1157 BfsWizard<SetPathBase<T> > path(const T &t)1158 {1159 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));1160 return BfsWizard<SetPathBase<T> >(*this);1161 }1162 1163 ///\brief \ref named-func-param "Named parameter"1164 ///for getting the distance of the target node.1165 ///1166 ///\ref named-func-param "Named parameter"1167 ///for getting the distance of the target node.1168 BfsWizard dist(const int &d)1169 {1170 Base::_di=const_cast<int*>(&d);1171 return *this;1172 }1173 1174 1138 }; 1175 1139 1176 ///Function -type interface for BFSalgorithm.1140 ///Function type interface for Bfs algorithm. 1177 1141 1178 1142 /// \ingroup search 1179 ///Function -type interface for BFSalgorithm.1143 ///Function type interface for Bfs algorithm. 1180 1144 /// 1181 ///This function also has several \ref named-func-param "named parameters", 1145 ///This function also has several 1146 ///\ref named-templ-func-param "named parameters", 1182 1147 ///they are declared as the members of class \ref BfsWizard. 1183 ///The following examples show how to use these parameters. 1148 ///The following 1149 ///example shows how to use these parameters. 1184 1150 ///\code 1185 /// // Compute shortest path from node s to each node 1186 /// bfs(g).predMap(preds).distMap(dists).run(s); 1187 /// 1188 /// // Compute shortest path from s to t 1189 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1151 /// bfs(g,source).predMap(preds).run(); 1190 1152 ///\endcode 1191 1153 ///\warning Don't forget to put the \ref BfsWizard::run() "run()" … … 1195 1157 template<class GR> 1196 1158 BfsWizard<BfsWizardBase<GR> > 1197 bfs(const GR & digraph)1159 bfs(const GR &g,typename GR::Node s=INVALID) 1198 1160 { 1199 return BfsWizard<BfsWizardBase<GR> >( digraph);1161 return BfsWizard<BfsWizardBase<GR> >(g,s); 1200 1162 } 1201 1163
Note: See TracChangeset
for help on using the changeset viewer.