COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/matrix_maps.h @ 1720:578d8b2b76c6

Last change on this file since 1720:578d8b2b76c6 was 1720:578d8b2b76c6, checked in by Balazs Dezso, 18 years ago

Matrixmaps moved to own file

File size: 11.6 KB
Line 
1/* -*- C++ -*-
2 * lemon/matrix_maps.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_MATRIX_MAPS_H
18#define LEMON_MATRIX_MAPS_H
19
20
21#include <vector>
22#include <lemon/utility.h>
23#include <lemon/maps.h>
24
25
26/// \file
27/// \ingroup maps
28/// \brief Maps indexed with pairs of items.
29///
30/// \todo This file has the same name as the concept file in concept/,
31///  and this is not easily detectable in docs...
32namespace lemon {
33
34  /// \brief Map for the coloumn view of the matrix
35  ///
36  /// Map for the coloumn view of the matrix.
37  template <typename _MatrixMap>
38  class MatrixColMap : public MapTraits<_MatrixMap> {
39  public:
40    typedef _MatrixMap MatrixMap;
41    typedef typename MatrixMap::SecondKey Key;
42    typedef typename MatrixMap::Value Value;
43
44
45    MatrixColMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _col)
46      : matrix(_matrix), col(_col) {}
47
48    /// \brief Subscription operator
49    ///
50    /// Subscription operator.
51    typename MapTraits<MatrixMap>::ReturnValue
52    operator[](Key row) {
53      return matrix(col, row);
54    }
55
56    /// \brief Setter function
57    ///
58    /// Setter function.
59    void set(Key row, const Value& val) {
60      matrix.set(col, row, val);
61    }
62     
63    /// \brief Subscription operator
64    ///
65    /// Subscription operator.
66    typename MapTraits<MatrixMap>::ConstReturnValue
67    operator[](Key row) const {
68      return matrix(col, row);
69    }
70
71  private:
72    MatrixMap& matrix;
73    typename MatrixMap::FirstKey col;
74  };
75
76  /// \brief Map for the coloumn view of the matrix
77  ///
78  /// Map for the coloumn view of the matrix.
79  template <typename _MatrixMap>
80  class ConstMatrixColMap : public MapTraits<_MatrixMap> {
81  public:
82    typedef _MatrixMap MatrixMap;
83    typedef typename MatrixMap::SecondKey Key;
84    typedef typename MatrixMap::Value Value;
85
86
87    ConstMatrixColMap(const MatrixMap& _matrix,
88                      typename MatrixMap::FirstKey _col)
89      : matrix(_matrix), col(_col) {}
90
91    /// \brief Subscription operator
92    ///
93    /// Subscription operator.
94    typename MapTraits<MatrixMap>::ConstReturnValue
95    operator[](Key row) const {
96      return matrix(col, row);
97    }
98
99  private:
100    const MatrixMap& matrix;
101    typename MatrixMap::FirstKey col;
102  };
103
104  /// \brief Gives back a coloumn view of the matrix map
105  ///
106  /// Gives back a coloumn view of the matrix map.
107  template <typename MatrixMap>
108  MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
109                                       typename MatrixMap::FirstKey col) {
110    return MatrixColMap<MatrixMap>(matrixMap, col);
111  }
112
113  template <typename MatrixMap>
114  ConstMatrixColMap<MatrixMap>
115  matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey col) {
116    return ConstMatrixColMap<MatrixMap>(matrixMap, col);
117  }
118
119  /// \brief Map for the row view of the matrix
120  ///
121  /// Map for the row view of the matrix.
122  template <typename _MatrixMap>
123  class MatrixRowMap : public MapTraits<_MatrixMap> {
124  public:
125    typedef _MatrixMap MatrixMap;
126    typedef typename MatrixMap::FirstKey Key;
127    typedef typename MatrixMap::Value Value;
128
129    MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _row)
130      : matrix(_matrix), row(_row) {}
131
132    /// \brief Subscription operator
133    ///
134    /// Subscription operator.
135    typename MapTraits<MatrixMap>::ReturnValue
136    operator[](Key col) {
137      return matrix(col, row);
138    }
139
140    /// \brief Setter function
141    ///
142    /// Setter function.
143    void set(Key col, const Value& val) {
144      matrix.set(col, row, val);
145    }
146     
147    /// \brief Subscription operator
148    ///
149    /// Subscription operator.
150    typename MapTraits<MatrixMap>::ConstReturnValue
151    operator[](Key col) const {
152      return matrix(col, row);
153    }
154
155  private:
156    MatrixMap& matrix;
157    typename MatrixMap::SecondKey row;
158  };
159
160  /// \brief Map for the row view of the matrix
161  ///
162  /// Map for the row view of the matrix.
163  template <typename _MatrixMap>
164  class ConstMatrixRowMap : public MapTraits<_MatrixMap> {
165  public:
166    typedef _MatrixMap MatrixMap;
167    typedef typename MatrixMap::FirstKey Key;
168    typedef typename MatrixMap::Value Value;
169
170    ConstMatrixRowMap(const MatrixMap& _matrix,
171                      typename MatrixMap::SecondKey _row)
172      : matrix(_matrix), row(_row) {}
173
174    /// \brief Subscription operator
175    ///
176    /// Subscription operator.
177    typename MapTraits<MatrixMap>::ConstReturnValue
178    operator[](Key col) const {
179      return matrix(col, row);
180    }
181
182  private:
183    const MatrixMap& matrix;
184    typename MatrixMap::SecondKey row;
185  };
186
187  /// \brief Gives back a row view of the matrix map
188  ///
189  /// Gives back a row view of the matrix map.
190  template <typename MatrixMap>
191  MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
192                                       typename MatrixMap::SecondKey row) {
193    return MatrixRowMap<MatrixMap>(matrixMap, row);
194  }
195
196  template <typename MatrixMap>
197  ConstMatrixRowMap<MatrixMap>
198  matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey row) {
199    return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
200  }
201
202  /// \brief Container for store values for each ordered pair of graph items
203  ///
204  /// This data structure can strore for each pairs of the same item
205  /// type a value. It increase the size of the container when the
206  /// associated graph modified, so it updated automaticly whenever
207  /// it is needed.
208  template <typename _Graph, typename _Item, typename _Value>
209  class DynamicMatrixMap
210    : protected AlterationNotifier<_Item>::ObserverBase {
211  public:
212    typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
213
214    typedef _Graph Graph;
215    typedef _Item Key;
216
217    typedef _Item FirstKey;
218    typedef _Item SecondKey;
219    typedef _Value Value;
220
221    typedef True ReferenceMapTag;
222
223  private:
224               
225    typedef std::vector<Value> Container;
226
227  public:
228
229    typedef typename Container::reference Reference;
230    typedef typename Container::const_reference ConstReference;
231
232    /// \brief Creates an item matrix for the given graph
233    ///
234    /// Creates an item matrix for the given graph.
235    DynamicMatrixMap(const Graph& _graph)
236      : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
237      Parent::attach(graph.getNotifier(Key()));
238    }
239
240    /// \brief Creates an item matrix for the given graph
241    ///
242    /// Creates an item matrix for the given graph and assigns for each
243    /// pairs of keys the given parameter.
244    DynamicMatrixMap(const Graph& _graph, const Value& _val)
245      : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
246      Parent::attach(graph.getNotifier(Key()));
247    }
248
249    ~DynamicMatrixMap() {
250      if (Parent::attached()) {
251        Parent::detach();
252      }
253    }
254
255    /// \brief Gives back the value assigned to the \c first - \c second
256    /// ordered pair.
257    ///
258    /// Gives back the value assigned to the \c first - \c second ordered pair.
259    ConstReference operator()(const Key& first, const Key& second) const {
260      return values[index(graph.id(first), graph.id(second))];
261    }
262   
263    /// \brief Gives back the value assigned to the \c first - \c second
264    /// ordered pair.
265    ///
266    /// Gives back the value assigned to the \c first - \c second ordered pair.
267    Reference operator()(const Key& first, const Key& second) {
268      return values[index(graph.id(first), graph.id(second))];
269    }
270
271    /// \brief Setter function for the matrix map.
272    ///
273    /// Setter function for the matrix map.
274    void set(const Key& first, const Key& second, const Value& val) {
275      values[index(graph.id(first), graph.id(second))] = val;
276    }
277
278  protected:
279
280    static int index(int i, int j) {
281      if (i < j) {
282        return j * j + i;
283      } else {
284        return i * i + i + j;
285      }
286    }
287
288    static int size(int s) {
289      return s * s;
290    }
291
292    virtual void add(const Key& key) {
293      if (size(graph.id(key) + 1) >= (int)values.size()) {
294        values.resize(size(graph.id(key) + 1));
295      }
296    }
297
298    virtual void erase(const Key&) {}
299
300    virtual void build() {
301      values.resize(size(graph.maxId(Key()) + 1));
302    }
303
304    virtual void clear() {
305      values.clear();
306    }   
307   
308  private:
309    const Graph& graph;
310    std::vector<Value> values;
311  };
312
313  /// \brief Container for store values for each unordered pair of graph items
314  ///
315  /// This data structure can strore for each pairs of the same item
316  /// type a value. It increase the size of the container when the
317  /// associated graph modified, so it updated automaticly whenever
318  /// it is needed.
319  template <typename _Graph, typename _Item, typename _Value>
320  class DynamicSymMatrixMap
321    : protected AlterationNotifier<_Item>::ObserverBase {
322  public:
323    typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
324
325    typedef _Graph Graph;
326    typedef _Item Key;
327
328    typedef _Item FirstKey;
329    typedef _Item SecondKey;
330    typedef _Value Value;
331
332    typedef True ReferenceMapTag;
333
334  private:
335               
336    typedef std::vector<Value> Container;
337
338  public:
339
340    typedef typename Container::reference Reference;
341    typedef typename Container::const_reference ConstReference;
342
343    /// \brief Creates an item matrix for the given graph
344    ///
345    /// Creates an item matrix for the given graph.
346    DynamicSymMatrixMap(const Graph& _graph)
347      : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
348      Parent::attach(graph.getNotifier(Key()));
349    }
350
351    /// \brief Creates an item matrix for the given graph
352    ///
353    /// Creates an item matrix for the given graph and assigns for each
354    /// pairs of keys the given parameter.
355    DynamicSymMatrixMap(const Graph& _graph, const Value& _val)
356      : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
357      Parent::attach(graph.getNotifier(Key()));
358    }
359
360    ~DynamicSymMatrixMap() {
361      if (Parent::attached()) {
362        Parent::detach();
363      }
364    }
365
366    /// \brief Gives back the value assigned to the \c first - \c second
367    /// unordered pair.
368    ///
369    /// Gives back the value assigned to the \c first - \c second unordered
370    /// pair.
371    ConstReference operator()(const Key& first, const Key& second) const {
372      return values[index(graph.id(first), graph.id(second))];
373    }
374   
375    /// \brief Gives back the value assigned to the \c first - \c second
376    /// unordered pair.
377    ///
378    /// Gives back the value assigned to the \c first - \c second unordered
379    /// pair.
380    Reference operator()(const Key& first, const Key& second) {
381      return values[index(graph.id(first), graph.id(second))];
382    }
383
384    /// \brief Setter function for the matrix map.
385    ///
386    /// Setter function for the matrix map.
387    void set(const Key& first, const Key& second, const Value& val) {
388      values[index(graph.id(first), graph.id(second))] = val;
389    }
390
391  protected:
392
393    static int index(int i, int j) {
394      if (i < j) {
395        return j * (j + 1) / 2 + i;
396      } else {
397        return i * (i + 1) / 2 + j;
398      }
399    }
400
401    static int size(int s) {
402      return s * (s + 1) / 2;
403    }
404
405    virtual void add(const Key& key) {
406      if (size(graph.id(key) + 1) >= (int)values.size()) {
407        values.resize(size(graph.id(key) + 1));
408      }
409    }
410
411    virtual void erase(const Key&) {}
412
413    virtual void build() {
414      values.resize(size(graph.maxId(Key()) + 1));
415    }
416
417    virtual void clear() {
418      values.clear();
419    }   
420   
421  private:
422    const Graph& graph;
423    std::vector<Value> values;
424  };
425
426}
427
428#endif
Note: See TracBrowser for help on using the repository browser.