Changeset 2091:c8ccc1f8fd51 in lemon0.x for lemon/maps.h
 Timestamp:
 05/18/06 10:04:00 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2760
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/maps.h
r2080 r2091 21 21 22 22 #include <iterator> 23 #include <functional> 23 24 24 25 #include <lemon/bits/utility.h> … … 1009 1010 } 1010 1011 1012 namespace _maps_bits { 1013 template <typename Value> 1014 struct Identity { 1015 typedef Value argument_type; 1016 typedef Value result_type; 1017 Value operator()(const Value& val) { 1018 return val; 1019 } 1020 }; 1021 } 1022 1023 1011 1024 /// \brief Writable bool map for store each true assigned elements. 1012 1025 /// … … 1014 1027 /// copies all the true setted keys to the given iterator. 1015 1028 /// 1016 /// \note The container of the iterator should contain for each element. 1017 template <typename _Iterator> 1029 /// \note The container of the iterator should contain space 1030 /// for each element. 1031 /// 1032 /// The next example shows how can you write the nodes directly 1033 /// to the standard output. 1034 ///\code 1035 /// typedef IdMap<UGraph, UEdge> UEdgeIdMap; 1036 /// UEdgeIdMap uedgeId(ugraph); 1037 /// 1038 /// typedef MapFunctor<UEdgeIdMap> UEdgeIdFunctor; 1039 /// UEdgeIdFunctor uedgeIdFunctor(uedgeId); 1040 /// 1041 /// StoreBoolMap<ostream_iterator<int>, UEdgeIdFunctor> 1042 /// writerMap(ostream_iterator<int>(cout, " "), uedgeIdFunctor); 1043 /// 1044 /// prim(ugraph, cost, writerMap); 1045 ///\endcode 1046 template <typename _Iterator, 1047 typename _Functor = 1048 _maps_bits::Identity<typename std::iterator_traits<_Iterator>::value_type> > 1018 1049 class StoreBoolMap { 1019 1050 public: 1020 1051 typedef _Iterator Iterator; 1021 1052 1022 typedef typename std::iterator_traits<Iterator>::value_type Key;1053 typedef typename _Functor::argument_type Key; 1023 1054 typedef bool Value; 1024 1055 1056 typedef _Functor Functor; 1057 1025 1058 /// Constructor 1026 StoreBoolMap(Iterator it) : _begin(it), _end(it) {} 1059 StoreBoolMap(Iterator it, const Functor& functor = Functor()) 1060 : _begin(it), _end(it), _functor(functor) {} 1027 1061 1028 1062 /// Gives back the given first setted iterator. … … 1039 1073 void set(const Key& key, Value value) { 1040 1074 if (value) { 1041 *_end++ = key;1075 *_end++ = _functor(key); 1042 1076 } 1043 1077 } … … 1045 1079 private: 1046 1080 Iterator _begin, _end; 1081 Functor _functor; 1047 1082 }; 1048 1083 … … 1052 1087 /// Writable bool map for store each true assigned elements in a back 1053 1088 /// insertable container. It will push back all the true setted keys into 1054 /// the container. 1055 template <typename Container> 1089 /// the container. It can be used to retrieve the items into a standard 1090 /// container. The next example shows how can you store the undirected 1091 /// edges in a vector with prim algorithm. 1092 /// 1093 ///\code 1094 /// vector<UEdge> span_tree_uedges; 1095 /// BackInserterBoolMap<vector<UEdge> > inserter_map(span_tree_uedges); 1096 /// prim(ugraph, cost, inserter_map); 1097 /// 1098 /// for (int i = 0; i < (int)span_tree_uedges.size(); ++i) { 1099 /// std::cout << ugraph.id(ugraph.source(span_tree_uedges[i])) << ' ' 1100 /// << ugraph.id(ugraph.target(span_tree_uedges[i])) << ' ' 1101 /// << cost[span_tree_uedges[i]] << endl; 1102 ///\endcode 1103 template <typename Container, 1104 typename Functor = 1105 _maps_bits::Identity<typename Container::value_type> > 1056 1106 class BackInserterBoolMap { 1057 1107 public: … … 1060 1110 1061 1111 /// Constructor 1062 BackInserterBoolMap(Container& _container) : container(_container) {} 1112 BackInserterBoolMap(Container& _container, 1113 const Functor& _functor = Functor()) 1114 : container(_container), functor(_functor) {} 1063 1115 1064 1116 /// Setter function of the map 1065 1117 void set(const Key& key, Value value) { 1066 1118 if (value) { 1067 container.push_back( key);1119 container.push_back(functor(key)); 1068 1120 } 1069 1121 } 1070 1122 1071 1123 private: 1072 Container& container; 1124 Container& container; 1125 Functor functor; 1073 1126 }; 1074 1127 … … 1078 1131 /// Writable bool map for store each true assigned elements in a front 1079 1132 /// insertable container. It will push front all the true setted keys into 1080 /// the container. 1081 template <typename Container> 1133 /// the container. For example see the BackInserterBoolMap. 1134 template <typename Container, 1135 typename Functor = 1136 _maps_bits::Identity<typename Container::value_type> > 1082 1137 class FrontInserterBoolMap { 1083 1138 public: … … 1086 1141 1087 1142 /// Constructor 1088 FrontInserterBoolMap(Container& _container) : container(_container) {} 1143 FrontInserterBoolMap(Container& _container, 1144 const Functor& _functor = Functor()) 1145 : container(_container), functor(_functor) {} 1089 1146 1090 1147 /// Setter function of the map … … 1097 1154 private: 1098 1155 Container& container; 1156 Functor functor; 1099 1157 }; 1100 1158 … … 1104 1162 /// Writable bool map for store each true assigned elements in an 1105 1163 /// insertable container. It will insert all the true setted keys into 1106 /// the container. 1107 template <typename Container> 1164 /// the container. If you want to store the cut edges of the strongly 1165 /// connected components in a set you can use the next code: 1166 /// 1167 ///\code 1168 /// set<Edge> cut_edges; 1169 /// InserterBoolMap<set<Edge> > inserter_map(cut_edges); 1170 /// stronglyConnectedCutEdges(graph, cost, inserter_map); 1171 ///\endcode 1172 template <typename Container, 1173 typename Functor = 1174 _maps_bits::Identity<typename Container::value_type> > 1108 1175 class InserterBoolMap { 1109 1176 public: … … 1112 1179 1113 1180 /// Constructor 1114 InserterBoolMap(Container& _container) : container(_container) {} 1181 InserterBoolMap(Container& _container, typename Container::iterator _it, 1182 const Functor& _functor = Functor()) 1183 : container(_container), it(_it), functor(_functor) {} 1184 1185 /// Constructor 1186 InserterBoolMap(Container& _container, const Functor& _functor = Functor()) 1187 : container(_container), it(_container.end()), functor(_functor) {} 1115 1188 1116 1189 /// Setter function of the map 1117 1190 void set(const Key& key, Value value) { 1118 1191 if (value) { 1119 container.insert(key); 1192 it = container.insert(it, key); 1193 ++it; 1120 1194 } 1121 1195 } 1122 1196 1123 1197 private: 1124 Container& container; 1198 Container& container; 1199 typename Container::iterator it; 1200 Functor functor; 1125 1201 }; 1126 1202 … … 1130 1206 /// The value can be setted 1131 1207 /// the container. 1208 /// 1209 /// The next code finds the connected components of the undirected graph 1210 /// and stores it in the \c comp map: 1211 ///\code 1212 /// typedef UGraph::NodeMap<int> ComponentMap; 1213 /// ComponentMap comp(ugraph); 1214 /// typedef FillBoolMap<UGraph::NodeMap<int> > ComponentFillerMap; 1215 /// ComponentFillerMap filler(comp, 0); 1216 /// 1217 /// Dfs<UGraph>::DefProcessedMap<ComponentFillerMap>::Create dfs(ugraph); 1218 /// dfs.processedMap(filler); 1219 /// dfs.init(); 1220 /// for (NodeIt it(ugraph); it != INVALID; ++it) { 1221 /// if (!dfs.reached(it)) { 1222 /// dfs.addSource(it); 1223 /// dfs.start(); 1224 /// ++filler.fillValue(); 1225 /// } 1226 /// } 1227 ///\endcode 1228 1132 1229 template <typename Map> 1133 1230 class FillBoolMap { … … 1145 1242 1146 1243 /// Gives back the current fill value 1147 typename Map::Value fillValue() const { 1244 const typename Map::Value& fillValue() const { 1245 return fill; 1246 } 1247 1248 /// Gives back the current fill value 1249 typename Map::Value& fillValue() { 1148 1250 return fill; 1149 1251 } … … 1171 1273 /// 1172 1274 /// Writable bool map which stores for each true assigned elements 1173 /// the setting order number. 1275 /// the setting order number. It make easy to calculate the leaving 1276 /// order of the nodes in the \ref dfs "Dfs" algorithm. 1277 /// 1278 ///\code 1279 /// typedef Graph::NodeMap<int> OrderMap; 1280 /// OrderMap order(graph); 1281 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap; 1282 /// OrderSetterMap setter(order); 1283 /// Dfs<Graph>::DefProcessedMap<OrderSetterMap>::Create dfs(graph); 1284 /// dfs.processedMap(setter); 1285 /// dfs.init(); 1286 /// for (NodeIt it(graph); it != INVALID; ++it) { 1287 /// if (!dfs.reached(it)) { 1288 /// dfs.addSource(it); 1289 /// dfs.start(); 1290 /// } 1291 /// } 1292 ///\endcode 1293 /// 1294 /// The discovering order can be stored a little harder because the 1295 /// ReachedMap should be readable in the dfs algorithm but the setting 1296 /// order map is not readable. Now we should use the fork map: 1297 /// 1298 ///\code 1299 /// typedef Graph::NodeMap<int> OrderMap; 1300 /// OrderMap order(graph); 1301 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap; 1302 /// OrderSetterMap setter(order); 1303 /// typedef Graph::NodeMap<bool> StoreMap; 1304 /// StoreMap store(graph); 1305 /// 1306 /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap; 1307 /// ReachedMap reached(store, setter); 1308 /// 1309 /// Dfs<Graph>::DefReachedMap<ReachedMap>::Create dfs(graph); 1310 /// dfs.reachedMap(reached); 1311 /// dfs.init(); 1312 /// for (NodeIt it(graph); it != INVALID; ++it) { 1313 /// if (!dfs.reached(it)) { 1314 /// dfs.addSource(it); 1315 /// dfs.start(); 1316 /// } 1317 /// } 1318 /// for (NodeIt it(graph); it != INVALID; ++it) { 1319 /// cout << graph.id(it) << ' ' << order[it] << endl; 1320 /// } 1321 ///\endcode 1174 1322 template <typename Map> 1175 1323 class SettingOrderBoolMap {
Note: See TracChangeset
for help on using the changeset viewer.