COIN-OR::LEMON - Graph Library

Changeset 767:6e8c27ee9079 in lemon


Ignore:
Timestamp:
07/23/09 18:13:59 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Improvements for graph maps (#302)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r731 r767  
    18271827  /// the items stored in the graph, which is returned by the \c id() 
    18281828  /// function of the graph. This map can be inverted with its member 
    1829   /// class \c InverseMap or with the \c operator() member. 
     1829  /// class \c InverseMap or with the \c operator()() member. 
    18301830  /// 
    18311831  /// \tparam GR The graph type. 
     
    20332033      typename Container::const_iterator it = _inv_map.find(val); 
    20342034      return it != _inv_map.end() ? it->second : INVALID; 
     2035    } 
     2036     
     2037    /// \brief Returns the number of items with the given value. 
     2038    /// 
     2039    /// This function returns the number of items with the given value 
     2040    /// associated with it. 
     2041    int count(const Value &val) const { 
     2042      return _inv_map.count(val); 
    20352043    } 
    20362044 
     
    21232131  }; 
    21242132 
    2125   /// \brief Provides continuous and unique ID for the 
     2133  /// \brief Provides continuous and unique id for the 
    21262134  /// items of a graph. 
    21272135  /// 
    21282136  /// RangeIdMap provides a unique and continuous 
    2129   /// ID for each item of a given type (\c Node, \c Arc or 
     2137  /// id for each item of a given type (\c Node, \c Arc or 
    21302138  /// \c Edge) in a graph. This id is 
    21312139  ///  - \b unique: different items get different ids, 
     
    21382146  /// the \c id() function of the graph or \ref IdMap. 
    21392147  /// This map can be inverted with its member class \c InverseMap, 
    2140   /// or with the \c operator() member. 
     2148  /// or with the \c operator()() member. 
    21412149  /// 
    21422150  /// \tparam GR The graph type. 
  • test/maps_test.cc

    r731 r767  
    330330  { 
    331331    typedef std::vector<int> vec; 
     332    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >(); 
     333    checkConcept<WriteMap<int, bool>, 
     334                 LoggerBoolMap<std::back_insert_iterator<vec> > >(); 
     335 
    332336    vec v1; 
    333337    vec v2(10); 
     
    351355  } 
    352356   
    353   // CrossRefMap 
     357  // IdMap, RangeIdMap 
    354358  { 
    355359    typedef ListDigraph Graph; 
    356360    DIGRAPH_TYPEDEFS(Graph); 
    357361 
     362    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >(); 
     363    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >(); 
     364    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >(); 
     365    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >(); 
     366     
     367    Graph gr; 
     368    IdMap<Graph, Node> nmap(gr); 
     369    IdMap<Graph, Arc> amap(gr); 
     370    RangeIdMap<Graph, Node> nrmap(gr); 
     371    RangeIdMap<Graph, Arc> armap(gr); 
     372     
     373    Node n0 = gr.addNode(); 
     374    Node n1 = gr.addNode(); 
     375    Node n2 = gr.addNode(); 
     376     
     377    Arc a0 = gr.addArc(n0, n1); 
     378    Arc a1 = gr.addArc(n0, n2); 
     379    Arc a2 = gr.addArc(n2, n1); 
     380    Arc a3 = gr.addArc(n2, n0); 
     381     
     382    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap"); 
     383    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap"); 
     384    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap"); 
     385 
     386    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap"); 
     387    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap"); 
     388    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap"); 
     389    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap"); 
     390 
     391    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap"); 
     392    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap"); 
     393     
     394    check(nrmap.size() == 3 && armap.size() == 4, 
     395          "Wrong RangeIdMap::size()"); 
     396 
     397    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap"); 
     398    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap"); 
     399    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap"); 
     400     
     401    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap"); 
     402    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); 
     403    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap"); 
     404    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap"); 
     405 
     406    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap"); 
     407    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap"); 
     408     
     409    gr.erase(n1); 
     410     
     411    if (nrmap[n0] == 1) nrmap.swap(n0, n2); 
     412    nrmap.swap(n2, n0); 
     413    if (armap[a1] == 1) armap.swap(a1, a3); 
     414    armap.swap(a3, a1); 
     415     
     416    check(nrmap.size() == 2 && armap.size() == 2, 
     417          "Wrong RangeIdMap::size()"); 
     418 
     419    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap"); 
     420    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap"); 
     421     
     422    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); 
     423    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap"); 
     424 
     425    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap"); 
     426    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap"); 
     427  } 
     428   
     429  // CrossRefMap 
     430  { 
     431    typedef ListDigraph Graph; 
     432    DIGRAPH_TYPEDEFS(Graph); 
     433 
    358434    checkConcept<ReadWriteMap<Node, int>, 
    359435                 CrossRefMap<Graph, Node, int> >(); 
     436    checkConcept<ReadWriteMap<Node, bool>, 
     437                 CrossRefMap<Graph, Node, bool> >(); 
     438    checkConcept<ReadWriteMap<Node, double>, 
     439                 CrossRefMap<Graph, Node, double> >(); 
    360440     
    361441    Graph gr; 
     
    371451    map.set(n1, 'B'); 
    372452    map.set(n2, 'C'); 
     453     
     454    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0, 
     455          "Wrong CrossRefMap"); 
     456    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1, 
     457          "Wrong CrossRefMap"); 
     458    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2, 
     459          "Wrong CrossRefMap"); 
     460    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, 
     461          "Wrong CrossRefMap::count()"); 
     462     
     463    ValueIt it = map.beginValue(); 
     464    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && 
     465          it == map.endValue(), "Wrong value iterator"); 
     466     
    373467    map.set(n2, 'A'); 
     468 
     469    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A', 
     470          "Wrong CrossRefMap"); 
     471    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap"); 
     472    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); 
     473    check(map('C') == INVALID && map.inverse()['C'] == INVALID, 
     474          "Wrong CrossRefMap"); 
     475    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0, 
     476          "Wrong CrossRefMap::count()"); 
     477 
     478    it = map.beginValue(); 
     479    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' && 
     480          it == map.endValue(), "Wrong value iterator"); 
     481 
    374482    map.set(n0, 'C'); 
    375483 
     
    379487    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); 
    380488    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap"); 
    381  
    382     ValueIt it = map.beginValue(); 
     489    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, 
     490          "Wrong CrossRefMap::count()"); 
     491 
     492    it = map.beginValue(); 
    383493    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && 
    384494          it == map.endValue(), "Wrong value iterator"); 
Note: See TracChangeset for help on using the changeset viewer.