gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
DescriptorMap->RangeIdMap, InvertableMap->CrossRefMap (#160)
0 2 0
default
2 files changed with 43 insertions and 44 deletions:
↑ Collapse diff ↑
Show white space 48 line context
... ...
@@ -1811,49 +1811,49 @@
1811 1811
  }
1812 1812

	
1813 1813
  /// @}
1814 1814

	
1815 1815
  /// \addtogroup graph_maps
1816 1816
  /// @{
1817 1817

	
1818 1818
  /// \brief Provides an immutable and unique id for each item in a graph.
1819 1819
  ///
1820 1820
  /// IdMap provides a unique and immutable id for each item of the
1821 1821
  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
1822 1822
  ///  - \b unique: different items get different ids,
1823 1823
  ///  - \b immutable: the id of an item does not change (even if you
1824 1824
  ///    delete other nodes).
1825 1825
  ///
1826 1826
  /// Using this map you get access (i.e. can read) the inner id values of
1827 1827
  /// the items stored in the graph, which is returned by the \c id()
1828 1828
  /// function of the graph. This map can be inverted with its member
1829 1829
  /// class \c InverseMap or with the \c operator() member.
1830 1830
  ///
1831 1831
  /// \tparam GR The graph type.
1832 1832
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1833 1833
  /// \c GR::Edge).
1834 1834
  ///
1835
  /// \see DescriptorMap
1835
  /// \see RangeIdMap
1836 1836
  template <typename GR, typename K>
1837 1837
  class IdMap : public MapBase<K, int> {
1838 1838
  public:
1839 1839
    /// The graph type of IdMap.
1840 1840
    typedef GR Graph;
1841 1841
    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
1842 1842
    typedef K Item;
1843 1843
    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
1844 1844
    typedef K Key;
1845 1845
    /// The value type of IdMap.
1846 1846
    typedef int Value;
1847 1847

	
1848 1848
    /// \brief Constructor.
1849 1849
    ///
1850 1850
    /// Constructor of the map.
1851 1851
    explicit IdMap(const Graph& graph) : _graph(&graph) {}
1852 1852

	
1853 1853
    /// \brief Gives back the \e id of the item.
1854 1854
    ///
1855 1855
    /// Gives back the immutable and unique \e id of the item.
1856 1856
    int operator[](const Item& item) const { return _graph->id(item);}
1857 1857

	
1858 1858
    /// \brief Gives back the \e item by its id.
1859 1859
    ///
... ...
@@ -1877,99 +1877,99 @@
1877 1877
      /// Constructor for creating an id-to-item map.
1878 1878
      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1879 1879

	
1880 1880
      /// \brief Constructor.
1881 1881
      ///
1882 1882
      /// Constructor for creating an id-to-item map.
1883 1883
      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1884 1884

	
1885 1885
      /// \brief Gives back the given item from its id.
1886 1886
      ///
1887 1887
      /// Gives back the given item from its id.
1888 1888
      Item operator[](int id) const { return _graph->fromId(id, Item());}
1889 1889

	
1890 1890
    private:
1891 1891
      const Graph* _graph;
1892 1892
    };
1893 1893

	
1894 1894
    /// \brief Gives back the inverse of the map.
1895 1895
    ///
1896 1896
    /// Gives back the inverse of the IdMap.
1897 1897
    InverseMap inverse() const { return InverseMap(*_graph);}
1898 1898
  };
1899 1899

	
1900 1900

	
1901
  /// \brief General invertable graph map type.
1901
  /// \brief General cross reference graph map type.
1902 1902

	
1903 1903
  /// This class provides simple invertable graph maps.
1904 1904
  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
1905 1905
  /// and if a key is set to a new value then store it
1906 1906
  /// in the inverse map.
1907 1907
  ///
1908 1908
  /// The values of the map can be accessed
1909 1909
  /// with stl compatible forward iterator.
1910 1910
  ///
1911 1911
  /// \tparam GR The graph type.
1912 1912
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1913 1913
  /// \c GR::Edge).
1914 1914
  /// \tparam V The value type of the map.
1915 1915
  ///
1916 1916
  /// \see IterableValueMap
1917 1917
  template <typename GR, typename K, typename V>
1918
  class InvertableMap
1918
  class CrossRefMap
1919 1919
    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
1920 1920
  private:
1921 1921

	
1922 1922
    typedef typename ItemSetTraits<GR, K>::
1923 1923
      template Map<V>::Type Map;
1924 1924

	
1925 1925
    typedef std::map<V, K> Container;
1926 1926
    Container _inv_map;
