www.mooseframework.org
Classes | Public Member Functions | Private Attributes | List of all members
DependencyResolver< T > Class Template Reference

#include <DependencyResolver.h>

Classes

class  key_iterator
 Helper classes for returning only keys or values in an iterator format. More...
 
class  value_iterator
 

Public Member Functions

 DependencyResolver ()
 
 ~DependencyResolver ()
 
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". More...
 
void addItem (const T &value)
 Add an independent item to the set. More...
 
void clear ()
 Clear Items from the resolver. More...
 
const std::vector< std::vector< T > > & getSortedValuesSets ()
 Returns a vector of sets that represent dependency resolved values. More...
 
const std::vector< T > & getSortedValues ()
 This function also returns dependency resolved values but with a simpler single vector interface. More...
 
bool dependsOn (const T &key, const T &value)
 Return true if key depends on value. More...
 
bool dependsOn (const std::vector< T > &keys, const T &value)
 Return true if any of elements of keys depends on value. More...
 
const std::vector< T > & getValues (const T &key)
 Returns a vector of values that the given key depends on. More...
 
bool operator() (const T &a, const T &b)
 

Private Attributes

std::multimap< T, T > _depends
 This is our main data structure a multimap that contains any number of dependencies in a key = value format. More...
 
std::set< std::pair< T, T > > _unique_deps
 Used to avoid duplicate tracking of identical insertions of dependencies. More...
 
std::vector< T > _independent_items
 Extra items that need to come out in the sorted list but contain no dependencies. More...
 
std::vector< T > _ordering_vector
 
std::vector< std::vector< T > > _ordered_items
 The sorted vector of sets. More...
 
std::vector< T > _ordered_items_vector
 The sorted vector (if requested) More...
 
std::vector< T > _values_vector
 List of values that a given key depends upon. More...
 

Detailed Description

template<typename T>
class DependencyResolver< T >

Definition at line 54 of file DependencyResolver.h.

Constructor & Destructor Documentation

◆ DependencyResolver()

template<typename T>
DependencyResolver< T >::DependencyResolver ( )
inline

Definition at line 57 of file DependencyResolver.h.

57 {}

◆ ~DependencyResolver()

template<typename T>
DependencyResolver< T >::~DependencyResolver ( )
inline

Definition at line 59 of file DependencyResolver.h.

59 {}

Member Function Documentation

◆ addItem()

template<typename T>
void DependencyResolver< T >::addItem ( const T &  value)

Add an independent item to the set.

Definition at line 229 of file DependencyResolver.h.

Referenced by FEProblemBase::executeControls(), MooseApp::executeMeshGenerators(), MooseApp::executeMeshModifiers(), and Syntax::registerTaskName().

230 {
231  if (std::find(_independent_items.begin(), _independent_items.end(), value) ==
232  _independent_items.end())
233  _independent_items.push_back(value);
234  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), value) == _ordering_vector.end())
235  _ordering_vector.push_back(value);
236 }
std::vector< T > _ordering_vector
std::vector< T > _independent_items
Extra items that need to come out in the sorted list but contain no dependencies. ...

◆ clear()

template<typename T >
void DependencyResolver< T >::clear ( )

Clear Items from the resolver.

Definition at line 240 of file DependencyResolver.h.

Referenced by Syntax::clearTaskDependencies().

241 {
242  _depends.clear();
243  _independent_items.clear();
244  _ordering_vector.clear();
245  _ordered_items.clear();
246  _ordered_items_vector.clear();
247  _values_vector.clear();
248 }
std::vector< T > _ordering_vector
std::multimap< T, T > _depends
This is our main data structure a multimap that contains any number of dependencies in a key = value ...
std::vector< T > _independent_items
Extra items that need to come out in the sorted list but contain no dependencies. ...
std::vector< T > _ordered_items_vector
The sorted vector (if requested)
std::vector< std::vector< T > > _ordered_items
The sorted vector of sets.
std::vector< T > _values_vector
List of values that a given key depends upon.

◆ dependsOn() [1/2]

template<typename T>
bool DependencyResolver< T >::dependsOn ( const T &  key,
const T &  value 
)

Return true if key depends on value.

