1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/concept/matrix_maps.h Fri Oct 14 10:49:51 2005 +0000
1.3 @@ -0,0 +1,205 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/concept/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_CONCEPT_MATRIX_MAPS_H
1.21 +#define LEMON_CONCEPT_MATRIX_MAPS_H
1.22 +
1.23 +#include <lemon/utility.h>
1.24 +#include <lemon/concept_check.h>
1.25 +
1.26 +///\ingroup concept
1.27 +///\file
1.28 +///\brief MatrixMap concepts checking classes for testing and documenting.
1.29 +
1.30 +namespace lemon {
1.31 +
1.32 + namespace concept {
1.33 +
1.34 + /// \addtogroup concept
1.35 + /// @{
1.36 +
1.37 + /// Readable matrix map concept
1.38 + template <typename K1, typename K2, typename V>
1.39 + class ReadMatrixMap
1.40 + {
1.41 + public:
1.42 + /// Map's first key type.
1.43 + typedef K1 FirstKey;
1.44 + /// Map's second key type.
1.45 + typedef K2 SecondKey;
1.46 + /// \brief Map's value type.
1.47 + /// (The type of objects associated with the pairs of keys).
1.48 + typedef V Value;
1.49 +
1.50 + // \bug Value don't need to be default constructible.
1.51 + /// Returns the value associated with a key.
1.52 + Value operator()(const FirstKey&, const SecondKey&) const {
1.53 + return Value();
1.54 + }
1.55 +
1.56 + template <typename _ReadMatrixMap>
1.57 + struct Constraints {
1.58 +
1.59 + void constraints() {
1.60 + Value val = m(first_key, second_key);
1.61 + val = m(first_key, second_key);
1.62 + typename _ReadMatrixMap::Value own_val =
1.63 + m(own_first_key, own_second_key);
1.64 + own_val = m(own_first_key, own_second_key);
1.65 + ignore_unused_variable_warning(val);
1.66 + ignore_unused_variable_warning(own_val);
1.67 + }
1.68 +
1.69 + FirstKey& first_key;
1.70 + SecondKey& second_key;
1.71 + typename _ReadMatrixMap::FirstKey& own_first_key;
1.72 + typename _ReadMatrixMap::SecondKey& own_second_key;
1.73 + _ReadMatrixMap& m;
1.74 + };
1.75 +
1.76 + };
1.77 +
1.78 +
1.79 + /// Writable map concept
1.80 + template <typename K1, typename K2, typename V>
1.81 + class WriteMatrixMap {
1.82 + public:
1.83 + /// Map's first key type.
1.84 + typedef K1 FirstKey;
1.85 + /// Map's second key type.
1.86 + typedef K2 SecondKey;
1.87 + /// \brief Map's value type.
1.88 + /// (The type of objects associated with the pairs of keys).
1.89 + typedef V Value;
1.90 +
1.91 + /// Sets the value associated with the pair of keys.
1.92 + void set(const FirstKey&, const SecondKey& ,const Value&) {}
1.93 +
1.94 + template <typename _WriteMatrixMap>
1.95 + struct Constraints {
1.96 + void constraints() {
1.97 + // No constraints for constructor.
1.98 + m.set(first_key, second_key, val);
1.99 + m.set(own_first_key, own_second_key, own_val);
1.100 + }
1.101 +
1.102 + Value& val;
1.103 + typename _WriteMatrixMap::Value own_val;
1.104 + FirstKey& first_key;
1.105 + SecondKey& second_key;
1.106 + typename _WriteMatrixMap::FirstKey& own_first_key;
1.107 + typename _WriteMatrixMap::SecondKey& own_second_key;
1.108 + _WriteMatrixMap& m;
1.109 +
1.110 + };
1.111 + };
1.112 +
1.113 + ///Read/Writable map concept
1.114 + template<typename K1, typename K2, typename V>
1.115 + class ReadWriteMatrixMap
1.116 + : public ReadMatrixMap<K1, K2, V>, public WriteMatrixMap<K1, K2, V> {
1.117 + public:
1.118 + /// Map's first key type.
1.119 + typedef K1 FirstKey;
1.120 + /// Map's second key type.
1.121 + typedef K2 SecondKey;
1.122 + /// \brief Map's value type.
1.123 + /// (The type of objects associated with the pairs of keys).
1.124 + typedef V Value;
1.125 +
1.126 + /// Returns the value associated with a pair of keys.
1.127 + Value operator()(const FirstKey&, const SecondKey&) const {
1.128 + return Value();
1.129 + }
1.130 + /// Sets the value associated with the pair of keys.
1.131 + void set(const FirstKey&, const SecondKey& ,const Value&) {}
1.132 +
1.133 + template<typename _ReadWriteMatrixMap>
1.134 + struct Constraints {
1.135 + void constraints() {
1.136 + checkConcept<ReadMatrixMap<K1, K2, V>, _ReadWriteMatrixMap >();
1.137 + checkConcept<WriteMatrixMap<K1, K2, V>, _ReadWriteMatrixMap >();
1.138 + }
1.139 + };
1.140 + };
1.141 +
1.142 +
1.143 + ///Dereferable matrix map concept
1.144 + template<typename K1, typename K2, typename V, typename R, typename CR>
1.145 + class ReferenceMatrixMap : public ReadWriteMatrixMap<K1, K2, V>
1.146 + {
1.147 + public:
1.148 + /// Tag for reference maps.
1.149 + typedef True ReferenceMapTag;
1.150 + /// Map's first key type.
1.151 + typedef K1 FirstKey;
1.152 + /// Map's second key type.
1.153 + typedef K1 SecondKey;
1.154 + /// Map's value type. (The type of objects associated with the keys).
1.155 + typedef V Value;
1.156 + /// Map's reference type.
1.157 + typedef R Reference;
1.158 + /// Map's const reference type.
1.159 + typedef CR ConstReference;
1.160 +
1.161 + protected:
1.162 + Value tmp;
1.163 + public:
1.164 +
1.165 + ///Returns a reference to the value associated to a pair of keys.
1.166 + Reference operator()(const FirstKey&, const SecondKey&) {
1.167 + return tmp;
1.168 + }
1.169 + ///Returns a const reference to the value associated to a pair of keys.
1.170 + ConstReference operator()(const FirstKey&, const SecondKey&) const {
1.171 + return tmp;
1.172 + }
1.173 + /// Sets the value associated with the pair of keys.
1.174 + void set(const FirstKey&, const SecondKey& ,const Value&) {}
1.175 +
1.176 + // \todo rethink this concept
1.177 + template<typename _ReferenceMatrixMap>
1.178 + struct ReferenceMapConcept {
1.179 +
1.180 + void constraints() {
1.181 + checkConcept<ReadWriteMatrixMap, _ReferenceMatrixMap >();
1.182 + m(first_key, second_key) = val;
1.183 + val = m(first_key, second_key);
1.184 + m(first_key, second_key) = ref;
1.185 + ref = m(first_key, second_key);
1.186 + m(own_first_key, own_second_key) = own_val;
1.187 + own_val = m(own_first_key, own_second_key);
1.188 + m(own_first_key, own_second_key) = own_ref;
1.189 + own_ref = m(own_first_key, own_second_key);
1.190 + }
1.191 +
1.192 + typename _ReferenceMatrixMap::Key& own_first_key;
1.193 + typename _ReferenceMatrixMap::Key& own_second_key;
1.194 + typename _ReferenceMatrixMap::Value& own_val;
1.195 + typename _ReferenceMatrixMap::Reference& own_ref;
1.196 + FirstKey& first_key;
1.197 + SecondKey& second_key;
1.198 + Value& val;
1.199 + Reference& ref;
1.200 + _ReferenceMatrixMap& m;
1.201 + };
1.202 + };
1.203 +
1.204 + // @}
1.205 +
1.206 + } //namespace concept
1.207 +} //namespace lemon
1.208 +#endif // LEMON_CONCEPT_MATRIX_MAPS_H
2.1 --- a/lemon/graph_utils.h Fri Oct 14 10:48:34 2005 +0000
2.2 +++ b/lemon/graph_utils.h Fri Oct 14 10:49:51 2005 +0000
2.3 @@ -25,6 +25,7 @@
2.4 #include <lemon/invalid.h>
2.5 #include <lemon/utility.h>
2.6 #include <lemon/maps.h>
2.7 +#include <lemon/traits.h>
2.8 #include <lemon/bits/alteration_notifier.h>
2.9
2.10 ///\ingroup gutils
2.11 @@ -400,7 +401,6 @@
2.12 }
2.13 }
2.14
2.15 -
2.16 /// \brief Class to copy a graph.
2.17 ///
2.18 /// Class to copy a graph to an other graph (duplicate a graph). The
2.19 @@ -515,6 +515,8 @@
2.20 return edgeRefMap;
2.21 }
2.22
2.23 + void run() {}
2.24 +
2.25 private:
2.26
2.27 const Source& source;
2.28 @@ -542,101 +544,225 @@
2.29 return GraphCopy<Target, Source>(target, source);
2.30 }
2.31
2.32 - template <typename _Graph, typename _Item>
2.33 - class ItemSetTraits {};
2.34 -
2.35 - template <typename _Graph>
2.36 - class ItemSetTraits<_Graph, typename _Graph::Node> {
2.37 + /// \brief Class to copy an undirected graph.
2.38 + ///
2.39 + /// Class to copy an undirected graph to an other graph (duplicate a graph).
2.40 + /// The simplest way of using it is through the \c copyUndirGraph() function.
2.41 + template <typename Target, typename Source>
2.42 + class UndirGraphCopy {
2.43 + public:
2.44 + typedef typename Source::Node Node;
2.45 + typedef typename Source::NodeIt NodeIt;
2.46 + typedef typename Source::Edge Edge;
2.47 + typedef typename Source::EdgeIt EdgeIt;
2.48 + typedef typename Source::UndirEdge UndirEdge;
2.49 + typedef typename Source::UndirEdgeIt UndirEdgeIt;
2.50 +
2.51 + typedef typename Source::
2.52 + template NodeMap<typename Target::Node> NodeRefMap;
2.53 +
2.54 + typedef typename Source::
2.55 + template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
2.56 +
2.57 + private:
2.58 +
2.59 + struct EdgeRefMap {
2.60 + EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
2.61 + typedef typename Source::Edge Key;
2.62 + typedef typename Target::Edge Value;
2.63 +
2.64 + Value operator[](const Key& key) {
2.65 + return gc.target.direct(gc.undirEdgeRef[key],
2.66 + gc.target.direction(key));
2.67 + }
2.68 +
2.69 + UndirGraphCopy& gc;
2.70 + };
2.71 +
2.72 public:
2.73 +
2.74 + /// \brief Constructor for the UndirGraphCopy.
2.75 + ///
2.76 + /// It copies the content of the \c _source graph into the
2.77 + /// \c _target graph. It creates also two references, one beetween
2.78 + /// the two nodeset and one beetween the two edgesets.
2.79 + UndirGraphCopy(Target& _target, const Source& _source)
2.80 + : source(_source), target(_target),
2.81 + nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
2.82 + for (NodeIt it(source); it != INVALID; ++it) {
2.83 + nodeRefMap[it] = target.addNode();
2.84 + }
2.85 + for (UndirEdgeIt it(source); it != INVALID; ++it) {
2.86 + undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
2.87 + nodeRefMap[source.target(it)]);
2.88 + }
2.89 + }
2.90 +
2.91 + /// \brief Copies the node references into the given map.
2.92 + ///
2.93 + /// Copies the node references into the given map.
2.94 + template <typename NodeRef>
2.95 + const UndirGraphCopy& nodeRef(NodeRef& map) const {
2.96 + for (NodeIt it(source); it != INVALID; ++it) {
2.97 + map.set(it, nodeRefMap[it]);
2.98 + }
2.99 + return *this;
2.100 + }
2.101 +
2.102 + /// \brief Reverse and copies the node references into the given map.
2.103 + ///
2.104 + /// Reverse and copies the node references into the given map.
2.105 + template <typename NodeRef>
2.106 + const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
2.107 + for (NodeIt it(source); it != INVALID; ++it) {
2.108 + map.set(nodeRefMap[it], it);
2.109 + }
2.110 + return *this;
2.111 + }
2.112 +
2.113 + /// \brief Copies the edge references into the given map.
2.114 + ///
2.115 + /// Copies the edge references into the given map.
2.116 + template <typename EdgeRef>
2.117 + const UndirGraphCopy& edgeRef(EdgeRef& map) const {
2.118 + for (EdgeIt it(source); it != INVALID; ++it) {
2.119 + map.set(edgeRefMap[it], it);
2.120 + }
2.121 + return *this;
2.122 + }
2.123 +
2.124 + /// \brief Reverse and copies the undirected edge references into the
2.125 + /// given map.
2.126 + ///
2.127 + /// Reverse and copies the undirected edge references into the given map.
2.128 + template <typename EdgeRef>
2.129 + const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
2.130 + for (EdgeIt it(source); it != INVALID; ++it) {
2.131 + map.set(it, edgeRefMap[it]);
2.132 + }
2.133 + return *this;
2.134 + }
2.135 +
2.136 + /// \brief Copies the undirected edge references into the given map.
2.137 + ///
2.138 + /// Copies the undirected edge references into the given map.
2.139 + template <typename EdgeRef>
2.140 + const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
2.141 + for (UndirEdgeIt it(source); it != INVALID; ++it) {
2.142 + map.set(it, undirEdgeRefMap[it]);
2.143 + }
2.144 + return *this;
2.145 + }
2.146 +
2.147 + /// \brief Reverse and copies the undirected edge references into the
2.148 + /// given map.
2.149 + ///
2.150 + /// Reverse and copies the undirected edge references into the given map.
2.151 + template <typename EdgeRef>
2.152 + const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
2.153 + for (UndirEdgeIt it(source); it != INVALID; ++it) {
2.154 + map.set(undirEdgeRefMap[it], it);
2.155 + }
2.156 + return *this;
2.157 + }
2.158 +
2.159 + /// \brief Make copy of the given map.
2.160 + ///
2.161 + /// Makes copy of the given map for the newly created graph.
2.162 + /// The new map's key type is the target graph's node type,
2.163 + /// and the copied map's key type is the source graph's node
2.164 + /// type.
2.165 + template <typename TargetMap, typename SourceMap>
2.166 + const UndirGraphCopy& nodeMap(TargetMap& tMap,
2.167 + const SourceMap& sMap) const {
2.168 + copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
2.169 + return *this;
2.170 + }
2.171 +
2.172 + /// \brief Make copy of the given map.
2.173 + ///
2.174 + /// Makes copy of the given map for the newly created graph.
2.175 + /// The new map's key type is the target graph's edge type,
2.176 + /// and the copied map's key type is the source graph's edge
2.177 + /// type.
2.178 + template <typename TargetMap, typename SourceMap>
2.179 + const UndirGraphCopy& edgeMap(TargetMap& tMap,
2.180 + const SourceMap& sMap) const {
2.181 + copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
2.182 + return *this;
2.183 + }
2.184 +
2.185 + /// \brief Make copy of the given map.
2.186 + ///
2.187 + /// Makes copy of the given map for the newly created graph.
2.188 + /// The new map's key type is the target graph's edge type,
2.189 + /// and the copied map's key type is the source graph's edge
2.190 + /// type.
2.191 + template <typename TargetMap, typename SourceMap>
2.192 + const UndirGraphCopy& undirEdgeMap(TargetMap& tMap,
2.193 + const SourceMap& sMap) const {
2.194 + copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
2.195 + return *this;
2.196 + }
2.197 +
2.198 + /// \brief Gives back the stored node references.
2.199 + ///
2.200 + /// Gives back the stored node references.
2.201 + const NodeRefMap& nodeRef() const {
2.202 + return nodeRefMap;
2.203 + }
2.204 +
2.205 + /// \brief Gives back the stored edge references.
2.206 + ///
2.207 + /// Gives back the stored edge references.
2.208 + const EdgeRefMap& edgeRef() const {
2.209 + return edgeRefMap;
2.210 + }
2.211 +
2.212 + /// \brief Gives back the stored undir edge references.
2.213 + ///
2.214 + /// Gives back the stored undir edge references.
2.215 + const UndirEdgeRefMap& undirEdgeRef() const {
2.216 + return undirEdgeRefMap;
2.217 + }
2.218 +
2.219 + void run() {}
2.220 +
2.221 + private:
2.222
2.223 - typedef _Graph Graph;
2.224 + const Source& source;
2.225 + Target& target;
2.226
2.227 - typedef typename Graph::Node Item;
2.228 - typedef typename Graph::NodeIt ItemIt;
2.229 -
2.230 - template <typename _Value>
2.231 - class Map : public Graph::template NodeMap<_Value> {
2.232 - public:
2.233 - typedef typename Graph::template NodeMap<_Value> Parent;
2.234 - typedef typename Parent::Value Value;
2.235 -
2.236 - Map(const Graph& _graph) : Parent(_graph) {}
2.237 - Map(const Graph& _graph, const Value& _value)
2.238 - : Parent(_graph, _value) {}
2.239 - };
2.240 -
2.241 + NodeRefMap nodeRefMap;
2.242 + EdgeRefMap edgeRefMap;
2.243 + UndirEdgeRefMap undirEdgeRefMap;
2.244 };
2.245
2.246 - template <typename _Graph>
2.247 - class ItemSetTraits<_Graph, typename _Graph::Edge> {
2.248 - public:
2.249 -
2.250 - typedef _Graph Graph;
2.251 + /// \brief Copy a graph to an other graph.
2.252 + ///
2.253 + /// Copy a graph to an other graph.
2.254 + /// The usage of the function:
2.255 + ///
2.256 + /// \code
2.257 + /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
2.258 + /// \endcode
2.259 + ///
2.260 + /// After the copy the \c nr map will contain the mapping from the
2.261 + /// source graph's nodes to the target graph's nodes and the \c ecr will
2.262 + /// contain the mapping from the target graph's edges to the source's
2.263 + /// edges.
2.264 + template <typename Target, typename Source>
2.265 + UndirGraphCopy<Target, Source>
2.266 + copyUndirGraph(Target& target, const Source& source) {
2.267 + return UndirGraphCopy<Target, Source>(target, source);
2.268 + }
2.269
2.270 - typedef typename Graph::Edge Item;
2.271 - typedef typename Graph::EdgeIt ItemIt;
2.272 -
2.273 - template <typename _Value>
2.274 - class Map : public Graph::template EdgeMap<_Value> {
2.275 - public:
2.276 - typedef typename Graph::template EdgeMap<_Value> Parent;
2.277 - typedef typename Parent::Value Value;
2.278 -
2.279 - Map(const Graph& _graph) : Parent(_graph) {}
2.280 - Map(const Graph& _graph, const Value& _value)
2.281 - : Parent(_graph, _value) {}
2.282 - };
2.283 -
2.284 - };
2.285 -
2.286 - template <typename _Graph>
2.287 - class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
2.288 - public:
2.289 -
2.290 - typedef _Graph Graph;
2.291 -
2.292 - typedef typename Graph::UndirEdge Item;
2.293 - typedef typename Graph::UndirEdgeIt ItemIt;
2.294 -
2.295 - template <typename _Value>
2.296 - class Map : public Graph::template UndirEdgeMap<_Value> {
2.297 - public:
2.298 - typedef typename Graph::template UndirEdgeMap<_Value> Parent;
2.299 - typedef typename Parent::Value Value;
2.300 -
2.301 - Map(const Graph& _graph) : Parent(_graph) {}
2.302 - Map(const Graph& _graph, const Value& _value)
2.303 - : Parent(_graph, _value) {}
2.304 - };
2.305 -
2.306 - };
2.307
2.308 /// @}
2.309
2.310 /// \addtogroup graph_maps
2.311 /// @{
2.312
2.313 - template <typename Map, typename Enable = void>
2.314 - struct ReferenceMapTraits {
2.315 - typedef typename Map::Value Value;
2.316 - typedef typename Map::Value& Reference;
2.317 - typedef const typename Map::Value& ConstReference;
2.318 - typedef typename Map::Value* Pointer;
2.319 - typedef const typename Map::Value* ConstPointer;
2.320 - };
2.321 -
2.322 - template <typename Map>
2.323 - struct ReferenceMapTraits<
2.324 - Map,
2.325 - typename enable_if<typename Map::FullTypeTag, void>::type
2.326 - > {
2.327 - typedef typename Map::Value Value;
2.328 - typedef typename Map::Reference Reference;
2.329 - typedef typename Map::ConstReference ConstReference;
2.330 - typedef typename Map::Pointer Pointer;
2.331 - typedef typename Map::ConstPointer ConstPointer;
2.332 - };
2.333 -
2.334 /// Provides an immutable and unique id for each item in the graph.
2.335
2.336 /// The IdMap class provides a unique and immutable id for each item of the
2.337 @@ -754,7 +880,7 @@
2.338 /// \brief The getter function of the map.
2.339 ///
2.340 /// It gives back the value associated with the key.
2.341 - const Value operator[](const Key& key) const {
2.342 + Value operator[](const Key& key) const {
2.343 return Map::operator[](key);
2.344 }
2.345
2.346 @@ -1192,234 +1318,6 @@
2.347 return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
2.348 }
2.349
2.350 - /// \brief Container for store values for each ordered pair of nodes
2.351 - ///
2.352 - /// Container for store values for each ordered pair of nodes.
2.353 - template <typename _Graph, typename _Value>
2.354 - class NodeMatrixMap
2.355 - : protected AlterationNotifier<typename _Graph::Node>::ObserverBase {
2.356 - public:
2.357 - typedef _Graph Graph;
2.358 - typedef typename Graph::Node Node;
2.359 - typedef Node Key;
2.360 - typedef _Value Value;
2.361 -
2.362 - /// \brief Creates a node matrix for the given graph
2.363 - ///
2.364 - /// Creates a node matrix for the given graph.
2.365 - NodeMatrixMap(const Graph& _graph)
2.366 - : graph(_graph), values(size(_graph.maxId(Node()) + 1)) {}
2.367 -
2.368 - /// \brief Creates a node matrix for the given graph
2.369 - ///
2.370 - /// Creates a node matrix for the given graph and assigns each
2.371 - /// initial value to the given parameter.
2.372 - NodeMatrixMap(const Graph& _graph, const Value& _val)
2.373 - : graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {}
2.374 -
2.375 - /// \brief Gives back the value assigned to the \c left - \c right
2.376 - /// ordered pair.
2.377 - ///
2.378 - /// Gives back the value assigned to the \c left - \c right ordered pair.
2.379 - const Value& operator()(const Node& left, const Node& right) const {
2.380 - return values[index(graph.id(left), graph.id(right))];
2.381 - }
2.382 -
2.383 - /// \brief Gives back the value assigned to the \c left - \c right
2.384 - /// ordered pair.
2.385 - ///
2.386 - /// Gives back the value assigned to the \c left - \c right ordered pair.
2.387 - Value& operator()(const Node& left, const Node& right) {
2.388 - return values[index(graph.id(left), graph.id(right))];
2.389 - }
2.390 -
2.391 - /// \brief Setter function for the matrix map.
2.392 - ///
2.393 - /// Setter function for the matrix map.
2.394 - void set(const Node& left, const Node& right, const Value& val) {
2.395 - values[index(graph.id(left), graph.id(right))] = val;
2.396 - }
2.397 -
2.398 - /// \brief Map for the coloumn view of the matrix
2.399 - ///
2.400 - /// Map for the coloumn view of the matrix.
2.401 - class ColMap : public MapBase<Node, Value> {
2.402 - friend class NodeMatrixMap;
2.403 - private:
2.404 - ColMap(NodeMatrixMap& _matrix, Node _col)
2.405 - : matrix(_matrix), col(_col) {}
2.406 -
2.407 - public:
2.408 - /// \brief Subscription operator
2.409 - ///
2.410 - /// Subscription operator.
2.411 - Value& operator[](Node row) {
2.412 - return matrix(col, row);
2.413 - }
2.414 -
2.415 - /// \brief Setter function
2.416 - ///
2.417 - /// Setter function.
2.418 - void set(Node row, const Value& val) {
2.419 - matrix.set(col, row, val);
2.420 - }
2.421 -
2.422 - /// \brief Subscription operator
2.423 - ///
2.424 - /// Subscription operator.
2.425 - const Value& operator[](Node row) const {
2.426 - return matrix(col, row);
2.427 - }
2.428 -
2.429 - private:
2.430 - NodeMatrixMap& matrix;
2.431 - Node col;
2.432 - };
2.433 -
2.434 - /// \brief Map for the const coloumn view of the matrix
2.435 - ///
2.436 - /// Map for the const coloumn view of the matrix.
2.437 - class ConstColMap : public MapBase<Node, Value> {
2.438 - friend class NodeMatrixMap;
2.439 - private:
2.440 - ConstColMap(const NodeMatrixMap& _matrix, Node _col)
2.441 - : matrix(_matrix), col(_col) {}
2.442 -
2.443 - public:
2.444 - /// \brief Subscription operator
2.445 - ///
2.446 - /// Subscription operator.
2.447 - const Value& operator[](Node row) const {
2.448 - return matrix(col, row);
2.449 - }
2.450 -
2.451 - private:
2.452 - const NodeMatrixMap& matrix;
2.453 - Node col;
2.454 - };
2.455 -
2.456 - /// \brief Map for the row view of the matrix
2.457 - ///
2.458 - /// Map for the row view of the matrix.
2.459 - class RowMap : public MapBase<Node, Value> {
2.460 - public:
2.461 - friend class NodeMatrixMap;
2.462 - private:
2.463 - RowMap(NodeMatrixMap& _matrix, Node _row)
2.464 - : matrix(_matrix), row(_row) {}
2.465 -
2.466 - public:
2.467 - /// \brief Subscription operator
2.468 - ///
2.469 - /// Subscription operator.
2.470 - Value& operator[](Node col) {
2.471 - return matrix(col, row);
2.472 - }
2.473 -
2.474 - /// \brief Setter function
2.475 - ///
2.476 - /// Setter function.
2.477 - void set(Node col, const Value& val) {
2.478 - matrix.set(col, row, val);
2.479 - }
2.480 -
2.481 - /// \brief Subscription operator
2.482 - ///
2.483 - /// Subscription operator.
2.484 - const Value& operator[](Node col) const {
2.485 - return matrix(col, row);
2.486 - }
2.487 -
2.488 - private:
2.489 - NodeMatrixMap& matrix;
2.490 - Node row;
2.491 - };
2.492 -
2.493 - /// \brief Map for the const row view of the matrix
2.494 - ///
2.495 - /// Map for the row const view of the matrix.
2.496 - class ConstRowMap : public MapBase<Node, Value> {
2.497 - public:
2.498 - friend class NodeMatrixMap;
2.499 - private:
2.500 - ConstRowMap(const NodeMatrixMap& _matrix, Node _row)
2.501 - : matrix(_matrix), row(_row) {}
2.502 -
2.503 - public:
2.504 - /// \brief Subscription operator
2.505 - ///
2.506 - /// Subscription operator.
2.507 - const Value& operator[](Node col) const {
2.508 - return matrix(col, row);
2.509 - }
2.510 -
2.511 - private:
2.512 - const NodeMatrixMap& matrix;
2.513 - Node row;
2.514 - };
2.515 -
2.516 - /// \brief Gives back the column view for the given node
2.517 - ///
2.518 - /// Gives back the column view for the given node
2.519 - ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }
2.520 - /// \brief Gives back the column view for the given node
2.521 - ///
2.522 - /// Gives back the column view for the given node
2.523 - ColMap operator[](Node col) { return ColMap(*this, col); }
2.524 -
2.525 - /// \brief Gives back the column view for the given node
2.526 - ///
2.527 - /// Gives back the column view for the given node
2.528 - ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }
2.529 - /// \brief Gives back the column view for the given node
2.530 - ///
2.531 - /// Gives back the column view for the given node
2.532 - ColMap colMap(Node col) { return ColMap(*this, col); }
2.533 -
2.534 - /// \brief Gives back the row view for the given node
2.535 - ///
2.536 - /// Gives back the row view for the given node
2.537 - ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }
2.538 - /// \brief Gives back the row view for the given node
2.539 - ///
2.540 - /// Gives back the row view for the given node
2.541 - RowMap rowMap(Node row) { return RowMap(*this, row); }
2.542 -
2.543 - protected:
2.544 -
2.545 - static int index(int i, int j) {
2.546 - if (i < j) {
2.547 - return j * j + i;
2.548 - } else {
2.549 - return i * i + i + j;
2.550 - }
2.551 - }
2.552 -
2.553 - static int size(int s) {
2.554 - return s * s;
2.555 - }
2.556 -
2.557 - void add(const Node& node) {
2.558 - if (size(graph.id(node) + 1) >= (int)values.size()) {
2.559 - values.resize(size(graph.id(node) + 1));
2.560 - }
2.561 - }
2.562 -
2.563 - void erase(const Node&) {}
2.564 -
2.565 - void build() {
2.566 - values.resize(size(graph.maxId(Node()) + 1));
2.567 - }
2.568 -
2.569 - void clear() {
2.570 - values.clear();
2.571 - }
2.572 -
2.573 - private:
2.574 - const Graph& graph;
2.575 - std::vector<Value> values;
2.576 - };
2.577 -
2.578 /// \brief Map of the node in-degrees.
2.579 ///
2.580 /// This map returns the in-degree of a node. Once it is constructed,
2.581 @@ -1427,14 +1325,6 @@
2.582 /// in constant time. On the other hand, the values are updated automatically
2.583 /// whenever the graph changes.
2.584 ///
2.585 - /// \warning Besides addNode() and addEdge(), a graph structure may provide
2.586 - /// alternative ways to mogify the graph. The correct behavior of InDegMap
2.587 - /// is not guarantied if these additional featureas are used. For example
2.588 - /// the funstions \ref ListGraph::changeSource() "changeSource()",
2.589 - /// \ref ListGraph::changeTarget() "changeTarget()" and
2.590 - /// \ref ListGraph::reverseEdge() "reverseEdge()"
2.591 - /// of \ref ListGraph will \e not update the degree values correctly.
2.592 - ///
2.593 /// \sa OutDegMap
2.594
2.595 template <typename _Graph>
2.596 @@ -1501,6 +1391,13 @@
2.597 --deg[graph.target(edge)];
2.598 }
2.599
2.600 + virtual void signalChange(const Edge& edge) {
2.601 + erase(edge);
2.602 + }
2.603 +
2.604 + virtual void commitChange(const Edge& edge) {
2.605 + add(edge);
2.606 + }
2.607
2.608 virtual void build() {
2.609 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2.610 @@ -1526,14 +1423,6 @@
2.611 /// in constant time. On the other hand, the values are updated automatically
2.612 /// whenever the graph changes.
2.613 ///
2.614 - /// \warning Besides addNode() and addEdge(), a graph structure may provide
2.615 - /// alternative ways to mogify the graph. The correct behavior of OutDegMap
2.616 - /// is not guarantied if these additional featureas are used. For example
2.617 - /// the funstions \ref ListGraph::changeSource() "changeSource()",
2.618 - /// \ref ListGraph::changeTarget() "changeTarget()" and
2.619 - /// \ref ListGraph::reverseEdge() "reverseEdge()"
2.620 - /// of \ref ListGraph will \e not update the degree values correctly.
2.621 - ///
2.622 /// \sa InDegMap
2.623
2.624 template <typename _Graph>
2.625 @@ -1600,6 +1489,14 @@
2.626 --deg[graph.source(edge)];
2.627 }
2.628
2.629 + virtual void signalChange(const Edge& edge) {
2.630 + erase(edge);
2.631 + }
2.632 +
2.633 + virtual void commitChange(const Edge& edge) {
2.634 + add(edge);
2.635 + }
2.636 +
2.637
2.638 virtual void build() {
2.639 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
2.640 @@ -1618,47 +1515,6 @@
2.641 AutoNodeMap deg;
2.642 };
2.643
2.644 - // Indicators for the tags
2.645 -
2.646 - template <typename Graph, typename Enable = void>
2.647 - struct NodeNumTagIndicator {
2.648 - static const bool value = false;
2.649 - };
2.650 -
2.651 - template <typename Graph>
2.652 - struct NodeNumTagIndicator<
2.653 - Graph,
2.654 - typename enable_if<typename Graph::NodeNumTag, void>::type
2.655 - > {
2.656 - static const bool value = true;
2.657 - };
2.658 -
2.659 - template <typename Graph, typename Enable = void>
2.660 - struct EdgeNumTagIndicator {
2.661 - static const bool value = false;
2.662 - };
2.663 -
2.664 - template <typename Graph>
2.665 - struct EdgeNumTagIndicator<
2.666 - Graph,
2.667 - typename enable_if<typename Graph::EdgeNumTag, void>::type
2.668 - > {
2.669 - static const bool value = true;
2.670 - };
2.671 -
2.672 - template <typename Graph, typename Enable = void>
2.673 - struct FindEdgeTagIndicator {
2.674 - static const bool value = false;
2.675 - };
2.676 -
2.677 - template <typename Graph>
2.678 - struct FindEdgeTagIndicator<
2.679 - Graph,
2.680 - typename enable_if<typename Graph::FindEdgeTag, void>::type
2.681 - > {
2.682 - static const bool value = true;
2.683 - };
2.684 -
2.685
2.686 /// @}
2.687
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/matrix_maps.h Fri Oct 14 10:49:51 2005 +0000
3.3 @@ -0,0 +1,428 @@
3.4 +/* -*- C++ -*-
3.5 + * lemon/matrix_maps.h - Part of LEMON, a generic C++ optimization library
3.6 + *
3.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.9 + *
3.10 + * Permission to use, modify and distribute this software is granted
3.11 + * provided that this copyright notice appears in all copies. For
3.12 + * precise terms see the accompanying LICENSE file.
3.13 + *
3.14 + * This software is provided "AS IS" with no warranty of any kind,
3.15 + * express or implied, and with no claim as to its suitability for any
3.16 + * purpose.
3.17 + *
3.18 + */
3.19 +
3.20 +#ifndef LEMON_MATRIX_MAPS_H
3.21 +#define LEMON_MATRIX_MAPS_H
3.22 +
3.23 +
3.24 +#include <vector>
3.25 +#include <lemon/utility.h>
3.26 +#include <lemon/maps.h>
3.27 +
3.28 +
3.29 +/// \file
3.30 +/// \ingroup maps
3.31 +/// \brief Maps indexed with pairs of items.
3.32 +///
3.33 +/// \todo This file has the same name as the concept file in concept/,
3.34 +/// and this is not easily detectable in docs...
3.35 +namespace lemon {
3.36 +
3.37 + /// \brief Map for the coloumn view of the matrix
3.38 + ///
3.39 + /// Map for the coloumn view of the matrix.
3.40 + template <typename _MatrixMap>
3.41 + class MatrixColMap : public MapTraits<_MatrixMap> {
3.42 + public:
3.43 + typedef _MatrixMap MatrixMap;
3.44 + typedef typename MatrixMap::SecondKey Key;
3.45 + typedef typename MatrixMap::Value Value;
3.46 +
3.47 +
3.48 + MatrixColMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _col)
3.49 + : matrix(_matrix), col(_col) {}
3.50 +
3.51 + /// \brief Subscription operator
3.52 + ///
3.53 + /// Subscription operator.
3.54 + typename MapTraits<MatrixMap>::ReturnValue
3.55 + operator[](Key row) {
3.56 + return matrix(col, row);
3.57 + }
3.58 +
3.59 + /// \brief Setter function
3.60 + ///
3.61 + /// Setter function.
3.62 + void set(Key row, const Value& val) {
3.63 + matrix.set(col, row, val);
3.64 + }
3.65 +
3.66 + /// \brief Subscription operator
3.67 + ///
3.68 + /// Subscription operator.
3.69 + typename MapTraits<MatrixMap>::ConstReturnValue
3.70 + operator[](Key row) const {
3.71 + return matrix(col, row);
3.72 + }
3.73 +
3.74 + private:
3.75 + MatrixMap& matrix;
3.76 + typename MatrixMap::FirstKey col;
3.77 + };
3.78 +
3.79 + /// \brief Map for the coloumn view of the matrix
3.80 + ///
3.81 + /// Map for the coloumn view of the matrix.
3.82 + template <typename _MatrixMap>
3.83 + class ConstMatrixColMap : public MapTraits<_MatrixMap> {
3.84 + public:
3.85 + typedef _MatrixMap MatrixMap;
3.86 + typedef typename MatrixMap::SecondKey Key;
3.87 + typedef typename MatrixMap::Value Value;
3.88 +
3.89 +
3.90 + ConstMatrixColMap(const MatrixMap& _matrix,
3.91 + typename MatrixMap::FirstKey _col)
3.92 + : matrix(_matrix), col(_col) {}
3.93 +
3.94 + /// \brief Subscription operator
3.95 + ///
3.96 + /// Subscription operator.
3.97 + typename MapTraits<MatrixMap>::ConstReturnValue
3.98 + operator[](Key row) const {
3.99 + return matrix(col, row);
3.100 + }
3.101 +
3.102 + private:
3.103 + const MatrixMap& matrix;
3.104 + typename MatrixMap::FirstKey col;
3.105 + };
3.106 +
3.107 + /// \brief Gives back a coloumn view of the matrix map
3.108 + ///
3.109 + /// Gives back a coloumn view of the matrix map.
3.110 + template <typename MatrixMap>
3.111 + MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
3.112 + typename MatrixMap::FirstKey col) {
3.113 + return MatrixColMap<MatrixMap>(matrixMap, col);
3.114 + }
3.115 +
3.116 + template <typename MatrixMap>
3.117 + ConstMatrixColMap<MatrixMap>
3.118 + matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey col) {
3.119 + return ConstMatrixColMap<MatrixMap>(matrixMap, col);
3.120 + }
3.121 +
3.122 + /// \brief Map for the row view of the matrix
3.123 + ///
3.124 + /// Map for the row view of the matrix.
3.125 + template <typename _MatrixMap>
3.126 + class MatrixRowMap : public MapTraits<_MatrixMap> {
3.127 + public:
3.128 + typedef _MatrixMap MatrixMap;
3.129 + typedef typename MatrixMap::FirstKey Key;
3.130 + typedef typename MatrixMap::Value Value;
3.131 +
3.132 + MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _row)
3.133 + : matrix(_matrix), row(_row) {}
3.134 +
3.135 + /// \brief Subscription operator
3.136 + ///
3.137 + /// Subscription operator.
3.138 + typename MapTraits<MatrixMap>::ReturnValue
3.139 + operator[](Key col) {
3.140 + return matrix(col, row);
3.141 + }
3.142 +
3.143 + /// \brief Setter function
3.144 + ///
3.145 + /// Setter function.
3.146 + void set(Key col, const Value& val) {
3.147 + matrix.set(col, row, val);
3.148 + }
3.149 +
3.150 + /// \brief Subscription operator
3.151 + ///
3.152 + /// Subscription operator.
3.153 + typename MapTraits<MatrixMap>::ConstReturnValue
3.154 + operator[](Key col) const {
3.155 + return matrix(col, row);
3.156 + }
3.157 +
3.158 + private:
3.159 + MatrixMap& matrix;
3.160 + typename MatrixMap::SecondKey row;
3.161 + };
3.162 +
3.163 + /// \brief Map for the row view of the matrix
3.164 + ///
3.165 + /// Map for the row view of the matrix.
3.166 + template <typename _MatrixMap>
3.167 + class ConstMatrixRowMap : public MapTraits<_MatrixMap> {
3.168 + public:
3.169 + typedef _MatrixMap MatrixMap;
3.170 + typedef typename MatrixMap::FirstKey Key;
3.171 + typedef typename MatrixMap::Value Value;
3.172 +
3.173 + ConstMatrixRowMap(const MatrixMap& _matrix,
3.174 + typename MatrixMap::SecondKey _row)
3.175 + : matrix(_matrix), row(_row) {}
3.176 +
3.177 + /// \brief Subscription operator
3.178 + ///
3.179 + /// Subscription operator.
3.180 + typename MapTraits<MatrixMap>::ConstReturnValue
3.181 + operator[](Key col) const {
3.182 + return matrix(col, row);
3.183 + }
3.184 +
3.185 + private:
3.186 + const MatrixMap& matrix;
3.187 + typename MatrixMap::SecondKey row;
3.188 + };
3.189 +
3.190 + /// \brief Gives back a row view of the matrix map
3.191 + ///
3.192 + /// Gives back a row view of the matrix map.
3.193 + template <typename MatrixMap>
3.194 + MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
3.195 + typename MatrixMap::SecondKey row) {
3.196 + return MatrixRowMap<MatrixMap>(matrixMap, row);
3.197 + }
3.198 +
3.199 + template <typename MatrixMap>
3.200 + ConstMatrixRowMap<MatrixMap>
3.201 + matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey row) {
3.202 + return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
3.203 + }
3.204 +
3.205 + /// \brief Container for store values for each ordered pair of graph items
3.206 + ///
3.207 + /// This data structure can strore for each pairs of the same item
3.208 + /// type a value. It increase the size of the container when the
3.209 + /// associated graph modified, so it updated automaticly whenever
3.210 + /// it is needed.
3.211 + template <typename _Graph, typename _Item, typename _Value>
3.212 + class DynamicMatrixMap
3.213 + : protected AlterationNotifier<_Item>::ObserverBase {
3.214 + public:
3.215 + typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
3.216 +
3.217 + typedef _Graph Graph;
3.218 + typedef _Item Key;
3.219 +
3.220 + typedef _Item FirstKey;
3.221 + typedef _Item SecondKey;
3.222 + typedef _Value Value;
3.223 +
3.224 + typedef True ReferenceMapTag;
3.225 +
3.226 + private:
3.227 +
3.228 + typedef std::vector<Value> Container;
3.229 +
3.230 + public:
3.231 +
3.232 + typedef typename Container::reference Reference;
3.233 + typedef typename Container::const_reference ConstReference;
3.234 +
3.235 + /// \brief Creates an item matrix for the given graph
3.236 + ///
3.237 + /// Creates an item matrix for the given graph.
3.238 + DynamicMatrixMap(const Graph& _graph)
3.239 + : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
3.240 + Parent::attach(graph.getNotifier(Key()));
3.241 + }
3.242 +
3.243 + /// \brief Creates an item matrix for the given graph
3.244 + ///
3.245 + /// Creates an item matrix for the given graph and assigns for each
3.246 + /// pairs of keys the given parameter.
3.247 + DynamicMatrixMap(const Graph& _graph, const Value& _val)
3.248 + : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
3.249 + Parent::attach(graph.getNotifier(Key()));
3.250 + }
3.251 +
3.252 + ~DynamicMatrixMap() {
3.253 + if (Parent::attached()) {
3.254 + Parent::detach();
3.255 + }
3.256 + }
3.257 +
3.258 + /// \brief Gives back the value assigned to the \c first - \c second
3.259 + /// ordered pair.
3.260 + ///
3.261 + /// Gives back the value assigned to the \c first - \c second ordered pair.
3.262 + ConstReference operator()(const Key& first, const Key& second) const {
3.263 + return values[index(graph.id(first), graph.id(second))];
3.264 + }
3.265 +
3.266 + /// \brief Gives back the value assigned to the \c first - \c second
3.267 + /// ordered pair.
3.268 + ///
3.269 + /// Gives back the value assigned to the \c first - \c second ordered pair.
3.270 + Reference operator()(const Key& first, const Key& second) {
3.271 + return values[index(graph.id(first), graph.id(second))];
3.272 + }
3.273 +
3.274 + /// \brief Setter function for the matrix map.
3.275 + ///
3.276 + /// Setter function for the matrix map.
3.277 + void set(const Key& first, const Key& second, const Value& val) {
3.278 + values[index(graph.id(first), graph.id(second))] = val;
3.279 + }
3.280 +
3.281 + protected:
3.282 +
3.283 + static int index(int i, int j) {
3.284 + if (i < j) {
3.285 + return j * j + i;
3.286 + } else {
3.287 + return i * i + i + j;
3.288 + }
3.289 + }
3.290 +
3.291 + static int size(int s) {
3.292 + return s * s;
3.293 + }
3.294 +
3.295 + virtual void add(const Key& key) {
3.296 + if (size(graph.id(key) + 1) >= (int)values.size()) {
3.297 + values.resize(size(graph.id(key) + 1));
3.298 + }
3.299 + }
3.300 +
3.301 + virtual void erase(const Key&) {}
3.302 +
3.303 + virtual void build() {
3.304 + values.resize(size(graph.maxId(Key()) + 1));
3.305 + }
3.306 +
3.307 + virtual void clear() {
3.308 + values.clear();
3.309 + }
3.310 +
3.311 + private:
3.312 + const Graph& graph;
3.313 + std::vector<Value> values;
3.314 + };
3.315 +
3.316 + /// \brief Container for store values for each unordered pair of graph items
3.317 + ///
3.318 + /// This data structure can strore for each pairs of the same item
3.319 + /// type a value. It increase the size of the container when the
3.320 + /// associated graph modified, so it updated automaticly whenever
3.321 + /// it is needed.
3.322 + template <typename _Graph, typename _Item, typename _Value>
3.323 + class DynamicSymMatrixMap
3.324 + : protected AlterationNotifier<_Item>::ObserverBase {
3.325 + public:
3.326 + typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
3.327 +
3.328 + typedef _Graph Graph;
3.329 + typedef _Item Key;
3.330 +
3.331 + typedef _Item FirstKey;
3.332 + typedef _Item SecondKey;
3.333 + typedef _Value Value;
3.334 +
3.335 + typedef True ReferenceMapTag;
3.336 +
3.337 + private:
3.338 +
3.339 + typedef std::vector<Value> Container;
3.340 +
3.341 + public:
3.342 +
3.343 + typedef typename Container::reference Reference;
3.344 + typedef typename Container::const_reference ConstReference;
3.345 +
3.346 + /// \brief Creates an item matrix for the given graph
3.347 + ///
3.348 + /// Creates an item matrix for the given graph.
3.349 + DynamicSymMatrixMap(const Graph& _graph)
3.350 + : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
3.351 + Parent::attach(graph.getNotifier(Key()));
3.352 + }
3.353 +
3.354 + /// \brief Creates an item matrix for the given graph
3.355 + ///
3.356 + /// Creates an item matrix for the given graph and assigns for each
3.357 + /// pairs of keys the given parameter.
3.358 + DynamicSymMatrixMap(const Graph& _graph, const Value& _val)
3.359 + : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
3.360 + Parent::attach(graph.getNotifier(Key()));
3.361 + }
3.362 +
3.363 + ~DynamicSymMatrixMap() {
3.364 + if (Parent::attached()) {
3.365 + Parent::detach();
3.366 + }
3.367 + }
3.368 +
3.369 + /// \brief Gives back the value assigned to the \c first - \c second
3.370 + /// unordered pair.
3.371 + ///
3.372 + /// Gives back the value assigned to the \c first - \c second unordered
3.373 + /// pair.
3.374 + ConstReference operator()(const Key& first, const Key& second) const {
3.375 + return values[index(graph.id(first), graph.id(second))];
3.376 + }
3.377 +
3.378 + /// \brief Gives back the value assigned to the \c first - \c second
3.379 + /// unordered pair.
3.380 + ///
3.381 + /// Gives back the value assigned to the \c first - \c second unordered
3.382 + /// pair.
3.383 + Reference operator()(const Key& first, const Key& second) {
3.384 + return values[index(graph.id(first), graph.id(second))];
3.385 + }
3.386 +
3.387 + /// \brief Setter function for the matrix map.
3.388 + ///
3.389 + /// Setter function for the matrix map.
3.390 + void set(const Key& first, const Key& second, const Value& val) {
3.391 + values[index(graph.id(first), graph.id(second))] = val;
3.392 + }
3.393 +
3.394 + protected:
3.395 +
3.396 + static int index(int i, int j) {
3.397 + if (i < j) {
3.398 + return j * (j + 1) / 2 + i;
3.399 + } else {
3.400 + return i * (i + 1) / 2 + j;
3.401 + }
3.402 + }
3.403 +
3.404 + static int size(int s) {
3.405 + return s * (s + 1) / 2;
3.406 + }
3.407 +
3.408 + virtual void add(const Key& key) {
3.409 + if (size(graph.id(key) + 1) >= (int)values.size()) {
3.410 + values.resize(size(graph.id(key) + 1));
3.411 + }
3.412 + }
3.413 +
3.414 + virtual void erase(const Key&) {}
3.415 +
3.416 + virtual void build() {
3.417 + values.resize(size(graph.maxId(Key()) + 1));
3.418 + }
3.419 +
3.420 + virtual void clear() {
3.421 + values.clear();
3.422 + }
3.423 +
3.424 + private:
3.425 + const Graph& graph;
3.426 + std::vector<Value> values;
3.427 + };
3.428 +
3.429 +}
3.430 +
3.431 +#endif