COIN-OR::LEMON - Graph Library

Ignore:
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r768 r741  
    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 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.
     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.
    19061907  /// The values of the map can be accessed
    19071908  /// with stl compatible forward iterator.
    19081909  ///
    19091910  /// This type is not reference map, so it cannot be modified with
    1910   /// the subscript operator.
     1911  /// the subscription operator.
    19111912  ///
    19121913  /// \tparam GR The graph type.
     
    19241925      template Map<V>::Type Map;
    19251926
    1926     typedef std::multimap<V, K> Container;
     1927    typedef std::map<V, K> Container;
    19271928    Container _inv_map;
    19281929
     
    19491950    /// iterator on the values of the map. The values can
    19501951    /// 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.
    19531952    class ValueIterator
    19541953      : public std::iterator<std::forward_iterator_tag, Value> {
     
    20032002    void set(const Key& key, const Value& val) {
    20042003      Value oldval = Map::operator[](key);
    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         }
     2004      typename Container::iterator it = _inv_map.find(oldval);
     2005      if (it != _inv_map.end() && it->second == key) {
     2006        _inv_map.erase(it);
    20122007      }
    20132008      _inv_map.insert(std::make_pair(val, key));
     
    20232018    }
    20242019
    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);
     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);
    20332025      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);
    20422026    }
    20432027
     
    20502034    virtual void erase(const Key& key) {
    20512035      Value val = Map::operator[](key);
    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         }
     2036      typename Container::iterator it = _inv_map.find(val);
     2037      if (it != _inv_map.end() && it->second == key) {
     2038        _inv_map.erase(it);
    20592039      }
    20602040      Map::erase(key);
     
    20682048      for (int i = 0; i < int(keys.size()); ++i) {
    20692049        Value val = Map::operator[](keys[i]);
    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           }
     2050        typename Container::iterator it = _inv_map.find(val);
     2051        if (it != _inv_map.end() && it->second == keys[i]) {
     2052          _inv_map.erase(it);
    20772053        }
    20782054      }
     
    21102086      /// \brief Subscript operator.
    21112087      ///
    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.
     2088      /// Subscript operator. It gives back the item
     2089      /// that was last assigned to the given value.
    21152090      Value operator[](const Key& key) const {
    21162091        return _inverted(key);
     
    21302105  };
    21312106
    2132   /// \brief Provides continuous and unique id for the
     2107  /// \brief Provides continuous and unique ID for the
    21332108  /// items of a graph.
    21342109  ///
    21352110  /// RangeIdMap provides a unique and continuous
    2136   /// id for each item of a given type (\c Node, \c Arc or
     2111  /// ID for each item of a given type (\c Node, \c Arc or
    21372112  /// \c Edge) in a graph. This id is
    21382113  ///  - \b unique: different items get different ids,
     
    21452120  /// the \c id() function of the graph or \ref IdMap.
    21462121  /// This map can be inverted with its member class \c InverseMap,
    2147   /// or with the \c operator()() member.
     2122  /// or with the \c operator() member.
    21482123  ///
    21492124  /// \tparam GR The graph type.
  • test/maps_test.cc

    r768 r741  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
    25 #include <lemon/list_graph.h>
    2625#include <lemon/smart_graph.h>
    2726
     
    331330  {
    332331    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 
    337332    vec v1;
    338333    vec v2(10);
     
    355350      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    356351  }
    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   }
    497352
    498353  // Iterable bool map
Note: See TracChangeset for help on using the changeset viewer.