COIN-OR::LEMON - Graph Library

Changes in / [694:71939d63ae77:721:99124ea4f048] in lemon-1.2


Ignore:
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r694 r721  
    18261826  /// the items stored in the graph, which is returned by the \c id()
    18271827  /// function of the graph. This map can be inverted with its member
    1828   /// class \c InverseMap or with the \c operator() member.
     1828  /// class \c InverseMap or with the \c operator()() member.
    18291829  ///
    18301830  /// \tparam GR The graph type.
     
    19021902
    19031903  /// This class provides simple invertable graph maps.
    1904   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
    1905   /// and if a key is set to a new value then store it
    1906   /// in the inverse map.
     1904  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
     1905  /// and if a key is set to a new value, then stores it in the inverse map.
    19071906  /// The values of the map can be accessed
    19081907  /// with stl compatible forward iterator.
    19091908  ///
    19101909  /// This type is not reference map, so it cannot be modified with
    1911   /// the subscription operator.
     1910  /// the subscript operator.
    19121911  ///
    19131912  /// \tparam GR The graph type.
     
    19251924      template Map<V>::Type Map;
    19261925
    1927     typedef std::map<V, K> Container;
     1926    typedef std::multimap<V, K> Container;
    19281927    Container _inv_map;
    19291928
     
    19501949    /// iterator on the values of the map. The values can
    19511950    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     1951    /// They are considered with multiplicity, so each value is
     1952    /// traversed for each item it is assigned to.
    19521953    class ValueIterator
    19531954      : public std::iterator<std::forward_iterator_tag, Value> {
     
    20022003    void set(const Key& key, const Value& val) {
    20032004      Value oldval = Map::operator[](key);
    2004       typename Container::iterator it = _inv_map.find(oldval);
    2005       if (it != _inv_map.end() && it->second == key) {
    2006         _inv_map.erase(it);
     2005      typename Container::iterator it;
     2006      for (it = _inv_map.equal_range(oldval).first;
     2007           it != _inv_map.equal_range(oldval).second; ++it) {
     2008        if (it->second == key) {
     2009          _inv_map.erase(it);
     2010          break;
     2011        }
    20072012      }
    20082013      _inv_map.insert(std::make_pair(val, key));
     
    20182023    }
    20192024
    2020     /// \brief Gives back the item by its value.
    2021     ///
    2022     /// Gives back the item by its value.
    2023     Key operator()(const Value& key) const {
    2024       typename Container::const_iterator it = _inv_map.find(key);
     2025    /// \brief Gives back an item by its value.
     2026    ///
     2027    /// This function gives back an item that is assigned to
     2028    /// the given value or \c INVALID if no such item exists.
     2029    /// If there are more items with the same associated value,
     2030    /// only one of them is returned.
     2031    Key operator()(const Value& val) const {
     2032      typename Container::const_iterator it = _inv_map.find(val);
    20252033      return it != _inv_map.end() ? it->second : INVALID;
     2034    }
     2035   
     2036    /// \brief Returns the number of items with the given value.
     2037    ///
     2038    /// This function returns the number of items with the given value
     2039    /// associated with it.
     2040    int count(const Value &val) const {
     2041      return _inv_map.count(val);
    20262042    }
    20272043
     
    20342050    virtual void erase(const Key& key) {
    20352051      Value val = Map::operator[](key);
    2036       typename Container::iterator it = _inv_map.find(val);
    2037       if (it != _inv_map.end() && it->second == key) {
    2038         _inv_map.erase(it);
     2052      typename Container::iterator it;
     2053      for (it = _inv_map.equal_range(val).first;
     2054           it != _inv_map.equal_range(val).second; ++it) {
     2055        if (it->second == key) {
     2056          _inv_map.erase(it);
     2057          break;
     2058        }
    20392059      }
    20402060      Map::erase(key);
     
    20482068      for (int i = 0; i < int(keys.size()); ++i) {
    20492069        Value val = Map::operator[](keys[i]);
    2050         typename Container::iterator it = _inv_map.find(val);
    2051         if (it != _inv_map.end() && it->second == keys[i]) {
    2052           _inv_map.erase(it);
     2070        typename Container::iterator it;
     2071        for (it = _inv_map.equal_range(val).first;
     2072             it != _inv_map.equal_range(val).second; ++it) {
     2073          if (it->second == keys[i]) {
     2074            _inv_map.erase(it);
     2075            break;
     2076          }
    20532077        }
    20542078      }
     
    20862110      /// \brief Subscript operator.
    20872111      ///
    2088       /// Subscript operator. It gives back the item
    2089       /// that was last assigned to the given value.
     2112      /// Subscript operator. It gives back an item
     2113      /// that is assigned to the given value or \c INVALID
     2114      /// if no such item exists.
    20902115      Value operator[](const Key& key) const {
    20912116        return _inverted(key);
     
    21052130  };
    21062131
    2107   /// \brief Provides continuous and unique ID for the
     2132  /// \brief Provides continuous and unique id for the
    21082133  /// items of a graph.
    21092134  ///
    21102135  /// RangeIdMap provides a unique and continuous
    2111   /// ID for each item of a given type (\c Node, \c Arc or
     2136  /// id for each item of a given type (\c Node, \c Arc or
    21122137  /// \c Edge) in a graph. This id is
    21132138  ///  - \b unique: different items get different ids,
     
    21202145  /// the \c id() function of the graph or \ref IdMap.
    21212146  /// This map can be inverted with its member class \c InverseMap,
    2122   /// or with the \c operator() member.
     2147  /// or with the \c operator()() member.
    21232148  ///
    21242149  /// \tparam GR The graph type.
  • test/maps_test.cc

    r694 r721  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
     25#include <lemon/list_graph.h>
    2526#include <lemon/smart_graph.h>
    2627
     
    330331  {
    331332    typedef std::vector<int> vec;
     333    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
     334    checkConcept<WriteMap<int, bool>,
     335                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
     336
    332337    vec v1;
    333338    vec v2(10);
     
    350355      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    351356  }
     357 
     358  // IdMap, RangeIdMap
     359  {
     360    typedef ListDigraph Graph;
     361    DIGRAPH_TYPEDEFS(Graph);
     362
     363    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
     364    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
     365    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
     366    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
     367   
     368    Graph gr;
     369    IdMap<Graph, Node> nmap(gr);
     370    IdMap<Graph, Arc> amap(gr);
     371    RangeIdMap<Graph, Node> nrmap(gr);
     372    RangeIdMap<Graph, Arc> armap(gr);
     373   
     374    Node n0 = gr.addNode();
     375    Node n1 = gr.addNode();
     376    Node n2 = gr.addNode();
     377   
     378    Arc a0 = gr.addArc(n0, n1);
     379    Arc a1 = gr.addArc(n0, n2);
     380    Arc a2 = gr.addArc(n2, n1);
     381    Arc a3 = gr.addArc(n2, n0);
     382   
     383    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
     384    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
     385    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");
     386
     387    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");
     388    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");
     389    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");
     390    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");
     391
     392    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
     393    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
     394   
     395    check(nrmap.size() == 3 && armap.size() == 4,
     396          "Wrong RangeIdMap::size()");
     397
     398    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");
     399    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
     400    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
     401   
     402    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
     403    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     404    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");
     405    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");
     406
     407    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
     408    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
     409   
     410    gr.erase(n1);
     411   
     412    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
     413    nrmap.swap(n2, n0);
     414    if (armap[a1] == 1) armap.swap(a1, a3);
     415    armap.swap(a3, a1);
     416   
     417    check(nrmap.size() == 2 && armap.size() == 2,
     418          "Wrong RangeIdMap::size()");
     419
     420    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
     421    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
     422   
     423    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     424    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
     425
     426    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");
     427    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
     428  }
     429 
     430  // CrossRefMap
     431  {
     432    typedef ListDigraph Graph;
     433    DIGRAPH_TYPEDEFS(Graph);
     434
     435    checkConcept<ReadWriteMap<Node, int>,
     436                 CrossRefMap<Graph, Node, int> >();
     437    checkConcept<ReadWriteMap<Node, bool>,
     438                 CrossRefMap<Graph, Node, bool> >();
     439    checkConcept<ReadWriteMap<Node, double>,
     440                 CrossRefMap<Graph, Node, double> >();
     441   
     442    Graph gr;
     443    typedef CrossRefMap<Graph, Node, char> CRMap;
     444    typedef CRMap::ValueIterator ValueIt;
     445    CRMap map(gr);
     446   
     447    Node n0 = gr.addNode();
     448    Node n1 = gr.addNode();
     449    Node n2 = gr.addNode();
     450   
     451    map.set(n0, 'A');
     452    map.set(n1, 'B');
     453    map.set(n2, 'C');
     454   
     455    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
     456          "Wrong CrossRefMap");
     457    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,
     458          "Wrong CrossRefMap");
     459    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,
     460          "Wrong CrossRefMap");
     461    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
     462          "Wrong CrossRefMap::count()");
     463   
     464    ValueIt it = map.beginValue();
     465    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     466          it == map.endValue(), "Wrong value iterator");
     467   
     468    map.set(n2, 'A');
     469
     470    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',
     471          "Wrong CrossRefMap");
     472    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");
     473    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     474    check(map('C') == INVALID && map.inverse()['C'] == INVALID,
     475          "Wrong CrossRefMap");
     476    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,
     477          "Wrong CrossRefMap::count()");
     478
     479    it = map.beginValue();
     480    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&
     481          it == map.endValue(), "Wrong value iterator");
     482
     483    map.set(n0, 'C');
     484
     485    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
     486          "Wrong CrossRefMap");
     487    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
     488    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     489    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
     490    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
     491          "Wrong CrossRefMap::count()");
     492
     493    it = map.beginValue();
     494    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     495          it == map.endValue(), "Wrong value iterator");
     496  }
    352497
    353498  // Iterable bool map
Note: See TracChangeset for help on using the changeset viewer.