That is, return true, if a chain of calls of the form insertDependency(key, v0) insertDependency(v0, v1) insertDependency(v1, v2) ... insertDependency(vN, value) has been performed. dependsOn(x, x) always returns true

Definition at line 412 of file DependencyResolver.h.

413 {
414  if (key == value)
415  return true;
416 
417  // recursively call dependsOn on all the things that key depends on
418  std::pair<typename std::multimap<T, T>::iterator, typename std::multimap<T, T>::iterator> ret;
419  ret = _depends.equal_range(key);
420  for (typename std::multimap<T, T>::iterator it = ret.first; it != ret.second; ++it)
421  if (dependsOn(it->second, value))
422  return true;
423 
424  // No dependencies were found,
425  // or the key is not in the tree (so it has no dependencies).
426  // In this latter case, the only way that key depends on value is if key == value,
427  // but we've already checked that
428  return false;
429 }
std::multimap< T, T > _depends
This is our main data structure a multimap that contains any number of dependencies in a key = value ...
bool dependsOn(const T &key, const T &value)
Return true if key depends on value.

◆ dependsOn() [2/2]

template<typename T>
bool DependencyResolver< T >::dependsOn ( const std::vector< T > &  keys,
const T &  value 
)

Return true if any of elements of keys depends on value.

Definition at line 433 of file DependencyResolver.h.

434 {
435  for (auto key : keys)
436  if (dependsOn(key, value))
437  return true;
438  return false;
439 }
bool dependsOn(const T &key, const T &value)
Return true if key depends on value.

◆ getSortedValues()

template<typename T >
const std::vector< T > & DependencyResolver< T >::getSortedValues ( )

This function also returns dependency resolved values but with a simpler single vector interface.

Some information may be lost as values at the same level that don't depend on one and other can't be represented in a single vector. This isn't a problem in practice though.

Definition at line 398 of file DependencyResolver.h.

Referenced by FEProblemBase::executeControls(), MooseApp::executeMeshGenerators(), MooseApp::executeMeshModifiers(), and Syntax::getSortedTask().

399 {
400  _ordered_items_vector.clear();
401 
403 
404  for (auto subset : _ordered_items)
405  std::copy(subset.begin(), subset.end(), std::back_inserter(_ordered_items_vector));
406 
407  return _ordered_items_vector;
408 }
const std::vector< std::vector< T > > & getSortedValuesSets()
Returns a vector of sets that represent dependency resolved values.
std::vector< T > _ordered_items_vector
The sorted vector (if requested)
std::vector< std::vector< T > > _ordered_items
The sorted vector of sets.

◆ getSortedValuesSets()

template<typename T >
const std::vector< std::vector< T > > & DependencyResolver< T >::getSortedValuesSets ( )

Returns a vector of sets that represent dependency resolved values.

Items in the same subvector have no dependence upon one and other.

Make a copy of the map to work on since: 1) we will remove values from the map 2) We need the copy to be sorted in an unambiguous order.

Definition at line 252 of file DependencyResolver.h.

Referenced by Syntax::getSortedTaskSet().

