www.mooseframework.org
DependencyResolver.h
Go to the documentation of this file.
1 //* This file is part of the MOOSE framework
2 //* https://www.mooseframework.org
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 // C++ includes
17 #include <map>
18 #include <set>
19 #include <string>
20 #include <vector>
21 #include <algorithm>
22 #include <sstream>
23 #include <exception>
24 
25 template <typename T>
27 {
28 public:
29  DependencyResolverComparator(const std::vector<T> & original_order)
30  : _original_order(original_order)
31  {
32  }
33 
34  bool operator()(const T & a, const T & b) const
35  {
36  auto a_it = std::find(_original_order.begin(), _original_order.end(), a);
37  auto b_it = std::find(_original_order.begin(), _original_order.end(), b);
38 
39  mooseAssert(a_it != _original_order.end(), "Bad DependencyResolverComparator request");
40  mooseAssert(b_it != _original_order.end(), "Bad DependencyResolverComparator request");
41 
45  return a_it < b_it;
46  }
47 
48 private:
49  const std::vector<T> & _original_order;
50 };
51 
52 template <typename T>
54 {
55 public:
57 
59 
64  void insertDependency(const T & key, const T & value);
65 
71  void deleteDependency(const T & key, const T & value);
72 
76  void deleteDependenciesOfKey(const T & key);
77 
81  void addItem(const T & value);
82 
86  void clear();
87 
92  const std::vector<std::vector<T>> & getSortedValuesSets();
93 
101  const std::vector<T> & getSortedValues();
102 
114  bool dependsOn(const T & key, const T & value);
115 
119  bool dependsOn(const std::vector<T> & keys, const T & value);
120 
124  const std::vector<T> & getValues(const T & key);
125 
126  bool operator()(const T & a, const T & b);
127 
128 private:
132  template <typename map_type>
134 
135  template <typename map_type>
136  class value_iterator;
137 
139  std::multimap<T, T> _depends;
140 
142  std::set<std::pair<T, T>> _unique_deps;
143 
145  std::vector<T> _independent_items;
146 
147  // A vector retaining the order in which items were added to the
148  // resolver, to disambiguate ordering of items with no
149  // mutual interdependencies
150  std::vector<T> _ordering_vector;
151 
153  std::vector<std::vector<T>> _ordered_items;
154 
156  std::vector<T> _ordered_items_vector;
157 
159  std::vector<T> _values_vector;
160 };
161 
162 template <typename T>
163 class CyclicDependencyException : public std::runtime_error
164 {
165 public:
166  CyclicDependencyException(const std::string & error,
167  const std::multimap<T, T> & cyclic_items) throw()
168  : runtime_error(error), _cyclic_items(cyclic_items)
169  {
170  }
171 
173  : runtime_error(e), _cyclic_items(e._cyclic_items)
174  {
175  }
176 
178 
179  const std::multimap<T, T> & getCyclicDependencies() const { return _cyclic_items; }
180 
181 private:
182  std::multimap<T, T> _cyclic_items;
183 };
184 
188 template <typename T>
189 template <typename map_type>
190 class DependencyResolver<T>::key_iterator : public map_type::iterator
191 {
192 public:
193  typedef typename map_type::iterator map_iterator;
194  typedef typename map_iterator::value_type::first_type key_type;
195 
196  key_iterator(const map_iterator & other) : map_type::iterator(other){};
197 
199 };
200 
201 template <typename T>
202 template <typename map_type>
203 class DependencyResolver<T>::value_iterator : public map_type::iterator
204 {
205 public:
206  typedef typename map_type::iterator map_iterator;
207  typedef typename map_iterator::value_type::second_type value_type;
208 
209  value_iterator(const map_iterator & other) : map_type::iterator(other){};
210 
212 };
213 
217 template <typename T>
218 void
219 DependencyResolver<T>::insertDependency(const T & key, const T & value)
220 {
221  auto k = std::make_pair(key, value);
222  if (_unique_deps.count(k) > 0)
223  return;
224  _unique_deps.insert(k);
225 
226  if (dependsOn(value, key))
227  {
229  "DependencyResolver: attempt to insert dependency will result in cyclic graph", _depends);
230  }
231  _depends.insert(k);
232  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), key) == _ordering_vector.end())
233  _ordering_vector.push_back(key);
234  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), value) == _ordering_vector.end())
235  _ordering_vector.push_back(value);
236 }
237 
238 template <typename T>
239 void
240 DependencyResolver<T>::deleteDependency(const T & key, const T & value)
241 {
242  std::pair<const int, int> k = std::make_pair(key, value);
243  _unique_deps.erase(k);
244 
245  // We don't want to remove every entry in the multimap with this key. We need to find the exact
246  // entry (e.g. the key/value pair).
247  auto eq_range = _depends.equal_range(key);
248  for (auto it = eq_range.first; it != eq_range.second; ++it)
249  if (*it == k)
250  {
251  _depends.erase(it);
252  break;
253  }
254 
255  // Now that we've removed the dependency, we need to see if either one of the items is orphaned.
256  // If it is, we'll need to add those items to the independent set.
257  if (_depends.find(key) == _depends.end())
258  addItem(key);
259 
260  bool found = false;
261  for (auto pair_it : _depends)
262  if (pair_it.second == value)
263  {
264  found = true;
265  break;
266  }
267 
268  if (!found)
269  addItem(value);
270 }
271 
272 template <typename T>
273 void
275 {
276  auto eq_range = _depends.equal_range(key);
277  _depends.erase(eq_range.first, eq_range.second);
278 }
279 
280 template <typename T>
281 void
283 {
284  if (std::find(_independent_items.begin(), _independent_items.end(), value) ==
285  _independent_items.end())
286  _independent_items.push_back(value);
287  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), value) == _ordering_vector.end())
288  _ordering_vector.push_back(value);
289 }
290 
291 template <typename T>
292 void
294 {
295  _depends.clear();
296  _independent_items.clear();
297  _ordering_vector.clear();
298  _ordered_items.clear();
299  _ordered_items_vector.clear();
300  _values_vector.clear();
301 }
302 
303 template <typename T>
304 const std::vector<std::vector<T>> &
306 {
307  // Use the original ordering for ordering subvectors
308  DependencyResolverComparator<T> comp(_ordering_vector);
309 
315  typedef std::multimap<T, T, DependencyResolverComparator<T>> dep_multimap;
316  dep_multimap depends(_depends.begin(), _depends.end(), comp);
317 
318  // Build up a set of all keys in depends that have nothing depending on them,
319  // and put it in the orphans set.
320  std::set<T> nodepends;
321 
322  std::set<T> all;
323  std::set<T> dependees;
324  for (auto & entry : depends)
325  {
326  dependees.insert(entry.second);
327  all.insert(entry.first);
328  all.insert(entry.second);
329  }
330 
331  std::set<T> orphans;
332  std::set_difference(all.begin(),
333  all.end(),
334  dependees.begin(),
335  dependees.end(),
336  std::inserter(orphans, orphans.end()));
337 
338  // Remove items from _independent_items if they actually appear in depends
339  for (auto siter = _independent_items.begin(); siter != _independent_items.end();)
340  {
341  T key = *siter;
342  bool founditem = false;
343  for (auto i2 : depends)
344  {
345  if (i2.first == key || i2.second == key)
346  {
347  founditem = true;
348  break;
349  }
350  }
351  if (founditem)
352  siter = _independent_items.erase(siter); // post increment to maintain a valid iterator
353  else
354  ++siter;
355  }
356 
357  /* Clear the ordered items vector */
358  _ordered_items.clear();
359 
360  // Put the independent items into the first set in _ordered_items
361  std::vector<T> next_set(_independent_items.begin(), _independent_items.end());
362 
363  /* Topological Sort */
364  while (!depends.empty())
365  {
366  /* Work with sets since set_difference doesn't always work properly with multi_map due
367  * to duplicate keys
368  */
369  std::set<T, DependencyResolverComparator<T>> keys(
370  typename DependencyResolver<T>::template key_iterator<dep_multimap>(depends.begin()),
371  typename DependencyResolver<T>::template key_iterator<dep_multimap>(depends.end()),
372  comp);
373 
374  std::set<T, DependencyResolverComparator<T>> values(
375  typename DependencyResolver<T>::template value_iterator<dep_multimap>(depends.begin()),
376  typename DependencyResolver<T>::template value_iterator<dep_multimap>(depends.end()),
377  comp);
378 
379  std::vector<T> current_set(next_set);
380  next_set.clear();
381 
382  /* This set difference creates a set of items that have no dependencies in the depend map*/
383  std::set<T, DependencyResolverComparator<T>> difference(comp);
384 
385  std::set_difference(values.begin(),
386  values.end(),
387  keys.begin(),
388  keys.end(),
389  std::inserter(difference, difference.end()),
390  comp);
391 
392  /* Now remove items from the temporary map that have been "resolved" */
393  if (!difference.empty())
394  {
395  for (auto iter = depends.begin(); iter != depends.end();)
396  {
397  if (difference.find(iter->second) != difference.end())
398  {
399  T key = iter->first;
400  depends.erase(iter++); // post increment to maintain a valid iterator
401 
402  // If the item is at the end of a dependency chain (by being an orphan) AND
403  // is not still in the depends map because it still has another unresolved link
404  // insert it into the next_set
405  if (orphans.find(key) != orphans.end() && depends.find(key) == depends.end())
406  next_set.push_back(key);
407  }
408  else
409  ++iter;
410  }
411  /* Add the current set of resolved items to the ordered vector */
412  current_set.insert(current_set.end(), difference.begin(), difference.end());
413  _ordered_items.push_back(current_set);
414  }
415  else
416  {
417 
418  /* If the last set difference was empty but there are still items that haven't come out then
419  * there is a cyclic dependency somewhere in the map.
420  */
421  if (!depends.empty())
422  {
423  std::ostringstream oss;
424  oss << "Cyclic dependency detected in the Dependency Resolver. Remaining items are:\n";
425  for (auto j : depends)
426  oss << j.first << " -> " << j.second << "\n";
427  // Return a multimap without a weird comparator, to avoid
428  // dangling reference problems and for backwards compatibility
429  std::multimap<T, T> cyclic_deps(depends.begin(), depends.end());
430  throw CyclicDependencyException<T>(oss.str(), cyclic_deps);
431  }
432  }
433  }
434 
435  if (next_set.empty())
436  {
437  if (!_independent_items.empty() || !depends.empty())
438  mooseError("DependencyResolver error: next_set shouldn't be empty!");
439  }
440  else
441  {
442  _ordered_items.push_back(next_set);
443  }
444 
445  return _ordered_items;
446 }
447 
448 template <typename T>
449 const std::vector<T> &
451 {
452  _ordered_items_vector.clear();
453 
454  getSortedValuesSets();
455 
456  for (auto subset : _ordered_items)
457  std::copy(subset.begin(), subset.end(), std::back_inserter(_ordered_items_vector));
458 
459  return _ordered_items_vector;
460 }
461 
462 template <typename T>
463 bool
464 DependencyResolver<T>::dependsOn(const T & key, const T & value)
465 {
466  if (key == value)
467  return true;
468 
469  // recursively call dependsOn on all the things that key depends on
470  auto ret = _depends.equal_range(key);
471  for (auto it = ret.first; it != ret.second; ++it)
472  if (dependsOn(it->second, value))
473  return true;
474 
475  // No dependencies were found,
476  // or the key is not in the tree (so it has no dependencies).
477  // In this latter case, the only way that key depends on value is if key == value,
478  // but we've already checked that
479  return false;
480 }
481 
482 template <typename T>
483 bool
484 DependencyResolver<T>::dependsOn(const std::vector<T> & keys, const T & value)
485 {
486  for (auto key : keys)
487  if (dependsOn(key, value))
488  return true;
489  return false;
490 }
491 
492 template <typename T>
493 const std::vector<T> &
495 {
496  _values_vector.clear();
497 
498  auto ret = _depends.equal_range(key);
499 
500  for (auto it = ret.first; it != ret.second; ++it)
501  _values_vector.push_back(it->second);
502 
503  return _values_vector;
504 }
505 
506 template <typename T>
507 bool
508 DependencyResolver<T>::operator()(const T & a, const T & b)
509 {
510  if (_ordered_items_vector.empty())
511  getSortedValues();
512 
513  auto a_it = std::find(_ordered_items_vector.begin(), _ordered_items_vector.end(), a);
514  auto b_it = std::find(_ordered_items_vector.begin(), _ordered_items_vector.end(), b);
515 
523  if (b_it == _ordered_items_vector.end())
524  return false;
525  if (a_it == _ordered_items_vector.end())
526  return true;
527  else
533  return a_it < b_it;
534 }
535 
DependencyResolverComparator(const std::vector< T > &original_order)
const std::vector< T > & _original_order
void deleteDependenciesOfKey(const T &key)
Removes dependencies of the given key.
std::vector< T > _ordering_vector
const std::vector< std::vector< T > > & getSortedValuesSets()
Returns a vector of sets that represent dependency resolved values.
std::multimap< T, T > _depends
This is our main data structure a multimap that contains any number of dependencies in a key = value ...
void mooseError(Args &&... args)
Emit an error message with the given stringified, concatenated args and terminate the application...
Definition: MooseError.h:207
map_iterator::value_type::second_type value_type
void clear()
Clear Items from the resolver.
bool dependsOn(const T &key, const T &value)
Return true if key depends on value.
std::vector< T > _independent_items
Extra items that need to come out in the sorted list but contain no dependencies. ...
CyclicDependencyException(const CyclicDependencyException &e)
bool operator()(const T &a, const T &b) const
auto operator*(const T1 &a, const RankFourTensorTempl< T2 > &b) -> typename std::enable_if< ScalarTraits< T1 >::value, RankFourTensorTempl< decltype(T1() *T2())>>::type
std::vector< T > _ordered_items_vector
The sorted vector (if requested)
map_iterator::value_type::first_type key_type
value_iterator(const map_iterator &other)
const std::vector< T > & getSortedValues()
This function also returns dependency resolved values but with a simpler single vector interface...
void deleteDependency(const T &key, const T &value)
Delete a dependency (only the edge) between items in the resolver.
bool operator()(const T &a, const T &b)
Helper classes for returning only keys or values in an iterator format.
std::vector< std::vector< T > > _ordered_items
The sorted vector of sets.
const std::multimap< T, T > & getCyclicDependencies() const
CyclicDependencyException(const std::string &error, const std::multimap< T, T > &cyclic_items)
std::multimap< T, T > _cyclic_items
std::set< std::pair< T, T > > _unique_deps
Used to avoid duplicate tracking of identical insertions of dependencies.
key_iterator(const map_iterator &other)
const std::vector< T > & getValues(const T &key)
Returns a vector of values that the given key depends on.
void addItem(const T &value)
Add an independent item to the set.
std::vector< T > _values_vector
List of values that a given key depends upon.
void insertDependency(const T &key, const T &value)
Insert a dependency pair - the first value or the "key" depends on the second value or the "value"...