COIN-OR::LEMON - Graph Library

Changeset 2091:c8ccc1f8fd51 in lemon-0.x


Ignore:
Timestamp:
05/18/06 10:04:00 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2760
Message:

Functor usage for writeable map adaptors
Documentation for writeable map adaptors

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r2080 r2091  
    2121
    2222#include <iterator>
     23#include <functional>
    2324
    2425#include <lemon/bits/utility.h>
     
    10091010  }
    10101011
     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
    10111024  /// \brief Writable bool map for store each true assigned elements.
    10121025  ///
     
    10141027  /// copies all the true setted keys to the given iterator.
    10151028  ///
    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> >
    10181049  class StoreBoolMap {
    10191050  public:
    10201051    typedef _Iterator Iterator;
    10211052
    1022     typedef typename std::iterator_traits<Iterator>::value_type Key;
     1053    typedef typename _Functor::argument_type Key;
    10231054    typedef bool Value;
    10241055
     1056    typedef _Functor Functor;
     1057
    10251058    /// Constructor
    1026     StoreBoolMap(Iterator it) : _begin(it), _end(it) {}
     1059    StoreBoolMap(Iterator it, const Functor& functor = Functor())
     1060      : _begin(it), _end(it), _functor(functor) {}
    10271061
    10281062    /// Gives back the given first setted iterator.
     
    10391073    void set(const Key& key, Value value) {
    10401074      if (value) {
    1041         *_end++ = key;
     1075        *_end++ = _functor(key);
    10421076      }
    10431077    }
     
    10451079  private:
    10461080    Iterator _begin, _end;
     1081    Functor _functor;
    10471082  };
    10481083
     
    10521087  /// Writable bool map for store each true assigned elements in a back
    10531088  /// 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> >
    10561106  class BackInserterBoolMap {
    10571107  public:
     
    10601110
    10611111    /// Constructor
    1062     BackInserterBoolMap(Container& _container) : container(_container) {}
     1112    BackInserterBoolMap(Container& _container,
     1113                        const Functor& _functor = Functor())
     1114      : container(_container), functor(_functor) {}
    10631115
    10641116    /// Setter function of the map
    10651117    void set(const Key& key, Value value) {
    10661118      if (value) {
    1067         container.push_back(key);
     1119        container.push_back(functor(key));
    10681120      }
    10691121    }
    10701122   
    10711123  private:
    1072     Container& container;   
     1124    Container& container;
     1125    Functor functor;
    10731126  };
    10741127
     
    10781131  /// Writable bool map for store each true assigned elements in a front
    10791132  /// 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> >
    10821137  class FrontInserterBoolMap {
    10831138  public:
     
    10861141
    10871142    /// Constructor
    1088     FrontInserterBoolMap(Container& _container) : container(_container) {}
     1143    FrontInserterBoolMap(Container& _container,
     1144                         const Functor& _functor = Functor())
     1145      : container(_container), functor(_functor) {}
    10891146
    10901147    /// Setter function of the map
     
    10971154  private:
    10981155    Container& container;   
     1156    Functor functor;
    10991157  };
    11001158
     
    11041162  /// Writable bool map for store each true assigned elements in an
    11051163  /// 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> >
    11081175  class InserterBoolMap {
    11091176  public:
     
    11121179
    11131180    /// 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) {}
    11151188
    11161189    /// Setter function of the map
    11171190    void set(const Key& key, Value value) {
    11181191      if (value) {
    1119         container.insert(key);
     1192        it = container.insert(it, key);
     1193        ++it;
    11201194      }
    11211195    }
    11221196   
    11231197  private:
    1124     Container& container;   
     1198    Container& container;
     1199    typename Container::iterator it;
     1200    Functor functor;
    11251201  };
    11261202
     
    11301206  /// The value can be setted
    11311207  /// 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
    11321229  template <typename Map>
    11331230  class FillBoolMap {
     
    11451242
    11461243    /// 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() {
    11481250      return fill;
    11491251    }
     
    11711273  ///
    11721274  /// 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
    11741322  template <typename Map>
    11751323  class SettingOrderBoolMap {
Note: See TracChangeset for help on using the changeset viewer.