1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/matrix_maps.h Fri Oct 14 10:49:51 2005 +0000
1.3 @@ -0,0 +1,428 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/matrix_maps.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_MATRIX_MAPS_H
1.21 +#define LEMON_MATRIX_MAPS_H
1.22 +
1.23 +
1.24 +#include <vector>
1.25 +#include <lemon/utility.h>
1.26 +#include <lemon/maps.h>
1.27 +
1.28 +
1.29 +/// \file
1.30 +/// \ingroup maps
1.31 +/// \brief Maps indexed with pairs of items.
1.32 +///
1.33 +/// \todo This file has the same name as the concept file in concept/,
1.34 +/// and this is not easily detectable in docs...
1.35 +namespace lemon {
1.36 +
1.37 + /// \brief Map for the coloumn view of the matrix
1.38 + ///
1.39 + /// Map for the coloumn view of the matrix.
1.40 + template <typename _MatrixMap>
1.41 + class MatrixColMap : public MapTraits<_MatrixMap> {
1.42 + public:
1.43 + typedef _MatrixMap MatrixMap;
1.44 + typedef typename MatrixMap::SecondKey Key;
1.45 + typedef typename MatrixMap::Value Value;
1.46 +
1.47 +
1.48 + MatrixColMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _col)
1.49 + : matrix(_matrix), col(_col) {}
1.50 +
1.51 + /// \brief Subscription operator
1.52 + ///
1.53 + /// Subscription operator.
1.54 + typename MapTraits<MatrixMap>::ReturnValue
1.55 + operator[](Key row) {
1.56 + return matrix(col, row);
1.57 + }
1.58 +
1.59 + /// \brief Setter function
1.60 + ///
1.61 + /// Setter function.
1.62 + void set(Key row, const Value& val) {
1.63 + matrix.set(col, row, val);
1.64 + }
1.65 +
1.66 + /// \brief Subscription operator
1.67 + ///
1.68 + /// Subscription operator.
1.69 + typename MapTraits<MatrixMap>::ConstReturnValue
1.70 + operator[](Key row) const {
1.71 + return matrix(col, row);
1.72 + }
1.73 +
1.74 + private:
1.75 + MatrixMap& matrix;
1.76 + typename MatrixMap::FirstKey col;
1.77 + };
1.78 +
1.79 + /// \brief Map for the coloumn view of the matrix
1.80 + ///
1.81 + /// Map for the coloumn view of the matrix.
1.82 + template <typename _MatrixMap>
1.83 + class ConstMatrixColMap : public MapTraits<_MatrixMap> {
1.84 + public:
1.85 + typedef _MatrixMap MatrixMap;
1.86 + typedef typename MatrixMap::SecondKey Key;
1.87 + typedef typename MatrixMap::Value Value;
1.88 +
1.89 +
1.90 + ConstMatrixColMap(const MatrixMap& _matrix,
1.91 + typename MatrixMap::FirstKey _col)
1.92 + : matrix(_matrix), col(_col) {}
1.93 +
1.94 + /// \brief Subscription operator
1.95 + ///
1.96 + /// Subscription operator.
1.97 + typename MapTraits<MatrixMap>::ConstReturnValue
1.98 + operator[](Key row) const {
1.99 + return matrix(col, row);
1.100 + }
1.101 +
1.102 + private:
1.103 + const MatrixMap& matrix;
1.104 + typename MatrixMap::FirstKey col;
1.105 + };
1.106 +
1.107 + /// \brief Gives back a coloumn view of the matrix map
1.108 + ///
1.109 + /// Gives back a coloumn view of the matrix map.
1.110 + template <typename MatrixMap>
1.111 + MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
1.112 + typename MatrixMap::FirstKey col) {
1.113 + return MatrixColMap<MatrixMap>(matrixMap, col);
1.114 + }
1.115 +
1.116 + template <typename MatrixMap>
1.117 + ConstMatrixColMap<MatrixMap>
1.118 + matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey col) {
1.119 + return ConstMatrixColMap<MatrixMap>(matrixMap, col);
1.120 + }
1.121 +
1.122 + /// \brief Map for the row view of the matrix
1.123 + ///
1.124 + /// Map for the row view of the matrix.
1.125 + template <typename _MatrixMap>
1.126 + class MatrixRowMap : public MapTraits<_MatrixMap> {
1.127 + public:
1.128 + typedef _MatrixMap MatrixMap;
1.129 + typedef typename MatrixMap::FirstKey Key;
1.130 + typedef typename MatrixMap::Value Value;
1.131 +
1.132 + MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _row)
1.133 + : matrix(_matrix), row(_row) {}
1.134 +
1.135 + /// \brief Subscription operator
1.136 + ///
1.137 + /// Subscription operator.
1.138 + typename MapTraits<MatrixMap>::ReturnValue
1.139 + operator[](Key col) {
1.140 + return matrix(col, row);
1.141 + }
1.142 +
1.143 + /// \brief Setter function
1.144 + ///
1.145 + /// Setter function.
1.146 + void set(Key col, const Value& val) {
1.147 + matrix.set(col, row, val);
1.148 + }
1.149 +
1.150 + /// \brief Subscription operator
1.151 + ///
1.152 + /// Subscription operator.
1.153 + typename MapTraits<MatrixMap>::ConstReturnValue
1.154 + operator[](Key col) const {
1.155 + return matrix(col, row);
1.156 + }
1.157 +
1.158 + private:
1.159 + MatrixMap& matrix;
1.160 + typename MatrixMap::SecondKey row;
1.161 + };
1.162 +
1.163 + /// \brief Map for the row view of the matrix
1.164 + ///
1.165 + /// Map for the row view of the matrix.
1.166 + template <typename _MatrixMap>
1.167 + class ConstMatrixRowMap : public MapTraits<_MatrixMap> {
1.168 + public:
1.169 + typedef _MatrixMap MatrixMap;
1.170 + typedef typename MatrixMap::FirstKey Key;
1.171 + typedef typename MatrixMap::Value Value;
1.172 +
1.173 + ConstMatrixRowMap(const MatrixMap& _matrix,
1.174 + typename MatrixMap::SecondKey _row)
1.175 + : matrix(_matrix), row(_row) {}
1.176 +
1.177 + /// \brief Subscription operator
1.178 + ///
1.179 + /// Subscription operator.
1.180 + typename MapTraits<MatrixMap>::ConstReturnValue
1.181 + operator[](Key col) const {
1.182 + return matrix(col, row);
1.183 + }
1.184 +
1.185 + private:
1.186 + const MatrixMap& matrix;
1.187 + typename MatrixMap::SecondKey row;
1.188 + };
1.189 +
1.190 + /// \brief Gives back a row view of the matrix map
1.191 + ///
1.192 + /// Gives back a row view of the matrix map.
1.193 + template <typename MatrixMap>
1.194 + MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
1.195 + typename MatrixMap::SecondKey row) {
1.196 + return MatrixRowMap<MatrixMap>(matrixMap, row);
1.197 + }
1.198 +
1.199 + template <typename MatrixMap>
1.200 + ConstMatrixRowMap<MatrixMap>
1.201 + matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey row) {
1.202 + return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
1.203 + }
1.204 +
1.205 + /// \brief Container for store values for each ordered pair of graph items
1.206 + ///
1.207 + /// This data structure can strore for each pairs of the same item
1.208 + /// type a value. It increase the size of the container when the
1.209 + /// associated graph modified, so it updated automaticly whenever
1.210 + /// it is needed.
1.211 + template <typename _Graph, typename _Item, typename _Value>
1.212 + class DynamicMatrixMap
1.213 + : protected AlterationNotifier<_Item>::ObserverBase {
1.214 + public:
1.215 + typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
1.216 +
1.217 + typedef _Graph Graph;
1.218 + typedef _Item Key;
1.219 +
1.220 + typedef _Item FirstKey;
1.221 + typedef _Item SecondKey;
1.222 + typedef _Value Value;
1.223 +
1.224 + typedef True ReferenceMapTag;
1.225 +
1.226 + private:
1.227 +
1.228 + typedef std::vector<Value> Container;
1.229 +
1.230 + public:
1.231 +
1.232 + typedef typename Container::reference Reference;
1.233 + typedef typename Container::const_reference ConstReference;
1.234 +
1.235 + /// \brief Creates an item matrix for the given graph
1.236 + ///
1.237 + /// Creates an item matrix for the given graph.
1.238 + DynamicMatrixMap(const Graph& _graph)
1.239 + : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
1.240 + Parent::attach(graph.getNotifier(Key()));
1.241 + }
1.242 +
1.243 + /// \brief Creates an item matrix for the given graph
1.244 + ///
1.245 + /// Creates an item matrix for the given graph and assigns for each
1.246 + /// pairs of keys the given parameter.
1.247 + DynamicMatrixMap(const Graph& _graph, const Value& _val)
1.248 + : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
1.249 + Parent::attach(graph.getNotifier(Key()));
1.250 + }
1.251 +
1.252 + ~DynamicMatrixMap() {
1.253 + if (Parent::attached()) {
1.254 + Parent::detach();
1.255 + }
1.256 + }
1.257 +
1.258 + /// \brief Gives back the value assigned to the \c first - \c second
1.259 + /// ordered pair.
1.260 + ///
1.261 + /// Gives back the value assigned to the \c first - \c second ordered pair.
1.262 + ConstReference operator()(const Key& first, const Key& second) const {
1.263 + return values[index(graph.id(first), graph.id(second))];
1.264 + }
1.265 +
1.266 + /// \brief Gives back the value assigned to the \c first - \c second
1.267 + /// ordered pair.
1.268 + ///
1.269 + /// Gives back the value assigned to the \c first - \c second ordered pair.
1.270 + Reference operator()(const Key& first, const Key& second) {
1.271 + return values[index(graph.id(first), graph.id(second))];
1.272 + }
1.273 +
1.274 + /// \brief Setter function for the matrix map.
1.275 + ///
1.276 + /// Setter function for the matrix map.
1.277 + void set(const Key& first, const Key& second, const Value& val) {
1.278 + values[index(graph.id(first), graph.id(second))] = val;
1.279 + }
1.280 +
1.281 + protected:
1.282 +
1.283 + static int index(int i, int j) {
1.284 + if (i < j) {
1.285 + return j * j + i;
1.286 + } else {
1.287 + return i * i + i + j;
1.288 + }
1.289 + }
1.290 +
1.291 + static int size(int s) {
1.292 + return s * s;
1.293 + }
1.294 +
1.295 + virtual void add(const Key& key) {
1.296 + if (size(graph.id(key) + 1) >= (int)values.size()) {
1.297 + values.resize(size(graph.id(key) + 1));
1.298 + }
1.299 + }
1.300 +
1.301 + virtual void erase(const Key&) {}
1.302 +
1.303 + virtual void build() {
1.304 + values.resize(size(graph.maxId(Key()) + 1));
1.305 + }
1.306 +
1.307 + virtual void clear() {
1.308 + values.clear();
1.309 + }
1.310 +
1.311 + private:
1.312 + const Graph& graph;
1.313 + std::vector<Value> values;
1.314 + };
1.315 +
1.316 + /// \brief Container for store values for each unordered pair of graph items
1.317 + ///
1.318 + /// This data structure can strore for each pairs of the same item
1.319 + /// type a value. It increase the size of the container when the
1.320 + /// associated graph modified, so it updated automaticly whenever
1.321 + /// it is needed.
1.322 + template <typename _Graph, typename _Item, typename _Value>
1.323 + class DynamicSymMatrixMap
1.324 + : protected AlterationNotifier<_Item>::ObserverBase {
1.325 + public:
1.326 + typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
1.327 +
1.328 + typedef _Graph Graph;
1.329 + typedef _Item Key;
1.330 +
1.331 + typedef _Item FirstKey;
1.332 + typedef _Item SecondKey;
1.333 + typedef _Value Value;
1.334 +
1.335 + typedef True ReferenceMapTag;
1.336 +
1.337 + private:
1.338 +
1.339 + typedef std::vector<Value> Container;
1.340 +
1.341 + public:
1.342 +
1.343 + typedef typename Container::reference Reference;
1.344 + typedef typename Container::const_reference ConstReference;
1.345 +
1.346 + /// \brief Creates an item matrix for the given graph
1.347 + ///
1.348 + /// Creates an item matrix for the given graph.
1.349 + DynamicSymMatrixMap(const Graph& _graph)
1.350 + : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
1.351 + Parent::attach(graph.getNotifier(Key()));
1.352 + }
1.353 +
1.354 + /// \brief Creates an item matrix for the given graph
1.355 + ///
1.356 + /// Creates an item matrix for the given graph and assigns for each
1.357 + /// pairs of keys the given parameter.
1.358 + DynamicSymMatrixMap(const Graph& _graph, const Value& _val)
1.359 + : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
1.360 + Parent::attach(graph.getNotifier(Key()));
1.361 + }
1.362 +
1.363 + ~DynamicSymMatrixMap() {
1.364 + if (Parent::attached()) {
1.365 + Parent::detach();
1.366 + }
1.367 + }
1.368 +
1.369 + /// \brief Gives back the value assigned to the \c first - \c second
1.370 + /// unordered pair.
1.371 + ///
1.372 + /// Gives back the value assigned to the \c first - \c second unordered
1.373 + /// pair.
1.374 + ConstReference operator()(const Key& first, const Key& second) const {
1.375 + return values[index(graph.id(first), graph.id(second))];
1.376 + }
1.377 +
1.378 + /// \brief Gives back the value assigned to the \c first - \c second
1.379 + /// unordered pair.
1.380 + ///
1.381 + /// Gives back the value assigned to the \c first - \c second unordered
1.382 + /// pair.
1.383 + Reference operator()(const Key& first, const Key& second) {
1.384 + return values[index(graph.id(first), graph.id(second))];
1.385 + }
1.386 +
1.387 + /// \brief Setter function for the matrix map.
1.388 + ///
1.389 + /// Setter function for the matrix map.
1.390 + void set(const Key& first, const Key& second, const Value& val) {
1.391 + values[index(graph.id(first), graph.id(second))] = val;
1.392 + }
1.393 +
1.394 + protected:
1.395 +
1.396 + static int index(int i, int j) {
1.397 + if (i < j) {
1.398 + return j * (j + 1) / 2 + i;
1.399 + } else {
1.400 + return i * (i + 1) / 2 + j;
1.401 + }
1.402 + }
1.403 +
1.404 + static int size(int s) {
1.405 + return s * (s + 1) / 2;
1.406 + }
1.407 +
1.408 + virtual void add(const Key& key) {
1.409 + if (size(graph.id(key) + 1) >= (int)values.size()) {
1.410 + values.resize(size(graph.id(key) + 1));
1.411 + }
1.412 + }
1.413 +
1.414 + virtual void erase(const Key&) {}
1.415 +
1.416 + virtual void build() {
1.417 + values.resize(size(graph.maxId(Key()) + 1));
1.418 + }
1.419 +
1.420 + virtual void clear() {
1.421 + values.clear();
1.422 + }
1.423 +
1.424 + private:
1.425 + const Graph& graph;
1.426 + std::vector<Value> values;
1.427 + };
1.428 +
1.429 +}
1.430 +
1.431 +#endif