1927 1927

	
1928 1928
  public:
1929 1929

	
1930
    /// The graph type of InvertableMap.
1930
    /// The graph type of CrossRefMap.
1931 1931
    typedef GR Graph;
1932
    /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
1932
    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
1933 1933
    typedef K Item;
1934
    /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
1934
    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
1935 1935
    typedef K Key;
1936
    /// The value type of InvertableMap.
1936
    /// The value type of CrossRefMap.
1937 1937
    typedef V Value;
1938 1938

	
1939 1939
    /// \brief Constructor.
1940 1940
    ///
1941
    /// Construct a new InvertableMap for the given graph.
1942
    explicit InvertableMap(const Graph& graph) : Map(graph) {}
1941
    /// Construct a new CrossRefMap for the given graph.
1942
    explicit CrossRefMap(const Graph& graph) : Map(graph) {}
1943 1943

	
1944 1944
    /// \brief Forward iterator for values.
1945 1945
    ///
1946 1946
    /// This iterator is an stl compatible forward
1947 1947
    /// iterator on the values of the map. The values can
1948 1948
    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1949 1949
    class ValueIterator
1950 1950
      : public std::iterator<std::forward_iterator_tag, Value> {
1951
      friend class InvertableMap;
1951
      friend class CrossRefMap;
1952 1952
    private:
1953 1953
      ValueIterator(typename Container::const_iterator _it)
1954 1954
        : it(_it) {}
1955 1955
    public:
1956 1956

	
1957 1957
      ValueIterator() {}
1958 1958

	
1959 1959
      ValueIterator& operator++() { ++it; return *this; }
1960 1960
      ValueIterator operator++(int) {
1961 1961
        ValueIterator tmp(*this);
1962 1962
        operator++();
1963 1963
        return tmp;
1964 1964
      }
1965 1965

	
1966 1966
      const Value& operator*() const { return it->first; }
1967 1967
      const Value* operator->() const { return &(it->first); }
1968 1968

	
1969 1969
      bool operator==(ValueIterator jt) const { return it == jt.it; }
1970 1970
      bool operator!=(ValueIterator jt) const { return it != jt.it; }
1971 1971

	
1972 1972
    private:
1973 1973
      typename Container::const_iterator it;
1974 1974
    };
1975 1975

	
... ...
@@ -2051,120 +2051,119 @@
2051 2051
      }
2052 2052
      Map::erase(keys);
2053 2053
    }
2054 2054

	
2055 2055
    /// \brief Clear the keys from the map and the inverse map.
2056 2056
    ///
2057 2057
    /// Clear the keys from the map and the inverse map. It is called by the
2058 2058
    /// \c AlterationNotifier.
2059 2059
    virtual void clear() {
2060 2060
      _inv_map.clear();
2061 2061
      Map::clear();
2062 2062
    }
2063 2063

	
2064 2064
  public:
2065 2065

	
2066 2066
    /// \brief The inverse map type.
2067 2067
    ///
2068 2068
    /// The inverse of this map. The subscript operator of the map
2069 2069
    /// gives back the item that was last assigned to the value.
2070 2070
    class InverseMap {
2071 2071
    public:
2072 2072
      /// \brief Constructor
2073 2073
      ///
2074 2074
      /// Constructor of the InverseMap.
2075
      explicit InverseMap(const InvertableMap& inverted)
2075
      explicit InverseMap(const CrossRefMap& inverted)
2076 2076
        : _inverted(inverted) {}
2077 2077

	
2078 2078
      /// The value type of the InverseMap.
2079
      typedef typename InvertableMap::Key Value;
2079
      typedef typename CrossRefMap::Key Value;
2080 2080
      /// The key type of the InverseMap.
2081
      typedef typename InvertableMap::Value Key;
2081
      typedef typename CrossRefMap::Value Key;
2082 2082

	
2083 2083
      /// \brief Subscript operator.
2084 2084
      ///
2085 2085
      /// Subscript operator. It gives back the item
2086 2086
      /// that was last assigned to the given value.
2087 2087
      Value operator[](const Key& key) const {
2088 2088
        return _inverted(key);
2089 2089
      }
2090 2090

	
2091 2091
    private:
2092
      const InvertableMap& _inverted;
2092
      const CrossRefMap& _inverted;
2093 2093
    };
2094 2094

	
2095 2095
    /// \brief It gives back the read-only inverse map.
2096 2096
    ///
2097 2097
    /// It gives back the read-only inverse map.
2098 2098
    InverseMap inverse() const {
2099 2099
      return InverseMap(*this);
2100 2100
    }
