1.1 --- a/lemon/maps.h Wed May 17 11:05:34 2006 +0000
1.2 +++ b/lemon/maps.h Thu May 18 08:04:00 2006 +0000
1.3 @@ -20,6 +20,7 @@
1.4 #define LEMON_MAPS_H
1.5
1.6 #include <iterator>
1.7 +#include <functional>
1.8
1.9 #include <lemon/bits/utility.h>
1.10 #include <lemon/bits/traits.h>
1.11 @@ -1008,22 +1009,55 @@
1.12 return NotWriteMap<M>(m);
1.13 }
1.14
1.15 + namespace _maps_bits {
1.16 + template <typename Value>
1.17 + struct Identity {
1.18 + typedef Value argument_type;
1.19 + typedef Value result_type;
1.20 + Value operator()(const Value& val) {
1.21 + return val;
1.22 + }
1.23 + };
1.24 + }
1.25 +
1.26 +
1.27 /// \brief Writable bool map for store each true assigned elements.
1.28 ///
1.29 /// Writable bool map for store each true assigned elements. It will
1.30 /// copies all the true setted keys to the given iterator.
1.31 ///
1.32 - /// \note The container of the iterator should contain for each element.
1.33 - template <typename _Iterator>
1.34 + /// \note The container of the iterator should contain space
1.35 + /// for each element.
1.36 + ///
1.37 + /// The next example shows how can you write the nodes directly
1.38 + /// to the standard output.
1.39 + ///\code
1.40 + /// typedef IdMap<UGraph, UEdge> UEdgeIdMap;
1.41 + /// UEdgeIdMap uedgeId(ugraph);
1.42 + ///
1.43 + /// typedef MapFunctor<UEdgeIdMap> UEdgeIdFunctor;
1.44 + /// UEdgeIdFunctor uedgeIdFunctor(uedgeId);
1.45 + ///
1.46 + /// StoreBoolMap<ostream_iterator<int>, UEdgeIdFunctor>
1.47 + /// writerMap(ostream_iterator<int>(cout, " "), uedgeIdFunctor);
1.48 + ///
1.49 + /// prim(ugraph, cost, writerMap);
1.50 + ///\endcode
1.51 + template <typename _Iterator,
1.52 + typename _Functor =
1.53 + _maps_bits::Identity<typename std::iterator_traits<_Iterator>::value_type> >
1.54 class StoreBoolMap {
1.55 public:
1.56 typedef _Iterator Iterator;
1.57
1.58 - typedef typename std::iterator_traits<Iterator>::value_type Key;
1.59 + typedef typename _Functor::argument_type Key;
1.60 typedef bool Value;
1.61
1.62 + typedef _Functor Functor;
1.63 +
1.64 /// Constructor
1.65 - StoreBoolMap(Iterator it) : _begin(it), _end(it) {}
1.66 + StoreBoolMap(Iterator it, const Functor& functor = Functor())
1.67 + : _begin(it), _end(it), _functor(functor) {}
1.68
1.69 /// Gives back the given first setted iterator.
1.70 Iterator begin() const {
1.71 @@ -1038,12 +1072,13 @@
1.72 /// Setter function of the map
1.73 void set(const Key& key, Value value) {
1.74 if (value) {
1.75 - *_end++ = key;
1.76 + *_end++ = _functor(key);
1.77 }
1.78 }
1.79
1.80 private:
1.81 Iterator _begin, _end;
1.82 + Functor _functor;
1.83 };
1.84
1.85 /// \brief Writable bool map for store each true assigned elements in
1.86 @@ -1051,25 +1086,43 @@
1.87 ///
1.88 /// Writable bool map for store each true assigned elements in a back
1.89 /// insertable container. It will push back all the true setted keys into
1.90 - /// the container.
1.91 - template <typename Container>
1.92 + /// the container. It can be used to retrieve the items into a standard
1.93 + /// container. The next example shows how can you store the undirected
1.94 + /// edges in a vector with prim algorithm.
1.95 + ///
1.96 + ///\code
1.97 + /// vector<UEdge> span_tree_uedges;
1.98 + /// BackInserterBoolMap<vector<UEdge> > inserter_map(span_tree_uedges);
1.99 + /// prim(ugraph, cost, inserter_map);
1.100 + ///
1.101 + /// for (int i = 0; i < (int)span_tree_uedges.size(); ++i) {
1.102 + /// std::cout << ugraph.id(ugraph.source(span_tree_uedges[i])) << ' '
1.103 + /// << ugraph.id(ugraph.target(span_tree_uedges[i])) << ' '
1.104 + /// << cost[span_tree_uedges[i]] << endl;
1.105 + ///\endcode
1.106 + template <typename Container,
1.107 + typename Functor =
1.108 + _maps_bits::Identity<typename Container::value_type> >
1.109 class BackInserterBoolMap {
1.110 public:
1.111 typedef typename Container::value_type Key;
1.112 typedef bool Value;
1.113
1.114 /// Constructor
1.115 - BackInserterBoolMap(Container& _container) : container(_container) {}
1.116 + BackInserterBoolMap(Container& _container,
1.117 + const Functor& _functor = Functor())
1.118 + : container(_container), functor(_functor) {}
1.119
1.120 /// Setter function of the map
1.121 void set(const Key& key, Value value) {
1.122 if (value) {
1.123 - container.push_back(key);
1.124 + container.push_back(functor(key));
1.125 }
1.126 }
1.127
1.128 private:
1.129 - Container& container;
1.130 + Container& container;
1.131 + Functor functor;
1.132 };
1.133
1.134 /// \brief Writable bool map for store each true assigned elements in
1.135 @@ -1077,15 +1130,19 @@
1.136 ///
1.137 /// Writable bool map for store each true assigned elements in a front
1.138 /// insertable container. It will push front all the true setted keys into
1.139 - /// the container.
1.140 - template <typename Container>
1.141 + /// the container. For example see the BackInserterBoolMap.
1.142 + template <typename Container,
1.143 + typename Functor =
1.144 + _maps_bits::Identity<typename Container::value_type> >
1.145 class FrontInserterBoolMap {
1.146 public:
1.147 typedef typename Container::value_type Key;
1.148 typedef bool Value;
1.149
1.150 /// Constructor
1.151 - FrontInserterBoolMap(Container& _container) : container(_container) {}
1.152 + FrontInserterBoolMap(Container& _container,
1.153 + const Functor& _functor = Functor())
1.154 + : container(_container), functor(_functor) {}
1.155
1.156 /// Setter function of the map
1.157 void set(const Key& key, Value value) {
1.158 @@ -1096,6 +1153,7 @@
1.159
1.160 private:
1.161 Container& container;
1.162 + Functor functor;
1.163 };
1.164
1.165 /// \brief Writable bool map for store each true assigned elements in
1.166 @@ -1103,25 +1161,43 @@
1.167 ///
1.168 /// Writable bool map for store each true assigned elements in an
1.169 /// insertable container. It will insert all the true setted keys into
1.170 - /// the container.
1.171 - template <typename Container>
1.172 + /// the container. If you want to store the cut edges of the strongly
1.173 + /// connected components in a set you can use the next code:
1.174 + ///
1.175 + ///\code
1.176 + /// set<Edge> cut_edges;
1.177 + /// InserterBoolMap<set<Edge> > inserter_map(cut_edges);
1.178 + /// stronglyConnectedCutEdges(graph, cost, inserter_map);
1.179 + ///\endcode
1.180 + template <typename Container,
1.181 + typename Functor =
1.182 + _maps_bits::Identity<typename Container::value_type> >
1.183 class InserterBoolMap {
1.184 public:
1.185 typedef typename Container::value_type Key;
1.186 typedef bool Value;
1.187
1.188 /// Constructor
1.189 - InserterBoolMap(Container& _container) : container(_container) {}
1.190 + InserterBoolMap(Container& _container, typename Container::iterator _it,
1.191 + const Functor& _functor = Functor())
1.192 + : container(_container), it(_it), functor(_functor) {}
1.193 +
1.194 + /// Constructor
1.195 + InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1.196 + : container(_container), it(_container.end()), functor(_functor) {}
1.197
1.198 /// Setter function of the map
1.199 void set(const Key& key, Value value) {
1.200 if (value) {
1.201 - container.insert(key);
1.202 + it = container.insert(it, key);
1.203 + ++it;
1.204 }
1.205 }
1.206
1.207 private:
1.208 - Container& container;
1.209 + Container& container;
1.210 + typename Container::iterator it;
1.211 + Functor functor;
1.212 };
1.213
1.214 /// \brief Fill the true setted elements with a given value.
1.215 @@ -1129,6 +1205,27 @@
1.216 /// Writable bool map for fill the true setted elements with a given value.
1.217 /// The value can be setted
1.218 /// the container.
1.219 + ///
1.220 + /// The next code finds the connected components of the undirected graph
1.221 + /// and stores it in the \c comp map:
1.222 + ///\code
1.223 + /// typedef UGraph::NodeMap<int> ComponentMap;
1.224 + /// ComponentMap comp(ugraph);
1.225 + /// typedef FillBoolMap<UGraph::NodeMap<int> > ComponentFillerMap;
1.226 + /// ComponentFillerMap filler(comp, 0);
1.227 + ///
1.228 + /// Dfs<UGraph>::DefProcessedMap<ComponentFillerMap>::Create dfs(ugraph);
1.229 + /// dfs.processedMap(filler);
1.230 + /// dfs.init();
1.231 + /// for (NodeIt it(ugraph); it != INVALID; ++it) {
1.232 + /// if (!dfs.reached(it)) {
1.233 + /// dfs.addSource(it);
1.234 + /// dfs.start();
1.235 + /// ++filler.fillValue();
1.236 + /// }
1.237 + /// }
1.238 + ///\endcode
1.239 +
1.240 template <typename Map>
1.241 class FillBoolMap {
1.242 public:
1.243 @@ -1144,7 +1241,12 @@
1.244 : map(_map), fill() {}
1.245
1.246 /// Gives back the current fill value
1.247 - typename Map::Value fillValue() const {
1.248 + const typename Map::Value& fillValue() const {
1.249 + return fill;
1.250 + }
1.251 +
1.252 + /// Gives back the current fill value
1.253 + typename Map::Value& fillValue() {
1.254 return fill;
1.255 }
1.256
1.257 @@ -1170,7 +1272,53 @@
1.258 /// the setting order number.
1.259 ///
1.260 /// Writable bool map which stores for each true assigned elements
1.261 - /// the setting order number.
1.262 + /// the setting order number. It make easy to calculate the leaving
1.263 + /// order of the nodes in the \ref dfs "Dfs" algorithm.
1.264 + ///
1.265 + ///\code
1.266 + /// typedef Graph::NodeMap<int> OrderMap;
1.267 + /// OrderMap order(graph);
1.268 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1.269 + /// OrderSetterMap setter(order);
1.270 + /// Dfs<Graph>::DefProcessedMap<OrderSetterMap>::Create dfs(graph);
1.271 + /// dfs.processedMap(setter);
1.272 + /// dfs.init();
1.273 + /// for (NodeIt it(graph); it != INVALID; ++it) {
1.274 + /// if (!dfs.reached(it)) {
1.275 + /// dfs.addSource(it);
1.276 + /// dfs.start();
1.277 + /// }
1.278 + /// }
1.279 + ///\endcode
1.280 + ///
1.281 + /// The discovering order can be stored a little harder because the
1.282 + /// ReachedMap should be readable in the dfs algorithm but the setting
1.283 + /// order map is not readable. Now we should use the fork map:
1.284 + ///
1.285 + ///\code
1.286 + /// typedef Graph::NodeMap<int> OrderMap;
1.287 + /// OrderMap order(graph);
1.288 + /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1.289 + /// OrderSetterMap setter(order);
1.290 + /// typedef Graph::NodeMap<bool> StoreMap;
1.291 + /// StoreMap store(graph);
1.292 + ///
1.293 + /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1.294 + /// ReachedMap reached(store, setter);
1.295 + ///
1.296 + /// Dfs<Graph>::DefReachedMap<ReachedMap>::Create dfs(graph);
1.297 + /// dfs.reachedMap(reached);
1.298 + /// dfs.init();
1.299 + /// for (NodeIt it(graph); it != INVALID; ++it) {
1.300 + /// if (!dfs.reached(it)) {
1.301 + /// dfs.addSource(it);
1.302 + /// dfs.start();
1.303 + /// }
1.304 + /// }
1.305 + /// for (NodeIt it(graph); it != INVALID; ++it) {
1.306 + /// cout << graph.id(it) << ' ' << order[it] << endl;
1.307 + /// }
1.308 + ///\endcode
1.309 template <typename Map>
1.310 class SettingOrderBoolMap {
1.311 public: