lemon-0.x: comparison lemon/maps.h

equal deleted inserted replaced

-:16dc7328937c
+:d6b9d90afaa3
 #ifndef LEMON_MAPS_H
 #define LEMON_MAPS_H
 #include <iterator>
+#include <functional>
 #include <lemon/bits/utility.h>
 #include <lemon/bits/traits.h>
 ///\file
 template <typename M>
 inline NotWriteMap<M> notMap(M &m) {
 return NotWriteMap<M>(m);
 }
+namespace _maps_bits {
+template <typename Value>
+struct Identity {
+typedef Value argument_type;
+typedef Value result_type;
+Value operator()(const Value& val) {
+	return val;
+}
+};
+}
 /// \brief Writable bool map for store each true assigned elements.
 ///
 /// Writable bool map for store each true assigned elements. It will
 /// copies all the true setted keys to the given iterator.
 ///
-/// \note The container of the iterator should contain for each element.
+/// \note The container of the iterator should contain space
-template <typename _Iterator>
+/// for each element.
+///
+/// The next example shows how can you write the nodes directly
+/// to the standard output.
+///\code
+/// typedef IdMap<UGraph, UEdge> UEdgeIdMap;
+/// UEdgeIdMap uedgeId(ugraph);
+///
+/// typedef MapFunctor<UEdgeIdMap> UEdgeIdFunctor;
+/// UEdgeIdFunctor uedgeIdFunctor(uedgeId);
+///
+/// StoreBoolMap<ostream_iterator<int>, UEdgeIdFunctor>
+///   writerMap(ostream_iterator<int>(cout, " "), uedgeIdFunctor);
+///
+/// prim(ugraph, cost, writerMap);
+///\endcode
+template <typename _Iterator,
+typename _Functor =
+_maps_bits::Identity<typename std::iterator_traits<_Iterator>::value_type> >
 class StoreBoolMap {
 public:
 typedef _Iterator Iterator;
-typedef typename std::iterator_traits<Iterator>::value_type Key;
+typedef typename _Functor::argument_type Key;
 typedef bool Value;
+typedef _Functor Functor;
 /// Constructor
-StoreBoolMap(Iterator it) : _begin(it), _end(it) {}
+StoreBoolMap(Iterator it, const Functor& functor = Functor())
+: _begin(it), _end(it), _functor(functor) {}
 /// Gives back the given first setted iterator.
 Iterator begin() const {
 return _begin;
 }
 }
 /// Setter function of the map
 void set(const Key& key, Value value) {
 if (value) {
-	*_end++ = key;
+	*_end++ = _functor(key);
 }
 }
 private:
 Iterator _begin, _end;
+Functor _functor;
 };
 /// \brief Writable bool map for store each true assigned elements in
 /// a back insertable container.
 ///
 /// Writable bool map for store each true assigned elements in a back
 /// insertable container. It will push back all the true setted keys into
-/// the container.
+/// the container. It can be used to retrieve the items into a standard
-template <typename Container>
+/// container. The next example shows how can you store the undirected
+/// edges in a vector with prim algorithm.
+///
+///\code
+/// vector<UEdge> span_tree_uedges;
+/// BackInserterBoolMap<vector<UEdge> > inserter_map(span_tree_uedges);
+/// prim(ugraph, cost, inserter_map);
+///
+/// for (int i = 0; i < (int)span_tree_uedges.size(); ++i) {
+/// std::cout << ugraph.id(ugraph.source(span_tree_uedges[i])) << ' '
+///           << ugraph.id(ugraph.target(span_tree_uedges[i])) << ' '
+///           << cost[span_tree_uedges[i]] << endl;
+///\endcode
+template <typename Container,
+typename Functor =
+_maps_bits::Identity<typename Container::value_type> >
 class BackInserterBoolMap {
 public:
 typedef typename Container::value_type Key;
 typedef bool Value;
 /// Constructor
-BackInserterBoolMap(Container& _container) : container(_container) {}
+BackInserterBoolMap(Container& _container,
+const Functor& _functor = Functor())
+: container(_container), functor(_functor) {}
 /// Setter function of the map
 void set(const Key& key, Value value) {
 if (value) {
-	container.push_back(key);
+	container.push_back(functor(key));
 }
 }
 private:
 Container& container;
+Functor functor;
 };
 /// \brief Writable bool map for store each true assigned elements in
 /// a front insertable container.
 ///
 /// Writable bool map for store each true assigned elements in a front
 /// insertable container. It will push front all the true setted keys into
-/// the container.
+/// the container. For example see the BackInserterBoolMap.
-template <typename Container>
+template <typename Container,
+typename Functor =
+_maps_bits::Identity<typename Container::value_type> >
 class FrontInserterBoolMap {
 public:
 typedef typename Container::value_type Key;
 typedef bool Value;
 /// Constructor
-FrontInserterBoolMap(Container& _container) : container(_container) {}
+FrontInserterBoolMap(Container& _container,
+const Functor& _functor = Functor())
+: container(_container), functor(_functor) {}
 /// Setter function of the map
 void set(const Key& key, Value value) {
 if (value) {
 	container.push_front(key);
 }
 }
 private:
 Container& container;
+Functor functor;
 };
 /// \brief Writable bool map for store each true assigned elements in
 /// an insertable container.
 ///
 /// Writable bool map for store each true assigned elements in an
 /// insertable container. It will insert all the true setted keys into
-/// the container.
+/// the container. If you want to store the cut edges of the strongly
-template <typename Container>
+/// connected components in a set you can use the next code:
+///
+///\code
+/// set<Edge> cut_edges;
+/// InserterBoolMap<set<Edge> > inserter_map(cut_edges);
+/// stronglyConnectedCutEdges(graph, cost, inserter_map);
+///\endcode
+template <typename Container,
+typename Functor =
+_maps_bits::Identity<typename Container::value_type> >
 class InserterBoolMap {
 public:
 typedef typename Container::value_type Key;
 typedef bool Value;
 /// Constructor
-InserterBoolMap(Container& _container) : container(_container) {}
+InserterBoolMap(Container& _container, typename Container::iterator _it,
+const Functor& _functor = Functor())
+: container(_container), it(_it), functor(_functor) {}
+/// Constructor
+InserterBoolMap(Container& _container, const Functor& _functor = Functor())
+: container(_container), it(_container.end()), functor(_functor) {}
 /// Setter function of the map
 void set(const Key& key, Value value) {
 if (value) {
-	container.insert(key);
+	it = container.insert(it, key);
+++it;
 }
 }
 private:
 Container& container;
+typename Container::iterator it;
+Functor functor;
 };
 /// \brief Fill the true setted elements with a given value.
 ///
 /// Writable bool map for fill the true setted elements with a given value.
 /// The value can be setted
 /// the container.
+///
+/// The next code finds the connected components of the undirected graph
+/// and stores it in the \c comp map:
+///\code
+/// typedef UGraph::NodeMap<int> ComponentMap;
+/// ComponentMap comp(ugraph);
+/// typedef FillBoolMap<UGraph::NodeMap<int> > ComponentFillerMap;
+/// ComponentFillerMap filler(comp, 0);
+///
+/// Dfs<UGraph>::DefProcessedMap<ComponentFillerMap>::Create dfs(ugraph);
+/// dfs.processedMap(filler);
+/// dfs.init();
+/// for (NodeIt it(ugraph); it != INVALID; ++it) {
+///   if (!dfs.reached(it)) {
+///     dfs.addSource(it);
+///     dfs.start();
+///     ++filler.fillValue();
+///   }
+/// }
+///\endcode
 template <typename Map>
 class FillBoolMap {
 public:
 typedef typename Map::Key Key;
 typedef bool Value;
 /// Constructor
 FillBoolMap(Map& _map)
 : map(_map), fill() {}
 /// Gives back the current fill value
-typename Map::Value fillValue() const {
+const typename Map::Value& fillValue() const {
+return fill;
+}
+/// Gives back the current fill value
+typename Map::Value& fillValue() {
 return fill;
 }
 /// Sets the current fill value
 void fillValue(const typename Map::Value& _fill) {
 /// \brief Writable bool map which stores for each true assigned elements
 /// the setting order number.
 ///
 /// Writable bool map which stores for each true assigned elements
-/// the setting order number.
+/// the setting order number. It make easy to calculate the leaving
+/// order of the nodes in the \ref dfs "Dfs" algorithm.
+///
+///\code
+/// typedef Graph::NodeMap<int> OrderMap;
+/// OrderMap order(graph);
+/// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
+/// OrderSetterMap setter(order);
+/// Dfs<Graph>::DefProcessedMap<OrderSetterMap>::Create dfs(graph);
+/// dfs.processedMap(setter);
+/// dfs.init();
+/// for (NodeIt it(graph); it != INVALID; ++it) {
+///   if (!dfs.reached(it)) {
+///     dfs.addSource(it);
+///     dfs.start();
+///   }
+/// }
+///\endcode
+///
+/// The discovering order can be stored a little harder because the
+/// ReachedMap should be readable in the dfs algorithm but the setting
+/// order map is not readable. Now we should use the fork map:
+///
+///\code
+/// typedef Graph::NodeMap<int> OrderMap;
+/// OrderMap order(graph);
+/// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
+/// OrderSetterMap setter(order);
+/// typedef Graph::NodeMap<bool> StoreMap;
+/// StoreMap store(graph);
+///
+/// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
+/// ReachedMap reached(store, setter);
+///
+/// Dfs<Graph>::DefReachedMap<ReachedMap>::Create dfs(graph);
+/// dfs.reachedMap(reached);
+/// dfs.init();
+/// for (NodeIt it(graph); it != INVALID; ++it) {
+///   if (!dfs.reached(it)) {
+///     dfs.addSource(it);
+///     dfs.start();
+///   }
+/// }
+/// for (NodeIt it(graph); it != INVALID; ++it) {
+///   cout << graph.id(it) << ' ' << order[it] << endl;
+/// }
+///\endcode
 template <typename Map>
 class SettingOrderBoolMap {
 public:
 typedef typename Map::Key Key;
 typedef bool Value;

changeset 2091	c8ccc1f8fd51
parent 2080	630a5e16dc12
child 2093	ff241247e157