2101 2101

	
2102 2102
  };
2103 2103

	
2104
  /// \brief Provides a mutable, continuous and unique descriptor for each
2105
  /// item in a graph.
2104
  /// \brief Provides continuous and unique ID for the
2105
  /// items of a graph.
2106 2106
  ///
2107
  /// DescriptorMap provides a unique and continuous (but mutable)
2108
  /// descriptor (id) for each item of the same type (\c Node, \c Arc or
2107
  /// RangeIdMap provides a unique and continuous
2108
  /// ID for each item of a given type (\c Node, \c Arc or
2109 2109
  /// \c Edge) in a graph. This id is
2110 2110
  ///  - \b unique: different items get different ids,
2111 2111
  ///  - \b continuous: the range of the ids is the set of integers
2112 2112
  ///    between 0 and \c n-1, where \c n is the number of the items of
2113
  ///    this type (\c Node, \c Arc or \c Edge). So the id of an item can
2114
  ///    change if you delete an other item of the same type, i.e. this
2115
  ///    id is mutable.
2113
  ///    this type (\c Node, \c Arc or \c Edge).
2114
  ///  - So, the ids can change when deleting an item of the same type.
2116 2115
  ///
2117 2116
  /// Thus this id is not (necessarily) the same as what can get using
2118 2117
  /// the \c id() function of the graph or \ref IdMap.
2119 2118
  /// This map can be inverted with its member class \c InverseMap,
2120 2119
  /// or with the \c operator() member.
2121 2120
  ///
2122 2121
  /// \tparam GR The graph type.
2123 2122
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
2124 2123
  /// \c GR::Edge).
2125 2124
  ///
2126 2125
  /// \see IdMap
2127 2126
  template <typename GR, typename K>
2128
  class DescriptorMap
2127
  class RangeIdMap
2129 2128
    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
2130 2129

	
2131 2130
    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
2132 2131

	
2133 2132
  public:
2134
    /// The graph type of DescriptorMap.
2133
    /// The graph type of RangeIdMap.
2135 2134
    typedef GR Graph;
2136
    /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
2135
    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
2137 2136
    typedef K Item;
2138
    /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
2137
    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
2139 2138
    typedef K Key;
2140
    /// The value type of DescriptorMap.
2139
    /// The value type of RangeIdMap.
2141 2140
    typedef int Value;
2142 2141

	
2143 2142
    /// \brief Constructor.
2144 2143
    ///
2145
    /// Constructor for descriptor map.
2146
    explicit DescriptorMap(const Graph& gr) : Map(gr) {
2144
    /// Constructor.
2145
    explicit RangeIdMap(const Graph& gr) : Map(gr) {
2147 2146
      Item it;
2148 2147
      const typename Map::Notifier* nf = Map::notifier();
2149 2148
      for (nf->first(it); it != INVALID; nf->next(it)) {
2150 2149
        Map::set(it, _inv_map.size());
2151 2150
        _inv_map.push_back(it);
2152 2151
      }
2153 2152
    }
2154 2153

	
2155 2154
  protected:
2156 2155

	
2157 2156
    /// \brief Adds a new key to the map.
2158 2157
    ///
2159 2158
    /// Add a new key to the map. It is called by the
2160 2159
    /// \c AlterationNotifier.
2161 2160
    virtual void add(const Item& item) {
2162 2161
      Map::add(item);
2163 2162
      Map::set(item, _inv_map.size());
2164 2163
      _inv_map.push_back(item);
2165 2164
    }
2166 2165

	
2167 2166
    /// \brief Add more new keys to the map.
2168 2167
    ///
2169 2168
    /// Add more new keys to the map. It is called by the
2170 2169
    /// \c AlterationNotifier.
... ...
@@ -2223,103 +2222,103 @@
2223 2222
      Map::clear();
2224 2223
    }
2225 2224

	
2226 2225
  public:
2227 2226

	
2228 2227
    /// \brief Returns the maximal value plus one.
2229 2228
    ///
2230 2229
    /// Returns the maximal value plus one in the map.
2231 2230
    unsigned int size() const {
2232 2231
      return _inv_map.size();
2233 2232
    }
2234 2233

	
2235 2234
    /// \brief Swaps the position of the two items in the map.
2236 2235
    ///
2237 2236
    /// Swaps the position of the two items in the map.
2238 2237
    void swap(const Item& p, const Item& q) {
2239 2238
      int pi = Map::operator[](p);
2240 2239
      int qi = Map::operator[](q);
2241 2240
      Map::set(p, qi);
2242 2241
      _inv_map[qi] = p;
2243 2242
      Map::set(q, pi);
2244 2243
      _inv_map[pi] = q;
2245 2244
    }