253 {
254  // Use the original ordering for ordering subvectors
256 
262  typedef std::multimap<T, T, DependencyResolverComparator<T>> dep_multimap;
263  dep_multimap depends(_depends.begin(), _depends.end(), comp);
264 
265  // Build up a set of all keys in depends that have nothing depending on them,
266  // and put it in the orphans set.
267  std::set<T> nodepends;
268 
269  std::set<T> all;
270  std::set<T> dependees;
271  for (auto & entry : depends)
272  {
273  dependees.insert(entry.second);
274  all.insert(entry.first);
275  all.insert(entry.second);
276  }
277 
278  std::set<T> orphans;
279  std::set_difference(all.begin(),
280  all.end(),
281  dependees.begin(),
282  dependees.end(),
283  std::inserter(orphans, orphans.end()));
284 
285  // Remove items from _independent_items if they actually appear in depends
286  for (auto siter = _independent_items.begin(); siter != _independent_items.end();)
287  {
288  T key = *siter;
289  bool founditem = false;
290  for (auto i2 : depends)
291  {
292  if (i2.first == key || i2.second == key)
293  {
294  founditem = true;
295  break;
296  }
297  }
298  if (founditem)
299  siter = _independent_items.erase(siter); // post increment to maintain a valid iterator
300  else
301  ++siter;
302  }
303 
304  /* Clear the ordered items vector */
305  _ordered_items.clear();
306 
307  // Put the independent items into the first set in _ordered_items
308  std::vector<T> next_set(_independent_items.begin(), _independent_items.end());
309 
310  /* Topological Sort */
311  while (!depends.empty())
312  {
313  /* Work with sets since set_difference doesn't always work properly with multi_map due
314  * to duplicate keys
315  */
316  std::set<T, DependencyResolverComparator<T>> keys(
317  typename DependencyResolver<T>::template key_iterator<dep_multimap>(depends.begin()),
318  typename DependencyResolver<T>::template key_iterator<dep_multimap>(depends.end()),
319  comp);
320 
321  std::set<T, DependencyResolverComparator<T>> values(
322  typename DependencyResolver<T>::template value_iterator<dep_multimap>(depends.begin()),
323  typename DependencyResolver<T>::template value_iterator<dep_multimap>(depends.end()),
324  comp);
325 
326  std::vector<T> current_set(next_set);
327  next_set.clear();
328 
329  /* This set difference creates a set of items that have no dependencies in the depend map*/
330  std::set<T, DependencyResolverComparator<T>> difference(comp);
331 
332  std::set_difference(values.begin(),
333  values.end(),
334  keys.begin(),
335  keys.end(),
336  std::inserter(difference, difference.end()),
337  comp);
338 
339  /* Now remove items from the temporary map that have been "resolved" */
340  if (!difference.empty())
341  {
342  for (auto iter = depends.begin(); iter != depends.end();)
343  {
344  if (difference.find(iter->second) != difference.end())
345  {
346  T key = iter->first;
347  depends.erase(iter++); // post increment to maintain a valid iterator
348 
349  // If the item is at the end of a dependency chain (by being an orphan) AND
350  // is not still in the depends map because it still has another unresolved link
351  // insert it into the next_set
352  if (orphans.find(key) != orphans.end() && depends.find(key) == depends.end())
353  next_set.push_back(key);
354  }
355  else
356  ++iter;
357  }
358  /* Add the current set of resolved items to the ordered vector */
359  current_set.insert(current_set.end(), difference.begin(), difference.end());
360  _ordered_items.push_back(current_set);
361  }
362  else
363  {
364 
365  /* If the last set difference was empty but there are still items that haven't come out then
366  * there is
367  * a cyclic dependency somewhere in the map
368  */
369  if (!depends.empty())
370  {
371  std::ostringstream oss;
372  oss << "Cyclic dependency detected in the Dependency Resolver. Remaining items are:\n";
373  for (auto j : depends)
374  oss << j.first << " -> " << j.second << "\n";
375  // Return a multimap without a weird comparator, to avoid
376  // dangling reference problems and for backwards compatibility
377  std::multimap<T, T> cyclic_deps(depends.begin(), depends.end());
378  throw CyclicDependencyException<T>(oss.str(), cyclic_deps);
379  }
380  }
381  }
382 
383  if (next_set.empty())
384  {
385  if (!_independent_items.empty() || !depends.empty())
386  mooseError("DependencyResolver error: next_set shouldn't be empty!");
387  }
388  else
389  {
390  _ordered_items.push_back(next_set);
391  }
392 
393  return _ordered_items;
394 }
std::vector< T > _ordering_vector
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:208
std::vector< T > _independent_items
Extra items that need to come out in the sorted list but contain no dependencies. ...
std::vector< std::vector< T > > _ordered_items
The sorted vector of sets.

◆ getValues()

template<typename T>
const std::vector< T > & DependencyResolver< T >::getValues ( const T &  key)

Returns a vector of values that the given key depends on.

Definition at line 443 of file DependencyResolver.h.

444 {
445  _values_vector.clear();
446 
447  std::pair<typename std::multimap<T, T>::iterator, typename std::multimap<T, T>::iterator> ret;
448  ret = _depends.equal_range(key);
449 
450  for (typename std::multimap<T, T>::iterator it = ret.first; it != ret.second; ++it)
451  _values_vector.push_back(it->second);
452 
453  return _values_vector;
454 }
std::multimap< T, T > _depends
This is our main data structure a multimap that contains any number of dependencies in a key = value ...
std::vector< T > _values_vector
List of values that a given key depends upon.

