deba@1720: /* -*- C++ -*- deba@1720: * lemon/matrix_maps.h - Part of LEMON, a generic C++ optimization library deba@1720: * deba@1720: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1720: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1720: * deba@1720: * Permission to use, modify and distribute this software is granted deba@1720: * provided that this copyright notice appears in all copies. For deba@1720: * precise terms see the accompanying LICENSE file. deba@1720: * deba@1720: * This software is provided "AS IS" with no warranty of any kind, deba@1720: * express or implied, and with no claim as to its suitability for any deba@1720: * purpose. deba@1720: * deba@1720: */ deba@1720: deba@1720: #ifndef LEMON_MATRIX_MAPS_H deba@1720: #define LEMON_MATRIX_MAPS_H deba@1720: deba@1720: deba@1720: #include deba@1720: #include deba@1720: #include deba@1720: deba@1720: deba@1720: /// \file deba@1720: /// \ingroup maps deba@1720: /// \brief Maps indexed with pairs of items. deba@1720: /// deba@1720: /// \todo This file has the same name as the concept file in concept/, deba@1720: /// and this is not easily detectable in docs... deba@1720: namespace lemon { deba@1720: deba@1720: /// \brief Map for the coloumn view of the matrix deba@1720: /// deba@1720: /// Map for the coloumn view of the matrix. deba@1720: template deba@1720: class MatrixColMap : public MapTraits<_MatrixMap> { deba@1720: public: deba@1720: typedef _MatrixMap MatrixMap; deba@1720: typedef typename MatrixMap::SecondKey Key; deba@1720: typedef typename MatrixMap::Value Value; deba@1720: deba@1720: deba@1720: MatrixColMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _col) deba@1720: : matrix(_matrix), col(_col) {} deba@1720: deba@1720: /// \brief Subscription operator deba@1720: /// deba@1720: /// Subscription operator. deba@1720: typename MapTraits::ReturnValue deba@1720: operator[](Key row) { deba@1720: return matrix(col, row); deba@1720: } deba@1720: deba@1720: /// \brief Setter function deba@1720: /// deba@1720: /// Setter function. deba@1720: void set(Key row, const Value& val) { deba@1720: matrix.set(col, row, val); deba@1720: } deba@1720: deba@1720: /// \brief Subscription operator deba@1720: /// deba@1720: /// Subscription operator. deba@1720: typename MapTraits::ConstReturnValue deba@1720: operator[](Key row) const { deba@1720: return matrix(col, row); deba@1720: } deba@1720: deba@1720: private: deba@1720: MatrixMap& matrix; deba@1720: typename MatrixMap::FirstKey col; deba@1720: }; deba@1720: deba@1720: /// \brief Map for the coloumn view of the matrix deba@1720: /// deba@1720: /// Map for the coloumn view of the matrix. deba@1720: template deba@1720: class ConstMatrixColMap : public MapTraits<_MatrixMap> { deba@1720: public: deba@1720: typedef _MatrixMap MatrixMap; deba@1720: typedef typename MatrixMap::SecondKey Key; deba@1720: typedef typename MatrixMap::Value Value; deba@1720: deba@1720: deba@1720: ConstMatrixColMap(const MatrixMap& _matrix, deba@1720: typename MatrixMap::FirstKey _col) deba@1720: : matrix(_matrix), col(_col) {} deba@1720: deba@1720: /// \brief Subscription operator deba@1720: /// deba@1720: /// Subscription operator. deba@1720: typename MapTraits::ConstReturnValue deba@1720: operator[](Key row) const { deba@1720: return matrix(col, row); deba@1720: } deba@1720: deba@1720: private: deba@1720: const MatrixMap& matrix; deba@1720: typename MatrixMap::FirstKey col; deba@1720: }; deba@1720: deba@1720: /// \brief Gives back a coloumn view of the matrix map deba@1720: /// deba@1720: /// Gives back a coloumn view of the matrix map. deba@1720: template deba@1720: MatrixColMap matrixColMap(MatrixMap& matrixMap, deba@1720: typename MatrixMap::FirstKey col) { deba@1720: return MatrixColMap(matrixMap, col); deba@1720: } deba@1720: deba@1720: template deba@1720: ConstMatrixColMap deba@1720: matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey col) { deba@1720: return ConstMatrixColMap(matrixMap, col); deba@1720: } deba@1720: deba@1720: /// \brief Map for the row view of the matrix deba@1720: /// deba@1720: /// Map for the row view of the matrix. deba@1720: template deba@1720: class MatrixRowMap : public MapTraits<_MatrixMap> { deba@1720: public: deba@1720: typedef _MatrixMap MatrixMap; deba@1720: typedef typename MatrixMap::FirstKey Key; deba@1720: typedef typename MatrixMap::Value Value; deba@1720: deba@1720: MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _row) deba@1720: : matrix(_matrix), row(_row) {} deba@1720: deba@1720: /// \brief Subscription operator deba@1720: /// deba@1720: /// Subscription operator. deba@1720: typename MapTraits::ReturnValue deba@1720: operator[](Key col) { deba@1720: return matrix(col, row); deba@1720: } deba@1720: deba@1720: /// \brief Setter function deba@1720: /// deba@1720: /// Setter function. deba@1720: void set(Key col, const Value& val) { deba@1720: matrix.set(col, row, val); deba@1720: } deba@1720: deba@1720: /// \brief Subscription operator deba@1720: /// deba@1720: /// Subscription operator. deba@1720: typename MapTraits::ConstReturnValue deba@1720: operator[](Key col) const { deba@1720: return matrix(col, row); deba@1720: } deba@1720: deba@1720: private: deba@1720: MatrixMap& matrix; deba@1720: typename MatrixMap::SecondKey row; deba@1720: }; deba@1720: deba@1720: /// \brief Map for the row view of the matrix deba@1720: /// deba@1720: /// Map for the row view of the matrix. deba@1720: template deba@1720: class ConstMatrixRowMap : public MapTraits<_MatrixMap> { deba@1720: public: deba@1720: typedef _MatrixMap MatrixMap; deba@1720: typedef typename MatrixMap::FirstKey Key; deba@1720: typedef typename MatrixMap::Value Value; deba@1720: deba@1720: ConstMatrixRowMap(const MatrixMap& _matrix, deba@1720: typename MatrixMap::SecondKey _row) deba@1720: : matrix(_matrix), row(_row) {} deba@1720: deba@1720: /// \brief Subscription operator deba@1720: /// deba@1720: /// Subscription operator. deba@1720: typename MapTraits::ConstReturnValue deba@1720: operator[](Key col) const { deba@1720: return matrix(col, row); deba@1720: } deba@1720: deba@1720: private: deba@1720: const MatrixMap& matrix; deba@1720: typename MatrixMap::SecondKey row; deba@1720: }; deba@1720: deba@1720: /// \brief Gives back a row view of the matrix map deba@1720: /// deba@1720: /// Gives back a row view of the matrix map. deba@1720: template deba@1720: MatrixRowMap matrixRowMap(MatrixMap& matrixMap, deba@1720: typename MatrixMap::SecondKey row) { deba@1720: return MatrixRowMap(matrixMap, row); deba@1720: } deba@1720: deba@1720: template deba@1720: ConstMatrixRowMap deba@1720: matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey row) { deba@1720: return ConstMatrixRowMap(matrixMap, row); deba@1720: } deba@1720: deba@1720: /// \brief Container for store values for each ordered pair of graph items deba@1720: /// deba@1720: /// This data structure can strore for each pairs of the same item deba@1720: /// type a value. It increase the size of the container when the deba@1720: /// associated graph modified, so it updated automaticly whenever deba@1720: /// it is needed. deba@1720: template deba@1720: class DynamicMatrixMap deba@1720: : protected AlterationNotifier<_Item>::ObserverBase { deba@1720: public: deba@1720: typedef typename AlterationNotifier<_Item>::ObserverBase Parent; deba@1720: deba@1720: typedef _Graph Graph; deba@1720: typedef _Item Key; deba@1720: deba@1720: typedef _Item FirstKey; deba@1720: typedef _Item SecondKey; deba@1720: typedef _Value Value; deba@1720: deba@1720: typedef True ReferenceMapTag; deba@1720: deba@1720: private: deba@1720: deba@1720: typedef std::vector Container; deba@1720: deba@1720: public: deba@1720: deba@1720: typedef typename Container::reference Reference; deba@1720: typedef typename Container::const_reference ConstReference; deba@1720: deba@1720: /// \brief Creates an item matrix for the given graph deba@1720: /// deba@1720: /// Creates an item matrix for the given graph. deba@1720: DynamicMatrixMap(const Graph& _graph) deba@1720: : graph(_graph), values(size(_graph.maxId(Key()) + 1)) { deba@1720: Parent::attach(graph.getNotifier(Key())); deba@1720: } deba@1720: deba@1720: /// \brief Creates an item matrix for the given graph deba@1720: /// deba@1720: /// Creates an item matrix for the given graph and assigns for each deba@1720: /// pairs of keys the given parameter. deba@1720: DynamicMatrixMap(const Graph& _graph, const Value& _val) deba@1720: : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) { deba@1720: Parent::attach(graph.getNotifier(Key())); deba@1720: } deba@1720: deba@1720: ~DynamicMatrixMap() { deba@1720: if (Parent::attached()) { deba@1720: Parent::detach(); deba@1720: } deba@1720: } deba@1720: deba@1720: /// \brief Gives back the value assigned to the \c first - \c second deba@1720: /// ordered pair. deba@1720: /// deba@1720: /// Gives back the value assigned to the \c first - \c second ordered pair. deba@1720: ConstReference operator()(const Key& first, const Key& second) const { deba@1720: return values[index(graph.id(first), graph.id(second))]; deba@1720: } deba@1720: deba@1720: /// \brief Gives back the value assigned to the \c first - \c second deba@1720: /// ordered pair. deba@1720: /// deba@1720: /// Gives back the value assigned to the \c first - \c second ordered pair. deba@1720: Reference operator()(const Key& first, const Key& second) { deba@1720: return values[index(graph.id(first), graph.id(second))]; deba@1720: } deba@1720: deba@1720: /// \brief Setter function for the matrix map. deba@1720: /// deba@1720: /// Setter function for the matrix map. deba@1720: void set(const Key& first, const Key& second, const Value& val) { deba@1720: values[index(graph.id(first), graph.id(second))] = val; deba@1720: } deba@1720: deba@1720: protected: deba@1720: deba@1720: static int index(int i, int j) { deba@1720: if (i < j) { deba@1720: return j * j + i; deba@1720: } else { deba@1720: return i * i + i + j; deba@1720: } deba@1720: } deba@1720: deba@1720: static int size(int s) { deba@1720: return s * s; deba@1720: } deba@1720: deba@1720: virtual void add(const Key& key) { deba@1720: if (size(graph.id(key) + 1) >= (int)values.size()) { deba@1720: values.resize(size(graph.id(key) + 1)); deba@1720: } deba@1720: } deba@1720: deba@1720: virtual void erase(const Key&) {} deba@1720: deba@1720: virtual void build() { deba@1720: values.resize(size(graph.maxId(Key()) + 1)); deba@1720: } deba@1720: deba@1720: virtual void clear() { deba@1720: values.clear(); deba@1720: } deba@1720: deba@1720: private: deba@1720: const Graph& graph; deba@1720: std::vector values; deba@1720: }; deba@1720: deba@1720: /// \brief Container for store values for each unordered pair of graph items deba@1720: /// deba@1720: /// This data structure can strore for each pairs of the same item deba@1720: /// type a value. It increase the size of the container when the deba@1720: /// associated graph modified, so it updated automaticly whenever deba@1720: /// it is needed. deba@1720: template deba@1720: class DynamicSymMatrixMap deba@1720: : protected AlterationNotifier<_Item>::ObserverBase { deba@1720: public: deba@1720: typedef typename AlterationNotifier<_Item>::ObserverBase Parent; deba@1720: deba@1720: typedef _Graph Graph; deba@1720: typedef _Item Key; deba@1720: deba@1720: typedef _Item FirstKey; deba@1720: typedef _Item SecondKey; deba@1720: typedef _Value Value; deba@1720: deba@1720: typedef True ReferenceMapTag; deba@1720: deba@1720: private: deba@1720: deba@1720: typedef std::vector Container; deba@1720: deba@1720: public: deba@1720: deba@1720: typedef typename Container::reference Reference; deba@1720: typedef typename Container::const_reference ConstReference; deba@1720: deba@1720: /// \brief Creates an item matrix for the given graph deba@1720: /// deba@1720: /// Creates an item matrix for the given graph. deba@1720: DynamicSymMatrixMap(const Graph& _graph) deba@1720: : graph(_graph), values(size(_graph.maxId(Key()) + 1)) { deba@1720: Parent::attach(graph.getNotifier(Key())); deba@1720: } deba@1720: deba@1720: /// \brief Creates an item matrix for the given graph deba@1720: /// deba@1720: /// Creates an item matrix for the given graph and assigns for each deba@1720: /// pairs of keys the given parameter. deba@1720: DynamicSymMatrixMap(const Graph& _graph, const Value& _val) deba@1720: : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) { deba@1720: Parent::attach(graph.getNotifier(Key())); deba@1720: } deba@1720: deba@1720: ~DynamicSymMatrixMap() { deba@1720: if (Parent::attached()) { deba@1720: Parent::detach(); deba@1720: } deba@1720: } deba@1720: deba@1720: /// \brief Gives back the value assigned to the \c first - \c second deba@1720: /// unordered pair. deba@1720: /// deba@1720: /// Gives back the value assigned to the \c first - \c second unordered deba@1720: /// pair. deba@1720: ConstReference operator()(const Key& first, const Key& second) const { deba@1720: return values[index(graph.id(first), graph.id(second))]; deba@1720: } deba@1720: deba@1720: /// \brief Gives back the value assigned to the \c first - \c second deba@1720: /// unordered pair. deba@1720: /// deba@1720: /// Gives back the value assigned to the \c first - \c second unordered deba@1720: /// pair. deba@1720: Reference operator()(const Key& first, const Key& second) { deba@1720: return values[index(graph.id(first), graph.id(second))]; deba@1720: } deba@1720: deba@1720: /// \brief Setter function for the matrix map. deba@1720: /// deba@1720: /// Setter function for the matrix map. deba@1720: void set(const Key& first, const Key& second, const Value& val) { deba@1720: values[index(graph.id(first), graph.id(second))] = val; deba@1720: } deba@1720: deba@1720: protected: deba@1720: deba@1720: static int index(int i, int j) { deba@1720: if (i < j) { deba@1720: return j * (j + 1) / 2 + i; deba@1720: } else { deba@1720: return i * (i + 1) / 2 + j; deba@1720: } deba@1720: } deba@1720: deba@1720: static int size(int s) { deba@1720: return s * (s + 1) / 2; deba@1720: } deba@1720: deba@1720: virtual void add(const Key& key) { deba@1720: if (size(graph.id(key) + 1) >= (int)values.size()) { deba@1720: values.resize(size(graph.id(key) + 1)); deba@1720: } deba@1720: } deba@1720: deba@1720: virtual void erase(const Key&) {} deba@1720: deba@1720: virtual void build() { deba@1720: values.resize(size(graph.maxId(Key()) + 1)); deba@1720: } deba@1720: deba@1720: virtual void clear() { deba@1720: values.clear(); deba@1720: } deba@1720: deba@1720: private: deba@1720: const Graph& graph; deba@1720: std::vector values; deba@1720: }; deba@1720: deba@1720: } deba@1720: deba@1720: #endif