2246 2245

	
2247
    /// \brief Gives back the \e descriptor of the item.
2246
    /// \brief Gives back the \e RangeId of the item
2248 2247
    ///
2249
    /// Gives back the mutable and unique \e descriptor of the map.
2248
    /// Gives back the \e RangeId of the item.
2250 2249
    int operator[](const Item& item) const {
2251 2250
      return Map::operator[](item);
2252 2251
    }
2253 2252

	
2254
    /// \brief Gives back the item by its descriptor.
2253
    /// \brief Gives back the item belonging to a \e RangeId
2255 2254
    ///
2256
    /// Gives back th item by its descriptor.
2255
    /// Gives back the item belonging to a \e RangeId.
2257 2256
    Item operator()(int id) const {
2258 2257
      return _inv_map[id];
2259 2258
    }
2260 2259

	
2261 2260
  private:
2262 2261

	
2263 2262
    typedef std::vector<Item> Container;
2264 2263
    Container _inv_map;
2265 2264

	
2266 2265
  public:
2267 2266

	
2268
    /// \brief The inverse map type of DescriptorMap.
2267
    /// \brief The inverse map type of RangeIdMap.
2269 2268
    ///
2270
    /// The inverse map type of DescriptorMap.
2269
    /// The inverse map type of RangeIdMap.
2271 2270
    class InverseMap {
2272 2271
    public:
2273 2272
      /// \brief Constructor
2274 2273
      ///
2275 2274
      /// Constructor of the InverseMap.
2276
      explicit InverseMap(const DescriptorMap& inverted)
2275
      explicit InverseMap(const RangeIdMap& inverted)
2277 2276
        : _inverted(inverted) {}
2278 2277

	
2279 2278

	
2280 2279
      /// The value type of the InverseMap.
2281
      typedef typename DescriptorMap::Key Value;
2280
      typedef typename RangeIdMap::Key Value;
2282 2281
      /// The key type of the InverseMap.
2283
      typedef typename DescriptorMap::Value Key;
2282
      typedef typename RangeIdMap::Value Key;
2284 2283

	
2285 2284
      /// \brief Subscript operator.
2286 2285
      ///
2287 2286
      /// Subscript operator. It gives back the item
2288 2287
      /// that the descriptor currently belongs to.
2289 2288
      Value operator[](const Key& key) const {
2290 2289
        return _inverted(key);
2291 2290
      }
2292 2291

	
2293 2292
      /// \brief Size of the map.
2294 2293
      ///
2295 2294
      /// Returns the size of the map.
2296 2295
      unsigned int size() const {
2297 2296
        return _inverted.size();
2298 2297
      }
2299 2298

	
2300 2299
    private:
2301
      const DescriptorMap& _inverted;
2300
      const RangeIdMap& _inverted;
2302 2301
    };
2303 2302

	
2304 2303
    /// \brief Gives back the inverse of the map.
2305 2304
    ///
2306 2305
    /// Gives back the inverse of the map.
2307 2306
    const InverseMap inverse() const {
2308 2307
      return InverseMap(*this);
2309 2308
    }
2310 2309
  };
2311 2310

	
2312 2311
  /// \brief Map of the source nodes of arcs in a digraph.
2313 2312
  ///
2314 2313
  /// SourceMap provides access for the source node of each arc in a digraph,
2315 2314
  /// which is returned by the \c source() function of the digraph.
2316 2315
  /// \tparam GR The digraph type.
2317 2316
  /// \see TargetMap
2318 2317
  template <typename GR>
