Debian Codegraph @

dune/istl/paamg/dependency.hh

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 #ifndef DUNE_AMG_DEPENDENCY_HH
6 #define DUNE_AMG_DEPENDENCY_HH
7
8
9 #include <bitset>
10 #include <ostream>
11
12 #include "graph.hh"
13 #include "properties.hh"
14 #include <dune/common/propertymap.hh>
15
16
17 namespace Dune
18 {
19 namespace Amg
20 {
21 /**
22 * @addtogroup ISTL_PAAMG
23 *
24 * @{
25 */
26 /** @file
27 * @author Markus Blatt
28 * @brief Provides classes for initializing the link attributes of a matrix graph.
29 */
30
31 /**
32 * @brief Class representing the properties of an edge in the matrix graph.
33 *
34 * During the coarsening process the matrix graph needs to hold different
35 * properties of its edges.
36 * This class contains methods for getting and setting these edge attributes.
37 */
38 class EdgeProperties
39 {
40 friend std::ostream& operator<<(std::ostream& os, const EdgeProperties& props);
41 public:
42 /** @brief Flags of the link.*/
43 enum {INFLUENCE, DEPEND, SIZE};
44
45 private:
46
47 std::bitset<SIZE> flags_;
48 public:
49 /** @brief Constructor. */
50 EdgeProperties();
51
52 /** @brief Access the bits directly */
53 std::bitset<SIZE>::reference operator[](std::size_t v);
54
55 /** @brief Access the bits directly */
56 bool operator[](std::size_t v) const;
57
58 /**
59 * @brief Checks whether the vertex the edge points to depends on
60 * the vertex the edge starts.
61 * @return True if it depends on the starting point.
62 */
63 bool depends() const;
64
65 /**
66 * @brief Marks the edge as one of which the end point depends on
67 * the starting point.
68 */
69 void setDepends();
70
71 /**
72 * @brief Resets the depends flag.
73 */
74 void resetDepends();
75
76 /**
77 * @brief Checks whether the start vertex is influenced by the end vertex.
78 * @return True if it is influenced.
79 */
80 bool influences() const;
81
82 /**
83 * @brief Marks the edge as one of which the start vertex by the end vertex.
84 */
85 void setInfluences();
86
87 /**
88 * @brief Resets the influence flag.
89 */
90 void resetInfluences();
91
92 /**
93 * @brief Checks whether the edge is one way.
94 * I.e. either the influence or the depends flag but is set.
95 */
96 bool isOneWay() const;
97
98 /**
99 * @brief Checks whether the edge is two way.
100 * I.e. both the influence flag and the depends flag are that.
101 */
102 bool isTwoWay() const;
103
104 /**
105 * @brief Checks whether the edge is strong.
106 * I.e. the influence or depends flag is set.
107 */
108 bool isStrong() const;
109
110 /**
111 * @brief Reset all flags.
112 */
113 void reset();
114
115 /**
116 * @brief Prints the attributes of the edge for debugging.
117 */
118 void printFlags() const;
119 };
120
121 /**
122 * @brief Class representing a node in the matrix graph.
123 *
124 * Contains methods for getting and setting node attributes.
125 */
126 class VertexProperties {
127 friend std::ostream& operator<<(std::ostream& os, const VertexProperties& props);
128 public:
129 enum { ISOLATED, VISITED, FRONT, BORDER, SIZE };
130 private:
131
132 /** @brief The attribute flags. */
133 std::bitset<SIZE> flags_;
134
135 public:
136 /** @brief Constructor. */
137 VertexProperties();
138
139 /** @brief Access the bits directly */
140 std::bitset<SIZE>::reference operator[](std::size_t v);
141
142 /** @brief Access the bits directly */
143 bool operator[](std::size_t v) const;
144
145 /**
146 * @brief Marks that node as being isolated.
147 *
148 * A node is isolated if it ha not got any strong connections to other nodes
149 * in the matrix graph.
150 */
151 void setIsolated();
152
153 /**
154 * @brief Checks whether the node is isolated.
155 */
156 bool isolated() const;
157
158 /**
159 * @brief Resets the isolated flag.
160 */
161 void resetIsolated();
162
163 /**
164 * @brief Mark the node as already visited.
165 */
166 void setVisited();
167
168 /**
169 * @brief Checks whether the node is marked as visited.
170 */
171 bool visited() const;
172
173 /**
174 * @brief Resets the visited flag.
175 */
176 void resetVisited();
177
178 /**
179 * @brief Marks the node as belonging to the current clusters front.
180 */
181 void setFront();
182
183 /**
184 * @brief Checks whether the node is marked as a front node.
185 */
186 bool front() const;
187
188 /**
189 * @brief Resets the front node flag.
190 */
191 void resetFront();
192
193 /**
194 * @brief Marks the vertex as excluded from the aggregation.
195 */
196 void setExcludedBorder();
197
198 /**
199 * @brief Tests whether the vertex is excluded from the aggregation.
200 * @return True if the vertex is excluded from the aggregation process.
201 */
202 bool excludedBorder() const;
203
204 /**
205 * @brief Marks the vertex as included in the aggregation.
206 */
207 void resetExcludedBorder();
208
209 /**
210 * @brief Reset all flags.
211 */
212 void reset();
213
214 };
215
216 template<typename G, std::size_t i>
217 class PropertyGraphVertexPropertyMap
218 : public RAPropertyMapHelper<typename std::bitset<VertexProperties::SIZE>::reference,
219 PropertyGraphVertexPropertyMap<G,i> >
220 {
221 public:
222
223 typedef ReadWritePropertyMapTag Category;
224
225 enum {
226 /** @brief the index to access in the bitset. */
227 index = i
228 };
229
230 /**
231 * @brief The type of the graph with internal properties.
232 */
233 typedef G Graph;
234
235 /**
236 * @brief The type of the bitset.
237 */
238 typedef std::bitset<VertexProperties::SIZE> BitSet;
239
240 /**
241 * @brief The reference type.
242 */
243 typedef typename BitSet::reference Reference;
244
245 /**
246 * @brief The value type.
247 */
248 typedef bool ValueType;
249
250 /**
251 * @brief The vertex descriptor.
252 */
253 typedef typename G::VertexDescriptor Vertex;
254
255 /**
256 * @brief Constructor.
257 * @param g The graph whose properties we access.
258 */
259 PropertyGraphVertexPropertyMap(G& g)
260 : graph_(&g)
261 {}
262
263 /**
264 * @brief Default constructor.
265 */
266 PropertyGraphVertexPropertyMap()
267 : graph_(0)
268 {}
269
270
271 /**
272 * @brief Get the properties associated to a vertex.
273 * @param vertex The vertex whose Properties we want.
274 */
275 Reference operator[](const Vertex& vertex) const
276 {
277 return graph_->getVertexProperties(vertex)[index];
278 }
279 private:
280 Graph* graph_;
281 };
282
283 } // end namespace Amg
284
285 template<typename G, typename EP, typename VM, typename EM>
286 struct PropertyMapTypeSelector<Amg::VertexVisitedTag,Amg::PropertiesGraph<G,Amg::VertexProperties,EP,VM,EM> >
287 {
288 typedef Amg::PropertyGraphVertexPropertyMap<Amg::PropertiesGraph<G,Amg::VertexProperties,EP,VM,EM>, Amg::VertexProperties::VISITED> Type;
289 };
290
291 template<typename G, typename EP, typename VM, typename EM>
292 typename PropertyMapTypeSelector<Amg::VertexVisitedTag,Amg::PropertiesGraph<G,Amg::VertexProperties,EP,VM,EM> >::Type
293 get([[maybe_unused]] const Amg::VertexVisitedTag& tag, Amg::PropertiesGraph<G,Amg::VertexProperties,EP,VM,EM>& graph)
294 {
295 return Amg::PropertyGraphVertexPropertyMap<Amg::PropertiesGraph<G,Amg::VertexProperties,EP,VM,EM>, Amg::VertexProperties::VISITED>(graph);
296 }
297
298 namespace Amg
299 {
300 inline std::ostream& operator<<(std::ostream& os, const EdgeProperties& props)
301 {
302 return os << props.flags_;
303 }
304
305 inline EdgeProperties::EdgeProperties()
306 : flags_()
307 {}
308
309 inline std::bitset<EdgeProperties::SIZE>::reference
310 EdgeProperties::operator[](std::size_t v)
311 {
312 return flags_[v];
313 }
314
315 inline bool EdgeProperties::operator[](std::size_t i) const
316 {
317 return flags_[i];
318 }
319
320 inline void EdgeProperties::reset()
321 {
322 flags_.reset();
323 }
324
325 inline void EdgeProperties::setInfluences()
326 {
327 // Set the INFLUENCE bit
328 //flags_ |= (1<<INFLUENCE);
329 flags_.set(INFLUENCE);
330 }
331
332 inline bool EdgeProperties::influences() const
333 {
334 // Test the INFLUENCE bit
335 return flags_.test(INFLUENCE);
336 }
337
338 inline void EdgeProperties::setDepends()
339 {
340 // Set the first bit.
341 //flags_ |= (1<<DEPEND);
342 flags_.set(DEPEND);
343 }
344
345 inline void EdgeProperties::resetDepends()
346 {
347 // reset the first bit.
348 //flags_ &= ~(1<<DEPEND);
349 flags_.reset(DEPEND);
350 }
351
352 inline bool EdgeProperties::depends() const
353 {
354 // Return the first bit.
355 return flags_.test(DEPEND);
356 }
357
358 inline void EdgeProperties::resetInfluences()
359 {
360 // reset the second bit.
361 flags_ &= ~(1<<INFLUENCE);
362 }
363
364 inline bool EdgeProperties::isOneWay() const
365 {
366 // Test whether only the first bit is set
367 //return isStrong() && !isTwoWay();
368 return ((flags_) & std::bitset<SIZE>((1<<INFLUENCE)|(1<<DEPEND)))==(1<<DEPEND);
369 }
370
371 inline bool EdgeProperties::isTwoWay() const
372 {
373 // Test whether the first and second bit is set
374 return ((flags_) & std::bitset<SIZE>((1<<INFLUENCE)|(1<<DEPEND)))==((1<<INFLUENCE)|(1<<DEPEND));
375 }
376
377 inline bool EdgeProperties::isStrong() const
378 {
379 // Test whether the first or second bit is set
380 return ((flags_) & std::bitset<SIZE>((1<<INFLUENCE)|(1<<DEPEND))).to_ulong();
381 }
382
383
384 inline std::ostream& operator<<(std::ostream& os, const VertexProperties& props)
385 {
386 return os << props.flags_;
387 }
388
389 inline VertexProperties::VertexProperties()
390 : flags_()
391 {}
392
393
394 inline std::bitset<VertexProperties::SIZE>::reference
395 VertexProperties::operator[](std::size_t v)
396 {
397 return flags_[v];
398 }
399
400 inline bool VertexProperties::operator[](std::size_t v) const
401 {
402 return flags_[v];
403 }
404
405 inline void VertexProperties::setIsolated()
406 {
407 flags_.set(ISOLATED);
408 }
409
410 inline bool VertexProperties::isolated() const
411 {
412 return flags_.test(ISOLATED);
413 }
414
415 inline void VertexProperties::resetIsolated()
416 {
417 flags_.reset(ISOLATED);
418 }
419
420 inline void VertexProperties::setVisited()
421 {
422 flags_.set(VISITED);
423 }
424
425 inline bool VertexProperties::visited() const
426 {
427 return flags_.test(VISITED);
428 }
429
430 inline void VertexProperties::resetVisited()
431 {
432 flags_.reset(VISITED);
433 }
434
435 inline void VertexProperties::setFront()
436 {
437 flags_.set(FRONT);
438 }
439
440 inline bool VertexProperties::front() const
441 {
442 return flags_.test(FRONT);
443 }
444
445 inline void VertexProperties::resetFront()
446 {
447 flags_.reset(FRONT);
448 }
449
450 inline void VertexProperties::setExcludedBorder()
451 {
452 flags_.set(BORDER);
453 }
454
455 inline bool VertexProperties::excludedBorder() const
456 {
457 return flags_.test(BORDER);
458 }
459
460 inline void VertexProperties::resetExcludedBorder()
461 {
462 flags_.reset(BORDER);
463 }
464
465 inline void VertexProperties::reset()
466 {
467 flags_.reset();
468 }
469
470 /** @} */
471 }
472 }
473 #endif