Empty graph is (strongly) connected.
2 * lemon/matrix_maps.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
17 #ifndef LEMON_MATRIX_MAPS_H
18 #define LEMON_MATRIX_MAPS_H
22 #include <lemon/utility.h>
23 #include <lemon/maps.h>
28 /// \brief Maps indexed with pairs of items.
30 /// \todo This file has the same name as the concept file in concept/,
31 /// and this is not easily detectable in docs...
34 /// \brief Map for the coloumn view of the matrix
36 /// Map for the coloumn view of the matrix.
37 template <typename _MatrixMap>
38 class MatrixRowMap : public MapTraits<_MatrixMap> {
40 typedef _MatrixMap MatrixMap;
41 typedef typename MatrixMap::SecondKey Key;
42 typedef typename MatrixMap::Value Value;
45 MatrixRowMap(MatrixMap& _matrix, typename MatrixMap::FirstKey _row)
46 : matrix(_matrix), row(_row) {}
48 /// \brief Subscription operator
50 /// Subscription operator.
51 typename MapTraits<MatrixMap>::ReturnValue
53 return matrix(row, col);
56 /// \brief Setter function
59 void set(Key col, const Value& val) {
60 matrix.set(row, col, val);
63 /// \brief Subscription operator
65 /// Subscription operator.
66 typename MapTraits<MatrixMap>::ConstReturnValue
67 operator[](Key col) const {
68 return matrix(row, col);
73 typename MatrixMap::FirstKey row;
76 /// \brief Map for the row view of the matrix
78 /// Map for the row view of the matrix.
79 template <typename _MatrixMap>
80 class ConstMatrixRowMap : public MapTraits<_MatrixMap> {
82 typedef _MatrixMap MatrixMap;
83 typedef typename MatrixMap::SecondKey Key;
84 typedef typename MatrixMap::Value Value;
87 ConstMatrixRowMap(const MatrixMap& _matrix,
88 typename MatrixMap::FirstKey _row)
89 : matrix(_matrix), row(_row) {}
91 /// \brief Subscription operator
93 /// Subscription operator.
94 typename MapTraits<MatrixMap>::ConstReturnValue
95 operator[](Key col) const {
96 return matrix(row, col);
100 const MatrixMap& matrix;
101 typename MatrixMap::FirstKey row;
104 /// \brief Gives back a row view of the matrix map
106 /// Gives back a row view of the matrix map.
107 template <typename MatrixMap>
108 MatrixRowMap<MatrixMap> matrixRowMap(MatrixMap& matrixMap,
109 typename MatrixMap::FirstKey row) {
110 return MatrixRowMap<MatrixMap>(matrixMap, row);
113 template <typename MatrixMap>
114 ConstMatrixRowMap<MatrixMap>
115 matrixRowMap(const MatrixMap& matrixMap, typename MatrixMap::FirstKey row) {
116 return ConstMatrixRowMap<MatrixMap>(matrixMap, row);
119 /// \brief Map for the row view of the matrix
121 /// Map for the row view of the matrix.
122 template <typename _MatrixMap>
123 class MatrixColMap : public MapTraits<_MatrixMap> {
125 typedef _MatrixMap MatrixMap;
126 typedef typename MatrixMap::FirstKey Key;
127 typedef typename MatrixMap::Value Value;
129 MatrixColMap(MatrixMap& _matrix, typename MatrixMap::SecondKey _col)
130 : matrix(_matrix), col(_col) {}
132 /// \brief Subscription operator
134 /// Subscription operator.
135 typename MapTraits<MatrixMap>::ReturnValue
136 operator[](Key row) {
137 return matrix(row, col);
140 /// \brief Setter function
143 void set(Key row, const Value& val) {
144 matrix.set(row, col, val);
147 /// \brief Subscription operator
149 /// Subscription operator.
150 typename MapTraits<MatrixMap>::ConstReturnValue
151 operator[](Key row) const {
152 return matrix(row, col);
157 typename MatrixMap::SecondKey col;
160 /// \brief Map for the col view of the matrix
162 /// Map for the col view of the matrix.
163 template <typename _MatrixMap>
164 class ConstMatrixColMap : public MapTraits<_MatrixMap> {
166 typedef _MatrixMap MatrixMap;
167 typedef typename MatrixMap::FirstKey Key;
168 typedef typename MatrixMap::Value Value;
170 ConstMatrixColMap(const MatrixMap& _matrix,
171 typename MatrixMap::SecondKey _col)
172 : matrix(_matrix), col(_col) {}
174 /// \brief Subscription operator
176 /// Subscription operator.
177 typename MapTraits<MatrixMap>::ConstReturnValue
178 operator[](Key row) const {
179 return matrix(row, col);
183 const MatrixMap& matrix;
184 typename MatrixMap::SecondKey col;
187 /// \brief Gives back a col view of the matrix map
189 /// Gives back a col view of the matrix map.
190 template <typename MatrixMap>
191 MatrixColMap<MatrixMap> matrixColMap(MatrixMap& matrixMap,
192 typename MatrixMap::SecondKey col) {
193 return MatrixColMap<MatrixMap>(matrixMap, col);
196 template <typename MatrixMap>
197 ConstMatrixColMap<MatrixMap>
198 matrixColMap(const MatrixMap& matrixMap, typename MatrixMap::SecondKey col) {
199 return ConstMatrixColMap<MatrixMap>(matrixMap, col);
202 /// \brief Container for store values for each ordered pair of graph items
204 /// This data structure can strore for each pair 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
208 template <typename _Graph, typename _Item, typename _Value>
209 class DynamicMatrixMap
210 : protected AlterationNotifier<_Item>::ObserverBase {
212 typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
214 typedef _Graph Graph;
217 typedef _Item FirstKey;
218 typedef _Item SecondKey;
219 typedef _Value Value;
221 typedef True ReferenceMapTag;
225 typedef std::vector<Value> Container;
229 typedef typename Container::reference Reference;
230 typedef typename Container::const_reference ConstReference;
232 /// \brief Creates an item matrix for the given graph
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()));
240 /// \brief Creates an item matrix for the given graph
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()));
249 ~DynamicMatrixMap() {
250 if (Parent::attached()) {
255 /// \brief Gives back the value assigned to the \c first - \c second
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))];
263 /// \brief Gives back the value assigned to the \c first - \c second
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))];
271 /// \brief Setter function for the matrix map.
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;
280 static int index(int i, int j) {
284 return i * i + i + j;
288 static int size(int s) {
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));
298 virtual void erase(const Key&) {}
300 virtual void build() {
301 values.resize(size(graph.maxId(Key()) + 1));
304 virtual void clear() {
310 std::vector<Value> values;
313 /// \brief Container for store values for each unordered pair of graph items
315 /// This data structure can strore for each pair 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
319 template <typename _Graph, typename _Item, typename _Value>
320 class DynamicSymMatrixMap
321 : protected AlterationNotifier<_Item>::ObserverBase {
323 typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
325 typedef _Graph Graph;
328 typedef _Item FirstKey;
329 typedef _Item SecondKey;
330 typedef _Value Value;
332 typedef True ReferenceMapTag;
336 typedef std::vector<Value> Container;
340 typedef typename Container::reference Reference;
341 typedef typename Container::const_reference ConstReference;
343 /// \brief Creates an item matrix for the given graph
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()));
351 /// \brief Creates an item matrix for the given graph
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()));
360 ~DynamicSymMatrixMap() {
361 if (Parent::attached()) {
366 /// \brief Gives back the value assigned to the \c first - \c second
369 /// Gives back the value assigned to the \c first - \c second unordered
371 ConstReference operator()(const Key& first, const Key& second) const {
372 return values[index(graph.id(first), graph.id(second))];
375 /// \brief Gives back the value assigned to the \c first - \c second
378 /// Gives back the value assigned to the \c first - \c second unordered
380 Reference operator()(const Key& first, const Key& second) {
381 return values[index(graph.id(first), graph.id(second))];
384 /// \brief Setter function for the matrix map.
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;
393 static int index(int i, int j) {
395 return j * (j + 1) / 2 + i;
397 return i * (i + 1) / 2 + j;
401 static int size(int s) {
402 return s * (s + 1) / 2;
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));
411 virtual void erase(const Key&) {}
413 virtual void build() {
414 values.resize(size(graph.maxId(Key()) + 1));
417 virtual void clear() {
423 std::vector<Value> values;