2319 2318
  class SourceMap {
2320 2319
  public:
2321 2320

	
2322 2321
    ///\e
2323 2322
    typedef typename GR::Arc Key;
2324 2323
    ///\e
2325 2324
    typedef typename GR::Node Value;
Show white space 48 line context
... ...
@@ -17,57 +17,57 @@
17 17
 */
18 18

	
19 19
#include <cstdlib>
20 20
#include <ctime>
21 21

	
22 22
#include <lemon/random.h>
23 23
#include <lemon/list_graph.h>
24 24
#include <lemon/smart_graph.h>
25 25
#include <lemon/maps.h>
26 26

	
27 27
#include "graph_test.h"
28 28
#include "test_tools.h"
29 29

	
30 30
using namespace lemon;
31 31

	
32 32
template <typename Digraph>
33 33
void checkFindArcs() {
34 34
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
35 35

	
36 36
  {
37 37
    Digraph digraph;
38 38
    for (int i = 0; i < 10; ++i) {
39 39
      digraph.addNode();
40 40
    }
41
    DescriptorMap<Digraph, Node> nodes(digraph);
42
    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
41
    RangeIdMap<Digraph, Node> nodes(digraph);
42
    typename RangeIdMap<Digraph, Node>::InverseMap invNodes(nodes);
43 43
    for (int i = 0; i < 100; ++i) {
44 44
      int src = rnd[invNodes.size()];
45 45
      int trg = rnd[invNodes.size()];
46 46
      digraph.addArc(invNodes[src], invNodes[trg]);
47 47
    }
48 48
    typename Digraph::template ArcMap<bool> found(digraph, false);
49
    DescriptorMap<Digraph, Arc> arcs(digraph);
49
    RangeIdMap<Digraph, Arc> arcs(digraph);
50 50
    for (NodeIt src(digraph); src != INVALID; ++src) {
51 51
      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
52 52
        for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
53 53
          check(digraph.source(con) == src, "Wrong source.");
54 54
          check(digraph.target(con) == trg, "Wrong target.");
55 55
          check(found[con] == false, "The arc found already.");
56 56
          found[con] = true;
57 57
        }
58 58
      }
59 59
    }
60 60
    for (ArcIt it(digraph); it != INVALID; ++it) {
61 61
      check(found[it] == true, "The arc is not found.");
62 62
    }
63 63
  }
64 64

	
65 65
  {
66 66
    int num = 5;
67 67
    Digraph fg;
68 68
    std::vector<Node> nodes;
69 69
    for (int i = 0; i < num; ++i) {
70 70
      nodes.push_back(fg.addNode());
71 71
    }
72 72
    for (int i = 0; i < num * num; ++i) {
73 73
      fg.addArc(nodes[i / num], nodes[i % num]);
... ...
@@ -92,57 +92,57 @@
92 92
        Arc con2 = al2(src, trg);
93 93
        Arc con3 = al3(src, trg);
94 94
        Arc con4 = findArc(fg, src, trg);
95 95
        check(con1 == con2 && con2 == con3 && con3 == con4,
96 96
              "Different results.")
97 97
        check(con1 != INVALID, "There is no connecting arc.");
98 98
        check(fg.source(con1) == src, "Wrong source.");
99 99
        check(fg.target(con1) == trg, "Wrong target.");
100 100
        check(al3(src, trg, con3) == INVALID,
101 101
              "There is more connecting arc.");
102 102
        check(findArc(fg, src, trg, con4) == INVALID,
103 103
              "There is more connecting arc.");
104 104
      }
105 105
    }
106 106
  }
107 107
}
108 108

	
109 109
template <typename Graph>
110 110
void checkFindEdges() {
111 111
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
112 112
  Graph graph;
113 113
  for (int i = 0; i < 10; ++i) {
114 114
    graph.addNode();
115 115
  }
116
  DescriptorMap<Graph, Node> nodes(graph);
117
  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
116
  RangeIdMap<Graph, Node> nodes(graph);
117
  typename RangeIdMap<Graph, Node>::InverseMap invNodes(nodes);
118 118
  for (int i = 0; i < 100; ++i) {
119 119
    int src = rnd[invNodes.size()];
120 120
    int trg = rnd[invNodes.size()];
121 121
    graph.addEdge(invNodes[src], invNodes[trg]);
122 122
  }
123 123
  typename Graph::template EdgeMap<int> found(graph, 0);
124
  DescriptorMap<Graph, Edge> edges(graph);
124
  RangeIdMap<Graph, Edge> edges(graph);
125 125
  for (NodeIt src(graph); src != INVALID; ++src) {
126 126
    for (NodeIt trg(graph); trg != INVALID; ++trg) {
127 127
      for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
128 128
        check( (graph.u(con) == src && graph.v(con) == trg) ||
129 129
               (graph.v(con) == src && graph.u(con) == trg),
130 130
               "Wrong end nodes.");
131 131
        ++found[con];
132 132
        check(found[con] <= 2, "The edge found more than twice.");
133 133
      }
134 134
    }
135 135
  }
136 136
  for (EdgeIt it(graph); it != INVALID; ++it) {
137 137
    check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
138 138
           (graph.u(it) == graph.v(it) && found[it] == 1),
139 139
           "The edge is not found correctly.");
140 140
  }
141 141
}
142 142

	
143 143
template <class Digraph>
144 144
void checkDeg()
145 145
{
146 146
  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
147 147

	
148 148
  const int nodeNum = 10;
0 comments (0 inline)