COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/matrix_maps.h @ 1978:ef2d00e46897

Last change on this file since 1978:ef2d00e46897 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

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