◆ insertDependency()

template<typename T>
void DependencyResolver< T >::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".

DependencyResolver class definitions.

Definition at line 208 of file DependencyResolver.h.

Referenced by Syntax::addDependency(), FEProblemBase::executeControls(), MooseApp::executeMeshGenerators(), MooseApp::executeMeshModifiers(), and DependencyResolverInterface::sort().

209 {
210  auto k = std::make_pair(key, value);
211  if (_unique_deps.count(k) > 0)
212  return;
213  _unique_deps.insert(k);
214 
215  if (dependsOn(value, key))
216  {
218  "DependencyResolver: attempt to insert dependency will result in cyclic graph", _depends);
219  }
220  _depends.insert(std::make_pair(key, value));
221  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), key) == _ordering_vector.end())
222  _ordering_vector.push_back(key);
223  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), value) == _ordering_vector.end())
224  _ordering_vector.push_back(value);
225 }
std::vector< T > _ordering_vector
std::multimap< T, T > _depends
This is our main data structure a multimap that contains any number of dependencies in a key = value ...
bool dependsOn(const T &key, const T &value)
Return true if key depends on value.
std::set< std::pair< T, T > > _unique_deps
Used to avoid duplicate tracking of identical insertions of dependencies.

◆ operator()()

template<typename T>
bool DependencyResolver< T >::operator() ( const T &  a,
const T &  b 
)

It's possible that a and/or b are not in the resolver in which case we want those values to come out first. However, we need to make sure that we maintain strict weak ordering so we'll compare b_it first, which will return false for a_it < b_it and b_it < a_it when both values are not in the ordered_items vector.

Compare the iterators. Users sometime fail to state all their items' dependencies, but do introduce dependant items only after the items they depended on; this preserves that sorting.

Definition at line 458 of file DependencyResolver.h.

459 {
460  if (_ordered_items_vector.empty())
461  getSortedValues();
462 
463  typename std::vector<T>::const_iterator a_it =
464  std::find(_ordered_items_vector.begin(), _ordered_items_vector.end(), a);
465  typename std::vector<T>::const_iterator b_it =
466  std::find(_ordered_items_vector.begin(), _ordered_items_vector.end(), b);
467 
475  if (b_it == _ordered_items_vector.end())
476  return false;
477  if (a_it == _ordered_items_vector.end())
478  return true;
479  else
485  return a_it < b_it;
486 }
std::vector< T > _ordered_items_vector
The sorted vector (if requested)
const std::vector< T > & getSortedValues()
This function also returns dependency resolved values but with a simpler single vector interface...

Member Data Documentation

◆ _depends

template<typename T>
std::multimap<T, T> DependencyResolver< T >::_depends
private

This is our main data structure a multimap that contains any number of dependencies in a key = value format.

Definition at line 125 of file DependencyResolver.h.

◆ _independent_items

template<typename T>
std::vector<T> DependencyResolver< T >::_independent_items
private

Extra items that need to come out in the sorted list but contain no dependencies.

Definition at line 134 of file DependencyResolver.h.

◆ _ordered_items

template<typename T>
std::vector<std::vector<T> > DependencyResolver< T >::_ordered_items
private

The sorted vector of sets.

Definition at line 142 of file DependencyResolver.h.

◆ _ordered_items_vector

template<typename T>
std::vector<T> DependencyResolver< T >::_ordered_items_vector
private

The sorted vector (if requested)

Definition at line 145 of file DependencyResolver.h.

◆ _ordering_vector

template<typename T>
std::vector<T> DependencyResolver< T >::_ordering_vector
private

Definition at line 139 of file DependencyResolver.h.

◆ _unique_deps

template<typename T>
std::set<std::pair<T, T> > DependencyResolver< T >::_unique_deps
private

Used to avoid duplicate tracking of identical insertions of dependencies.

Definition at line 131 of file DependencyResolver.h.

◆ _values_vector

template<typename T>
std::vector<T> DependencyResolver< T >::_values_vector
private

List of values that a given key depends upon.

Definition at line 148 of file DependencyResolver.h.


The documentation for this class was generated from the following file: