COIN-OR::LEMON - Graph Library

Changeset 773:3fc2a801c39e in lemon


Ignore:
Timestamp:
09/26/09 07:08:10 (14 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
772:11404088d1a5 (diff), 766:ba79e8d64448 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #302

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/maps.h

    r764 r773  
    5757  /// but data written to it is not required (i.e. it will be sent to
    5858  /// <tt>/dev/null</tt>).
    59   /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     59  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    6060  ///
    6161  /// \sa ConstMap
     
    9090  ///
    9191  /// In other aspects it is equivalent to \c NullMap.
    92   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
     92  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
    9393  /// concept, but it absorbs the data written to it.
    9494  ///
     
    159159  ///
    160160  /// In other aspects it is equivalent to \c NullMap.
    161   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
     161  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
    162162  /// concept, but it absorbs the data written to it.
    163163  ///
     
    233233  /// It can be used with some data structures, for example
    234234  /// \c UnionFind, \c BinHeap, when the used items are small
    235   /// integers. This map conforms the \ref concepts::ReferenceMap
     235  /// integers. This map conforms to the \ref concepts::ReferenceMap
    236236  /// "ReferenceMap" concept.
    237237  ///
     
    341341  /// stored actually. This value can be different from the default
    342342  /// contructed value (i.e. \c %Value()).
    343   /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
     343  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
    344344  /// concept.
    345345  ///
     
    707707  /// The \c Key type of it is inherited from \c M and the \c Value
    708708  /// type is \c V.
    709   /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
     709  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    710710  ///
    711711  /// The simplest way of using this map is through the convertMap()
     
    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.
     
    18661866  public:
    18671867
    1868     /// \brief This class represents the inverse of its owner (IdMap).
    1869     ///
    1870     /// This class represents the inverse of its owner (IdMap).
     1868    /// \brief The inverse map type of IdMap.
     1869    ///
     1870    /// The inverse map type of IdMap. The subscript operator gives back
     1871    /// an item by its id.
     1872    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    18711873    /// \see inverse()
    18721874    class InverseMap {
     
    18831885      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
    18841886
    1885       /// \brief Gives back the given item from its id.
     1887      /// \brief Gives back an item by its id.
    18861888      ///
    1887       /// Gives back the given item from its id.
     1889      /// Gives back an item by its id.
    18881890      Item operator[](int id) const { return _graph->fromId(id, Item());}
    18891891
     
    18981900  };
    18991901
     1902  /// \brief Returns an \c IdMap class.
     1903  ///
     1904  /// This function just returns an \c IdMap class.
     1905  /// \relates IdMap
     1906  template <typename K, typename GR>
     1907  inline IdMap<GR, K> idMap(const GR& graph) {
     1908    return IdMap<GR, K>(graph);
     1909  }
    19001910
    19011911  /// \brief General cross reference graph map type.
     
    19041914  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
    19051915  /// and if a key is set to a new value, then stores it in the inverse map.
    1906   /// The values of the map can be accessed
    1907   /// with stl compatible forward iterator.
     1916  /// The graph items can be accessed by their values either using
     1917  /// \c InverseMap or \c operator()(), and the values of the map can be
     1918  /// accessed with an STL compatible forward iterator (\c ValueIt).
     1919  ///
     1920  /// This map is intended to be used when all associated values are
     1921  /// different (the map is actually invertable) or there are only a few
     1922  /// items with the same value.
     1923  /// Otherwise consider to use \c IterableValueMap, which is more
     1924  /// suitable and more efficient for such cases. It provides iterators
     1925  /// to traverse the items with the same associated value, however
     1926  /// it does not have \c InverseMap.
    19081927  ///
    19091928  /// This type is not reference map, so it cannot be modified with
     
    19461965    /// \brief Forward iterator for values.
    19471966    ///
    1948     /// This iterator is an stl compatible forward
     1967    /// This iterator is an STL compatible forward
    19491968    /// iterator on the values of the map. The values can
    19501969    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    19511970    /// They are considered with multiplicity, so each value is
    19521971    /// traversed for each item it is assigned to.
    1953     class ValueIterator
     1972    class ValueIt
    19541973      : public std::iterator<std::forward_iterator_tag, Value> {
    19551974      friend class CrossRefMap;
    19561975    private:
    1957       ValueIterator(typename Container::const_iterator _it)
     1976      ValueIt(typename Container::const_iterator _it)
    19581977        : it(_it) {}
    19591978    public:
    19601979
    1961       ValueIterator() {}
    1962 
    1963       ValueIterator& operator++() { ++it; return *this; }
    1964       ValueIterator operator++(int) {
    1965         ValueIterator tmp(*this);
     1980      /// Constructor
     1981      ValueIt() {}
     1982
     1983      /// \e
     1984      ValueIt& operator++() { ++it; return *this; }
     1985      /// \e
     1986      ValueIt operator++(int) {
     1987        ValueIt tmp(*this);
    19661988        operator++();
    19671989        return tmp;
    19681990      }
    19691991
     1992      /// \e
    19701993      const Value& operator*() const { return it->first; }
     1994      /// \e
    19711995      const Value* operator->() const { return &(it->first); }
    19721996
    1973       bool operator==(ValueIterator jt) const { return it == jt.it; }
    1974       bool operator!=(ValueIterator jt) const { return it != jt.it; }
     1997      /// \e
     1998      bool operator==(ValueIt jt) const { return it == jt.it; }
     1999      /// \e
     2000      bool operator!=(ValueIt jt) const { return it != jt.it; }
    19752001
    19762002    private:
    19772003      typename Container::const_iterator it;
    19782004    };
     2005   
     2006    /// Alias for \c ValueIt
     2007    typedef ValueIt ValueIterator;
    19792008
    19802009    /// \brief Returns an iterator to the first value.
    19812010    ///
    1982     /// Returns an stl compatible iterator to the
     2011    /// Returns an STL compatible iterator to the
    19832012    /// first value of the map. The values of the
    19842013    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    19852014    /// range.
    1986     ValueIterator beginValue() const {
    1987       return ValueIterator(_inv_map.begin());
     2015    ValueIt beginValue() const {
     2016      return ValueIt(_inv_map.begin());
    19882017    }
    19892018
    19902019    /// \brief Returns an iterator after the last value.
    19912020    ///
    1992     /// Returns an stl compatible iterator after the
     2021    /// Returns an STL compatible iterator after the
    19932022    /// last value of the map. The values of the
    19942023    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    19952024    /// range.
    1996     ValueIterator endValue() const {
    1997       return ValueIterator(_inv_map.end());
     2025    ValueIt endValue() const {
     2026      return ValueIt(_inv_map.end());
    19982027    }
    19992028
     
    20322061      typename Container::const_iterator it = _inv_map.find(val);
    20332062      return it != _inv_map.end() ? it->second : INVALID;
     2063    }
     2064   
     2065    /// \brief Returns the number of items with the given value.
     2066    ///
     2067    /// This function returns the number of items with the given value
     2068    /// associated with it.
     2069    int count(const Value &val) const {
     2070      return _inv_map.count(val);
    20342071    }
    20352072
     
    20832120  public:
    20842121
    2085     /// \brief The inverse map type.
    2086     ///
    2087     /// The inverse of this map. The subscript operator of the map
    2088     /// gives back the item that was last assigned to the value.
     2122    /// \brief The inverse map type of CrossRefMap.
     2123    ///
     2124    /// The inverse map type of CrossRefMap. The subscript operator gives
     2125    /// back an item by its value.
     2126    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
     2127    /// \see inverse()
    20892128    class InverseMap {
    20902129    public:
     
    21132152    };
    21142153
    2115     /// \brief It gives back the read-only inverse map.
    2116     ///
    2117     /// It gives back the read-only inverse map.
     2154    /// \brief Gives back the inverse of the map.
     2155    ///
     2156    /// Gives back the inverse of the CrossRefMap.
    21182157    InverseMap inverse() const {
    21192158      return InverseMap(*this);
     
    21222161  };
    21232162
    2124   /// \brief Provides continuous and unique ID for the
     2163  /// \brief Provides continuous and unique id for the
    21252164  /// items of a graph.
    21262165  ///
    21272166  /// RangeIdMap provides a unique and continuous
    2128   /// ID for each item of a given type (\c Node, \c Arc or
     2167  /// id for each item of a given type (\c Node, \c Arc or
    21292168  /// \c Edge) in a graph. This id is
    21302169  ///  - \b unique: different items get different ids,
     
    21372176  /// the \c id() function of the graph or \ref IdMap.
    21382177  /// This map can be inverted with its member class \c InverseMap,
    2139   /// or with the \c operator() member.
     2178  /// or with the \c operator()() member.
    21402179  ///
    21412180  /// \tparam GR The graph type.
     
    22652304    }
    22662305
    2267     /// \brief Gives back the \e RangeId of the item
    2268     ///
    2269     /// Gives back the \e RangeId of the item.
     2306    /// \brief Gives back the \e range \e id of the item
     2307    ///
     2308    /// Gives back the \e range \e id of the item.
    22702309    int operator[](const Item& item) const {
    22712310      return Map::operator[](item);
    22722311    }
    22732312
    2274     /// \brief Gives back the item belonging to a \e RangeId
    2275     ///
    2276     /// Gives back the item belonging to a \e RangeId.
     2313    /// \brief Gives back the item belonging to a \e range \e id
     2314    ///
     2315    /// Gives back the item belonging to the given \e range \e id.
    22772316    Item operator()(int id) const {
    22782317      return _inv_map[id];
     
    22882327    /// \brief The inverse map type of RangeIdMap.
    22892328    ///
    2290     /// The inverse map type of RangeIdMap.
     2329    /// The inverse map type of RangeIdMap. The subscript operator gives
     2330    /// back an item by its \e range \e id.
     2331    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    22912332    class InverseMap {
    22922333    public:
     
    23062347      ///
    23072348      /// Subscript operator. It gives back the item
    2308       /// that the descriptor currently belongs to.
     2349      /// that the given \e range \e id currently belongs to.
    23092350      Value operator[](const Key& key) const {
    23102351        return _inverted(key);
     
    23242365    /// \brief Gives back the inverse of the map.
    23252366    ///
    2326     /// Gives back the inverse of the map.
     2367    /// Gives back the inverse of the RangeIdMap.
    23272368    const InverseMap inverse() const {
    23282369      return InverseMap(*this);
     
    23302371  };
    23312372
     2373  /// \brief Returns a \c RangeIdMap class.
     2374  ///
     2375  /// This function just returns an \c RangeIdMap class.
     2376  /// \relates RangeIdMap
     2377  template <typename K, typename GR>
     2378  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
     2379    return RangeIdMap<GR, K>(graph);
     2380  }
     2381 
    23322382  /// \brief Dynamic iterable \c bool map.
    23332383  ///
     
    23352385  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
    23362386  /// For both \c true and \c false values it is possible to iterate on
    2337   /// the keys.
     2387  /// the keys mapped to the value.
    23382388  ///
    23392389  /// This type is a reference map, so it can be modified with the
     
    27042754  /// mapped to the value.
    27052755  ///
     2756  /// This map is intended to be used with small integer values, for which
     2757  /// it is efficient, and supports iteration only for non-negative values.
     2758  /// If you need large values and/or iteration for negative integers,
     2759  /// consider to use \ref IterableValueMap instead.
     2760  ///
    27062761  /// This type is a reference map, so it can be modified with the
    27072762  /// subscript operator.
     
    29853040  /// \brief Dynamic iterable map for comparable values.
    29863041  ///
    2987   /// This class provides a special graph map type which can store an
     3042  /// This class provides a special graph map type which can store a
    29883043  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
    29893044  /// For each value it is possible to iterate on the keys mapped to
    2990   /// the value.
    2991   ///
    2992   /// The map stores for each value a linked list with
    2993   /// the items which mapped to the value, and the values are stored
    2994   /// in balanced binary tree. The values of the map can be accessed
    2995   /// with stl compatible forward iterator.
     3045  /// the value (\c ItemIt), and the values of the map can be accessed
     3046  /// with an STL compatible forward iterator (\c ValueIt).
     3047  /// The map stores a linked list for each value, which contains
     3048  /// the items mapped to the value, and the used values are stored
     3049  /// in balanced binary tree (\c std::map).
     3050  ///
     3051  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
     3052  /// specialized for \c bool and \c int values, respectively.
    29963053  ///
    29973054  /// This type is not reference map, so it cannot be modified with
     
    30723129    /// \brief Forward iterator for values.
    30733130    ///
    3074     /// This iterator is an stl compatible forward
     3131    /// This iterator is an STL compatible forward
    30753132    /// iterator on the values of the map. The values can
    30763133    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    3077     class ValueIterator
     3134    class ValueIt
    30783135      : public std::iterator<std::forward_iterator_tag, Value> {
    30793136      friend class IterableValueMap;
    30803137    private:
    3081       ValueIterator(typename std::map<Value, Key>::const_iterator _it)
     3138      ValueIt(typename std::map<Value, Key>::const_iterator _it)
    30823139        : it(_it) {}
    30833140    public:
    30843141
    3085       ValueIterator() {}
    3086 
    3087       ValueIterator& operator++() { ++it; return *this; }
    3088       ValueIterator operator++(int) {
    3089         ValueIterator tmp(*this);
     3142      /// Constructor
     3143      ValueIt() {}
     3144
     3145      /// \e
     3146      ValueIt& operator++() { ++it; return *this; }
     3147      /// \e
     3148      ValueIt operator++(int) {
     3149        ValueIt tmp(*this);
    30903150        operator++();
    30913151        return tmp;
    30923152      }
    30933153
     3154      /// \e
    30943155      const Value& operator*() const { return it->first; }
     3156      /// \e
    30953157      const Value* operator->() const { return &(it->first); }
    30963158
    3097       bool operator==(ValueIterator jt) const { return it == jt.it; }
    3098       bool operator!=(ValueIterator jt) const { return it != jt.it; }
     3159      /// \e
     3160      bool operator==(ValueIt jt) const { return it == jt.it; }
     3161      /// \e
     3162      bool operator!=(ValueIt jt) const { return it != jt.it; }
    30993163
    31003164    private:
     
    31043168    /// \brief Returns an iterator to the first value.
    31053169    ///
    3106     /// Returns an stl compatible iterator to the
     3170    /// Returns an STL compatible iterator to the
    31073171    /// first value of the map. The values of the
    31083172    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    31093173    /// range.
    3110     ValueIterator beginValue() const {
    3111       return ValueIterator(_first.begin());
     3174    ValueIt beginValue() const {
     3175      return ValueIt(_first.begin());
    31123176    }
    31133177
    31143178    /// \brief Returns an iterator after the last value.
    31153179    ///
    3116     /// Returns an stl compatible iterator after the
     3180    /// Returns an STL compatible iterator after the
    31173181    /// last value of the map. The values of the
    31183182    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    31193183    /// range.
    3120     ValueIterator endValue() const {
    3121       return ValueIterator(_first.end());
     3184    ValueIt endValue() const {
     3185      return ValueIt(_first.end());
    31223186    }
    31233187
     
    32373301  public:
    32383302
    3239     ///\e
     3303    /// The key type (the \c Arc type of the digraph).
    32403304    typedef typename GR::Arc Key;
    3241     ///\e
     3305    /// The value type (the \c Node type of the digraph).
    32423306    typedef typename GR::Node Value;
    32433307
     
    32783342  public:
    32793343
    3280     ///\e
     3344    /// The key type (the \c Arc type of the digraph).
    32813345    typedef typename GR::Arc Key;
    3282     ///\e
     3346    /// The value type (the \c Node type of the digraph).
    32833347    typedef typename GR::Node Value;
    32843348
     
    33203384  public:
    33213385
     3386    /// The key type (the \c Edge type of the digraph).
     3387    typedef typename GR::Edge Key;
     3388    /// The value type (the \c Arc type of the digraph).
    33223389    typedef typename GR::Arc Value;
    3323     typedef typename GR::Edge Key;
    33243390
    33253391    /// \brief Constructor
     
    33603426  public:
    33613427
     3428    /// The key type (the \c Edge type of the digraph).
     3429    typedef typename GR::Edge Key;
     3430    /// The value type (the \c Arc type of the digraph).
    33623431    typedef typename GR::Arc Value;
    3363     typedef typename GR::Edge Key;
    33643432
    33653433    /// \brief Constructor
  • lemon/maps.h

    r772 r773  
    17901790  /// \code
    17911791  ///   std::vector<Node> v;
    1792   ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
     1792  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
    17931793  /// \endcode
    17941794  /// \code
    17951795  ///   std::vector<Node> v(countNodes(g));
    1796   ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
     1796  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
    17971797  /// \endcode
    17981798  ///
  • test/maps_test.cc

    r742 r773  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
     25#include <lemon/list_graph.h>
    2526#include <lemon/smart_graph.h>
     27#include <lemon/adaptors.h>
     28#include <lemon/dfs.h>
    2629
    2730#include "test_tools.h"
     
    6164typedef ReadWriteMap<A, bool> BoolWriteMap;
    6265typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
     66
     67template<typename Map1, typename Map2, typename ItemIt>
     68void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {
     69  for (; it != INVALID; ++it)
     70    check(map1[it] == map2[it], "The maps are not equal");
     71}
    6372
    6473int main()
     
    330339  {
    331340    typedef std::vector<int> vec;
     341    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
     342    checkConcept<WriteMap<int, bool>,
     343                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
     344
    332345    vec v1;
    333346    vec v2(10);
     
    349362          it != map2.end(); ++it )
    350363      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
     364   
     365    typedef ListDigraph Graph;
     366    DIGRAPH_TYPEDEFS(Graph);
     367    Graph gr;
     368
     369    Node n0 = gr.addNode();
     370    Node n1 = gr.addNode();
     371    Node n2 = gr.addNode();
     372    Node n3 = gr.addNode();
     373   
     374    gr.addArc(n3, n0);
     375    gr.addArc(n3, n2);
     376    gr.addArc(n0, n2);
     377    gr.addArc(n2, n1);
     378    gr.addArc(n0, n1);
     379   
     380    {
     381      std::vector<Node> v;
     382      dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();
     383
     384      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
     385            "Something is wrong with LoggerBoolMap");
     386    }
     387    {
     388      std::vector<Node> v(countNodes(gr));
     389      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();
     390     
     391      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
     392            "Something is wrong with LoggerBoolMap");
     393    }
     394  }
     395 
     396  // IdMap, RangeIdMap
     397  {
     398    typedef ListDigraph Graph;
     399    DIGRAPH_TYPEDEFS(Graph);
     400
     401    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
     402    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
     403    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
     404    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
     405   
     406    Graph gr;
     407    IdMap<Graph, Node> nmap(gr);
     408    IdMap<Graph, Arc> amap(gr);
     409    RangeIdMap<Graph, Node> nrmap(gr);
     410    RangeIdMap<Graph, Arc> armap(gr);
     411   
     412    Node n0 = gr.addNode();
     413    Node n1 = gr.addNode();
     414    Node n2 = gr.addNode();
     415   
     416    Arc a0 = gr.addArc(n0, n1);
     417    Arc a1 = gr.addArc(n0, n2);
     418    Arc a2 = gr.addArc(n2, n1);
     419    Arc a3 = gr.addArc(n2, n0);
     420   
     421    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
     422    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
     423    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");
     424
     425    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");
     426    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");
     427    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");
     428    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");
     429
     430    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
     431    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
     432   
     433    check(nrmap.size() == 3 && armap.size() == 4,
     434          "Wrong RangeIdMap::size()");
     435
     436    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");
     437    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
     438    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
     439   
     440    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
     441    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     442    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");
     443    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");
     444
     445    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
     446    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
     447   
     448    gr.erase(n1);
     449   
     450    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
     451    nrmap.swap(n2, n0);
     452    if (armap[a1] == 1) armap.swap(a1, a3);
     453    armap.swap(a3, a1);
     454   
     455    check(nrmap.size() == 2 && armap.size() == 2,
     456          "Wrong RangeIdMap::size()");
     457
     458    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
     459    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
     460   
     461    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     462    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
     463
     464    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");
     465    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
     466  }
     467 
     468  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap
     469  {
     470    typedef ListGraph Graph;
     471    GRAPH_TYPEDEFS(Graph);
     472   
     473    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();
     474    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
     475    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();
     476    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();
     477    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();
     478    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();
     479
     480    Graph gr;
     481    Node n0 = gr.addNode();
     482    Node n1 = gr.addNode();
     483    Node n2 = gr.addNode();
     484   
     485    gr.addEdge(n0,n1);
     486    gr.addEdge(n1,n2);
     487    gr.addEdge(n0,n2);
     488    gr.addEdge(n2,n1);
     489    gr.addEdge(n1,n2);
     490    gr.addEdge(n0,n1);
     491   
     492    for (EdgeIt e(gr); e != INVALID; ++e) {
     493      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
     494      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
     495    }
     496   
     497    compareMap(sourceMap(orienter(gr, constMap<Edge, bool>(true))),
     498               targetMap(orienter(gr, constMap<Edge, bool>(false))),
     499               EdgeIt(gr));
     500
     501    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
     502    Digraph dgr(gr, constMap<Edge, bool>(true));
     503    OutDegMap<Digraph> odm(dgr);
     504    InDegMap<Digraph> idm(dgr);
     505   
     506    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");
     507    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
     508   
     509    gr.addEdge(n2, n0);
     510
     511    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");
     512    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
     513  }
     514 
     515  // CrossRefMap
     516  {
     517    typedef ListDigraph Graph;
     518    DIGRAPH_TYPEDEFS(Graph);
     519
     520    checkConcept<ReadWriteMap<Node, int>,
     521                 CrossRefMap<Graph, Node, int> >();
     522    checkConcept<ReadWriteMap<Node, bool>,
     523                 CrossRefMap<Graph, Node, bool> >();
     524    checkConcept<ReadWriteMap<Node, double>,
     525                 CrossRefMap<Graph, Node, double> >();
     526   
     527    Graph gr;
     528    typedef CrossRefMap<Graph, Node, char> CRMap;
     529    CRMap map(gr);
     530   
     531    Node n0 = gr.addNode();
     532    Node n1 = gr.addNode();
     533    Node n2 = gr.addNode();
     534   
     535    map.set(n0, 'A');
     536    map.set(n1, 'B');
     537    map.set(n2, 'C');
     538   
     539    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
     540          "Wrong CrossRefMap");
     541    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,
     542          "Wrong CrossRefMap");
     543    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,
     544          "Wrong CrossRefMap");
     545    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
     546          "Wrong CrossRefMap::count()");
     547   
     548    CRMap::ValueIt it = map.beginValue();
     549    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     550          it == map.endValue(), "Wrong value iterator");
     551   
     552    map.set(n2, 'A');
     553
     554    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',
     555          "Wrong CrossRefMap");
     556    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");
     557    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     558    check(map('C') == INVALID && map.inverse()['C'] == INVALID,
     559          "Wrong CrossRefMap");
     560    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,
     561          "Wrong CrossRefMap::count()");
     562
     563    it = map.beginValue();
     564    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&
     565          it == map.endValue(), "Wrong value iterator");
     566
     567    map.set(n0, 'C');
     568
     569    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
     570          "Wrong CrossRefMap");
     571    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
     572    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     573    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
     574    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
     575          "Wrong CrossRefMap::count()");
     576
     577    it = map.beginValue();
     578    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     579          it == map.endValue(), "Wrong value iterator");
    351580  }
    352581
     
    547776    }
    548777
    549     for (Ivm::ValueIterator vit = map1.beginValue();
     778    for (Ivm::ValueIt vit = map1.beginValue();
    550779         vit != map1.endValue(); ++vit) {
    551780      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
    552             "Wrong ValueIterator");
     781            "Wrong ValueIt");
    553782    }
    554783
  • test/maps_test.cc

    r771 r773  
    580580  }
    581581
     582  // CrossRefMap
     583  {
     584    typedef SmartDigraph Graph;
     585    DIGRAPH_TYPEDEFS(Graph);
     586
     587    checkConcept<ReadWriteMap<Node, int>,
     588                 CrossRefMap<Graph, Node, int> >();
     589   
     590    Graph gr;
     591    typedef CrossRefMap<Graph, Node, char> CRMap;
     592    typedef CRMap::ValueIterator ValueIt;
     593    CRMap map(gr);
     594   
     595    Node n0 = gr.addNode();
     596    Node n1 = gr.addNode();
     597    Node n2 = gr.addNode();
     598   
     599    map.set(n0, 'A');
     600    map.set(n1, 'B');
     601    map.set(n2, 'C');
     602    map.set(n2, 'A');
     603    map.set(n0, 'C');
     604
     605    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
     606          "Wrong CrossRefMap");
     607    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
     608    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     609    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
     610
     611    ValueIt it = map.beginValue();
     612    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     613          it == map.endValue(), "Wrong value iterator");
     614  }
     615 
    582616  // Iterable bool map
    583617  {
Note: See TracChangeset for help on using the changeset viewer.