Line data Source code
1 : //* This file is part of the MOOSE framework
2 : //* https://mooseframework.inl.gov
3 : //*
4 : //* All rights reserved, see COPYRIGHT for full restrictions
5 : //* https://github.com/idaholab/moose/blob/master/COPYRIGHT
6 : //*
7 : //* Licensed under LGPL 2.1, please see LICENSE for details
8 : //* https://www.gnu.org/licenses/lgpl-2.1.html
9 :
10 : #pragma once
11 :
12 : // MOOSE includes
13 : #include "Moose.h"
14 : #include "MooseError.h"
15 :
16 : #include "libmesh/utility.h"
17 : #include "libmesh/simple_range.h"
18 :
19 : // C++ includes
20 : #include <map>
21 : #include <string>
22 : #include <vector>
23 : #include <list>
24 : #include <algorithm>
25 : #include <sstream>
26 : #include <exception>
27 :
28 : template <class T, class Compare>
29 : class CyclicDependencyException;
30 :
31 : /**
32 : * Class that represents the dependecy as a graph
33 : */
34 : template <class T, class Compare = std::less<T>>
35 : class DependencyResolver
36 : {
37 : public:
38 350157 : DependencyResolver() = default;
39 344252 : ~DependencyResolver() = default;
40 :
41 : /**
42 : * Add a node 'a' to the graph
43 : */
44 : void addNode(const T & a);
45 :
46 : /**
47 : * Add an edge between nodes 'a' and 'b'
48 : */
49 : void addEdge(const T & a, const T & b);
50 :
51 : /**
52 : * Remove an edge between nodes 'a' and 'b'
53 : */
54 : void removeEdge(const T & a, const T & b);
55 :
56 : /**
57 : * Remove edges drawn from 'a'
58 : */
59 : void removeEdgesInvolving(const T & a);
60 :
61 : /**
62 : * Insert a dependency pair - the first value or the "key" depends on the second value or the
63 : * "value"
64 : */
65 10909383 : void insertDependency(const T & key, const T & value) { addEdge(value, key); }
66 :
67 : /**
68 : * Delete a dependency (only the edge) between items in the resolver
69 : */
70 2 : void deleteDependency(const T & key, const T & value) { removeEdge(value, key); }
71 :
72 : /**
73 : * Removes dependencies of the given key
74 : */
75 1 : void deleteDependenciesOfKey(const T & key) { removeEdgesInvolving(key); }
76 :
77 : /**
78 : * Add an independent item to the set
79 : */
80 8948328 : void addItem(const T & value) { addNode(value); }
81 :
82 : /**
83 : * Clear Items from the resolver
84 : */
85 : void clear();
86 :
87 : /**
88 : * Do depth-first search from root nodes to obtain order in which graph nodes should be
89 : * "executed".
90 : */
91 : const std::vector<T> & dfs();
92 :
93 : /**
94 : * Returns a vector of sets that represent dependency resolved values. Items in the same
95 : * subvector have no dependence upon one and other.
96 : */
97 : [[nodiscard]] const std::vector<std::vector<T>> & getSortedValuesSets();
98 :
99 : /**
100 : * This function also returns dependency resolved values but with a simpler single vector
101 : * interface.
102 : * Some information may be lost as values at the same level that don't depend on one and other
103 : * can't
104 : * be represented in a single vector. This isn't a problem in practice though.
105 : */
106 69272 : [[nodiscard]] const std::vector<T> & getSortedValues() { return dfs(); }
107 :
108 : /**
109 : * Return true if key depends on value.
110 : * That is, return true, if a chain of calls of the form
111 : * insertDependency(key, v0)
112 : * insertDependency(v0, v1)
113 : * insertDependency(v1, v2)
114 : * ...
115 : * insertDependency(vN, value)
116 : * has been performed.
117 : * dependsOn(x, x) always returns true
118 : */
119 : [[nodiscard]] bool dependsOn(const T & key, const T & value);
120 :
121 : /**
122 : * Return true if any of elements of keys depends on value
123 : */
124 : [[nodiscard]] bool dependsOn(const std::vector<T> & keys, const T & value);
125 :
126 : /**
127 : * Returns a list of all values that a given key depends on
128 : */
129 : [[nodiscard]] std::list<T> getAncestors(const T & key);
130 :
131 : /**
132 : * Returns the number of unique items stored in the dependency resolver. lindsayad comment: does
133 : * it really return the number of *unique* items?
134 : */
135 21837 : std::size_t size() const { return _sorted_vector.size(); }
136 :
137 : protected:
138 : /**
139 : * depth first search from a root node, searching for a specific item
140 : * @param root The node we start from
141 : * @param item The node we are searching for
142 : */
143 : [[nodiscard]] bool dependsOnFromNode(const T & root, const T & item);
144 :
145 : /**
146 : * Perform a depth-first-search from the specified \p root node. Populates _visited and
147 : * _sorted_vector data members
148 : * @return whether a cyclic graph was detected while performing the depth-first-search from the \p
149 : * root node
150 : */
151 : bool dfsFromNode(const T & root);
152 :
153 : /// adjacency lists (from leaves to roots)
154 : std::map<T, std::list<T>, Compare> _adj;
155 : /// adjacency lists (from roots to leaves)
156 : std::map<T, std::list<T>, Compare> _inv_adj;
157 : /// vector of visited nodes
158 : std::map<T, bool, Compare> _visited;
159 : /// number of visited nodes; used to avoid iterating through _visited
160 : std::size_t _num_visited = 0;
161 : /// recursive stack
162 : std::map<T, bool, Compare> _rec_stack;
163 : /// "sorted" vector of nodes
164 : std::vector<T> _sorted_vector;
165 : /// The sorted vector of sets
166 : std::vector<std::vector<T>> _ordered_items;
167 : /// Container for keeping track of the insertion order. We will use this to determine iteration
168 : /// order because it is essential that iteration order be sync'd across multiple
169 : /// processes. Iterating over maps with pointer keys, for example, can be out of sync on multiple
170 : /// processes. If dependency resolver memory usage shows up in profiling, we can consider making
171 : /// this a container of reference wrappers
172 : std::vector<T> _insertion_order;
173 : /// Data member for storing nodes that appear circularly in the graph
174 : T _circular_node = T{};
175 :
176 : friend class CyclicDependencyException<T, Compare>;
177 : };
178 :
179 : template <class T, class Compare>
180 : void
181 31732404 : DependencyResolver<T, Compare>::addNode(const T & a)
182 : {
183 : #ifndef NDEBUG
184 : bool new_adj_insertion = false, new_inv_insertion = false;
185 : #endif
186 31732404 : if (_adj.find(a) == _adj.end())
187 : {
188 : #ifndef NDEBUG
189 : new_adj_insertion = true;
190 : #endif
191 9664629 : _adj[a] = {};
192 9664629 : _insertion_order.push_back(a);
193 : }
194 :
195 31732404 : if (_inv_adj.find(a) == _inv_adj.end())
196 : {
197 : #ifndef NDEBUG
198 : new_inv_insertion = true;
199 : #endif
200 9664629 : _inv_adj[a] = {};
201 : }
202 : mooseAssert(new_adj_insertion == new_inv_insertion,
203 : "We should have symmetric behavior between adjacent and inverse-adjacent "
204 : "insertion/non-insertion.");
205 31732404 : }
206 :
207 : template <class T, class Compare>
208 : void
209 10994757 : DependencyResolver<T, Compare>::addEdge(const T & a, const T & b)
210 : {
211 10994757 : addNode(a);
212 10994757 : addNode(b);
213 :
214 10994757 : _adj[a].push_back(b);
215 10994757 : _inv_adj[b].push_back(a);
216 10994757 : }
217 :
218 : template <class T, class Compare>
219 : void
220 4 : DependencyResolver<T, Compare>::removeEdge(const T & a, const T & b)
221 : {
222 16 : auto remove_item = [](auto & list, const auto & item)
223 : {
224 8 : auto it = std::find(list.begin(), list.end(), item);
225 : mooseAssert(it != list.end(), "We should have this item");
226 8 : list.erase(it);
227 : };
228 4 : remove_item(_adj[a], b);
229 4 : remove_item(_inv_adj[b], a);
230 4 : }
231 :
232 : template <class T, class Compare>
233 : void
234 1 : DependencyResolver<T, Compare>::removeEdgesInvolving(const T & a)
235 : {
236 1 : const auto & inv_adjs = _inv_adj[a];
237 2 : for (const auto & inv_adj : inv_adjs)
238 : {
239 1 : auto & adj = _adj[inv_adj];
240 1 : auto it = std::find(adj.begin(), adj.end(), a);
241 : mooseAssert(it != adj.end(), "Should have reciprocity");
242 1 : adj.erase(it);
243 : }
244 :
245 1 : _inv_adj[a].clear();
246 1 : }
247 :
248 : template <class T, class Compare>
249 : void
250 0 : DependencyResolver<T, Compare>::clear()
251 : {
252 0 : _adj.clear();
253 0 : _inv_adj.clear();
254 0 : _insertion_order.clear();
255 0 : }
256 :
257 : template <class T, class Compare>
258 : const std::vector<T> &
259 349328 : DependencyResolver<T, Compare>::dfs()
260 : {
261 349328 : _sorted_vector.clear();
262 349328 : _visited.clear();
263 349328 : _num_visited = 0;
264 349328 : _rec_stack.clear();
265 349328 : _circular_node = T{};
266 :
267 9900958 : for (auto & n : _adj)
268 : {
269 9551630 : _visited[n.first] = false;
270 9551630 : _rec_stack[n.first] = false;
271 : }
272 :
273 349328 : bool is_cyclic = false;
274 :
275 : // If there are no adjacencies, then all nodes are both roots and leaves
276 349328 : bool roots_found = _adj.empty();
277 9900829 : for (auto & n : _insertion_order)
278 9551506 : if (_adj[n].size() == 0)
279 : {
280 1324177 : roots_found = true;
281 1324177 : is_cyclic = dfsFromNode(n);
282 1324177 : if (is_cyclic)
283 5 : break;
284 : }
285 :
286 349328 : if (roots_found)
287 : {
288 : // At this point, if we have any sub-graphs that are cyclic that do not have any
289 : // roots _and_ we have found one more or more separate sub-graphs with a root,
290 : // we will have never visited the aforementioned cyclic sub-graphs. Therefore,
291 : // at this point if we haven't visited something it's a part of a cyclic sub-graph
292 349323 : if (!is_cyclic && _num_visited != _insertion_order.size())
293 : {
294 2 : for (const auto & [n, visited] : _visited)
295 2 : if (!visited && (is_cyclic = dfsFromNode(n)))
296 1 : break;
297 :
298 : mooseAssert(is_cyclic, "Should have found a cyclic dependency");
299 : }
300 : }
301 : // Didn't find any roots
302 : else
303 : {
304 5 : is_cyclic = true;
305 : // Create a cycle graph
306 5 : for (auto & n : _insertion_order)
307 5 : if (dfsFromNode(n))
308 5 : break;
309 : }
310 :
311 349328 : if (is_cyclic)
312 11 : throw CyclicDependencyException<T, Compare>("cyclic graph detected", *this);
313 :
314 : mooseAssert(_sorted_vector.size() == _insertion_order.size(), "Unexpected sorted size");
315 : mooseAssert(_num_visited == _insertion_order.size(), "Did not visit all nodes");
316 :
317 349317 : return _sorted_vector;
318 : }
319 :
320 : template <class T, class Compare>
321 : const std::vector<std::vector<T>> &
322 45807 : DependencyResolver<T, Compare>::getSortedValuesSets()
323 : {
324 45807 : _ordered_items.clear();
325 :
326 45807 : const auto & flat_sorted = dfs();
327 :
328 45803 : std::vector<T> current_group;
329 147490 : for (const auto & object : flat_sorted)
330 : {
331 101687 : if (current_group.empty())
332 : {
333 45803 : current_group.push_back(object);
334 45803 : continue;
335 : }
336 :
337 55884 : const auto & prev_adj_list = _adj[current_group.back()];
338 : const bool depends_on_prev =
339 55884 : std::find(prev_adj_list.begin(), prev_adj_list.end(), object) != prev_adj_list.end();
340 :
341 55884 : if (depends_on_prev)
342 : {
343 74208 : _ordered_items.push_back({object});
344 48359 : auto & finalized_group = _ordered_items.back();
345 : // Swap the current-group into the back of our ordered items container, and now our newest
346 : // object becomes the current group
347 48359 : finalized_group.swap(current_group);
348 : }
349 : else
350 7525 : current_group.push_back(object);
351 : }
352 :
353 45803 : if (!current_group.empty())
354 45803 : _ordered_items.push_back(std::move(current_group));
355 :
356 45803 : return _ordered_items;
357 71652 : }
358 :
359 : template <class T, class Compare>
360 : bool
361 91 : DependencyResolver<T, Compare>::dependsOn(const T & key, const T & value)
362 : {
363 91 : if (_adj.find(value) == _adj.end())
364 1 : return false;
365 :
366 560 : for (auto & n : _adj)
367 470 : _visited[n.first] = false;
368 :
369 90 : return dependsOnFromNode(key, value);
370 : }
371 :
372 : template <class T, class Compare>
373 : bool
374 : DependencyResolver<T, Compare>::dependsOn(const std::vector<T> & keys, const T & value)
375 : {
376 : if (_adj.find(value) == _adj.end())
377 : return false;
378 :
379 : for (auto & n : _adj)
380 : _visited[n.first] = false;
381 :
382 : for (const auto & key : keys)
383 : if (dependsOnFromNode(key, value))
384 : return true;
385 :
386 : return false;
387 : }
388 :
389 : template <class T, class Compare>
390 : std::list<T>
391 21838 : DependencyResolver<T, Compare>::getAncestors(const T & key)
392 : {
393 21838 : std::vector<T> ret_vec;
394 : // Our sorted vector is our work vector but we also return references to it. So we have to make
395 : // sure at the end that we restore the original data we had in it
396 21838 : ret_vec.swap(_sorted_vector);
397 :
398 67931 : for (auto & n : _adj)
399 46093 : _visited[n.first] = false;
400 :
401 21838 : dfsFromNode(key);
402 :
403 21838 : ret_vec.swap(_sorted_vector);
404 : mooseAssert(ret_vec.back() == key, "Our key should be the back of the vector");
405 :
406 43676 : return {ret_vec.begin(), ret_vec.end()};
407 21838 : }
408 :
409 : template <class T, class Compare>
410 : bool
411 252 : DependencyResolver<T, Compare>::dependsOnFromNode(const T & root, const T & item)
412 : {
413 252 : if (root == item)
414 65 : return true;
415 :
416 187 : _visited[root] = true;
417 :
418 187 : auto & my_dependencies = _inv_adj[root];
419 :
420 285 : for (auto & i : my_dependencies)
421 168 : if (!_visited.at(i) && dependsOnFromNode(i, item))
422 70 : return true;
423 :
424 117 : return false;
425 : }
426 :
427 : template <class T, class Compare>
428 : bool
429 9597658 : DependencyResolver<T, Compare>::dfsFromNode(const T & root)
430 : {
431 9597658 : bool cyclic = false;
432 9597658 : auto & visited = libmesh_map_find(_visited, root);
433 9597658 : if (!visited)
434 : {
435 9597658 : ++_num_visited;
436 9597658 : visited = true;
437 : }
438 9597658 : _rec_stack[root] = true;
439 :
440 20477163 : for (auto & i : _inv_adj[root])
441 : {
442 10879553 : if (!_visited.at(i) && dfsFromNode(i))
443 : {
444 37 : cyclic = true;
445 37 : break;
446 : }
447 10879516 : else if (_rec_stack.at(i))
448 : {
449 11 : _circular_node = i;
450 11 : _sorted_vector.push_back(i);
451 11 : cyclic = true;
452 11 : break;
453 : }
454 : }
455 :
456 9597658 : _sorted_vector.push_back(root);
457 9597658 : _rec_stack[root] = false;
458 9597658 : return cyclic;
459 : }
460 :
461 : template <class T, class Compare = std::less<T>>
462 : class CyclicDependencyException : public std::runtime_error
463 : {
464 : public:
465 11 : CyclicDependencyException(const std::string & error,
466 : const DependencyResolver<T, Compare> & graph) throw()
467 11 : : runtime_error(error)
468 : {
469 11 : const auto & sorted = graph._sorted_vector;
470 11 : auto first_occurence = std::find(sorted.begin(), sorted.end(), graph._circular_node);
471 11 : if (first_occurence == sorted.end())
472 0 : mooseError("We must have at least one occurence of the circular node");
473 11 : auto second_occurence = std::find(first_occurence + 1, sorted.end(), graph._circular_node);
474 11 : if (second_occurence == sorted.end())
475 0 : mooseError("We must have two occurences of the circular node");
476 11 : _cyclic_graph = std::vector<T>(first_occurence, second_occurence + 1);
477 11 : }
478 :
479 : CyclicDependencyException(const CyclicDependencyException & e) throw()
480 : : runtime_error(e), _cyclic_graph(e._cyclic_graph)
481 : {
482 : }
483 :
484 3 : ~CyclicDependencyException() throw() {}
485 :
486 9 : const std::vector<T> & getCyclicDependencies() const { return _cyclic_graph; }
487 :
488 : private:
489 : std::vector<T> _cyclic_graph;
490 : };
|
