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 deleteDependency (const T &key, const T &value)
 Delete a dependency (only the edge) between items in the resolver. More...
 
void deleteDependenciesOfKey (const T &key)
 Removes dependencies of the given key. 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 283 of file DependencyResolver.h.

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

284 {
285  if (std::find(_independent_items.begin(), _independent_items.end(), value) ==
286  _independent_items.end())
287  _independent_items.push_back(value);
288  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), value) == _ordering_vector.end())
289  _ordering_vector.push_back(value);
290 }
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 294 of file DependencyResolver.h.

Referenced by Syntax::clearTaskDependencies().

295 {
296  _depends.clear();
297  _independent_items.clear();
298  _ordering_vector.clear();
299  _ordered_items.clear();
300  _ordered_items_vector.clear();
301  _values_vector.clear();
302 }
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.

◆ deleteDependenciesOfKey()

template<typename T>
void DependencyResolver< T >::deleteDependenciesOfKey ( const T &  key)

Removes dependencies of the given key.

Does not fixup the graph or change indpendent items.

Definition at line 275 of file DependencyResolver.h.

Referenced by Syntax::deleteTaskDependencies().

276 {
277  auto eq_range = _depends.equal_range(key);
278  _depends.erase(eq_range.first, eq_range.second);
279 }
std::multimap< T, T > _depends
This is our main data structure a multimap that contains any number of dependencies in a key = value ...

◆ deleteDependency()

template<typename T>
void DependencyResolver< T >::deleteDependency ( const T &  key,
const T &  value 
)

Delete a dependency (only the edge) between items in the resolver.

If either item is orphaned due to the deletion of the edge, the items are inserted into the independent items set so they will still come out when running the resolver.

Definition at line 241 of file DependencyResolver.h.

242 {
243  std::pair<const int, int> k = std::make_pair(key, value);
244  _unique_deps.erase(k);
245 
246  // We don't want to remove every entry in the multimap with this key. We need to find the exact
247  // entry (e.g. the key/value pair).
248  auto eq_range = _depends.equal_range(key);
249  for (auto it = eq_range.first; it != eq_range.second; ++it)
250  if (*it == k)
251  {
252  _depends.erase(it);
253  break;
254  }
255 
256  // Now that we've removed the dependency, we need to see if either one of the items is orphaned.
257  // If it is, we'll need to add those items to the independent set.
258  if (_depends.find(key) == _depends.end())
259  addItem(key);
260 
261  bool found = false;
262  for (auto pair_it : _depends)
263  if (pair_it.second == value)
264  {
265  found = true;
266  break;
267  }
268 
269  if (!found)
270  addItem(value);
271 }
std::multimap< T, T > _depends
This is our main data structure a multimap that contains any number of dependencies in a key = value ...
std::set< std::pair< T, T > > _unique_deps
Used to avoid duplicate tracking of identical insertions of dependencies.
void addItem(const T &value)
Add an independent item to the set.

◆ 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 465 of file DependencyResolver.h.

466 {
467  if (key == value)
468  return true;
469 
470  // recursively call dependsOn on all the things that key depends on
471  auto ret = _depends.equal_range(key);
472  for (auto it = ret.first; it != ret.second; ++it)
473  if (dependsOn(it->second, value))
474  return true;
475 
476  // No dependencies were found,
477  // or the key is not in the tree (so it has no dependencies).
478  // In this latter case, the only way that key depends on value is if key == value,
479  // but we've already checked that
480  return false;
481 }
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 485 of file DependencyResolver.h.

486 {
487  for (auto key : keys)
488  if (dependsOn(key, value))
489  return true;
490  return false;
491 }
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 451 of file DependencyResolver.h.

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

452 {
453  _ordered_items_vector.clear();
454 
456 
457  for (auto subset : _ordered_items)
458  std::copy(subset.begin(), subset.end(), std::back_inserter(_ordered_items_vector));
459 
460  return _ordered_items_vector;
461 }
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 306 of file DependencyResolver.h.

Referenced by Syntax::getSortedTaskSet().

307 {
308  // Use the original ordering for ordering subvectors
310 
316  typedef std::multimap<T, T, DependencyResolverComparator<T>> dep_multimap;
317  dep_multimap depends(_depends.begin(), _depends.end(), comp);
318 
319  // Build up a set of all keys in depends that have nothing depending on them,
320  // and put it in the orphans set.
321  std::set<T> nodepends;
322 
323  std::set<T> all;
324  std::set<T> dependees;
325  for (auto & entry : depends)
326  {
327  dependees.insert(entry.second);
328  all.insert(entry.first);
329  all.insert(entry.second);
330  }
331 
332  std::set<T> orphans;
333  std::set_difference(all.begin(),
334  all.end(),
335  dependees.begin(),
336  dependees.end(),
337  std::inserter(orphans, orphans.end()));
338 
339  // Remove items from _independent_items if they actually appear in depends
340  for (auto siter = _independent_items.begin(); siter != _independent_items.end();)
341  {
342  T key = *siter;
343  bool founditem = false;
344  for (auto i2 : depends)
345  {
346  if (i2.first == key || i2.second == key)
347  {
348  founditem = true;
349  break;
350  }
351  }
352  if (founditem)
353  siter = _independent_items.erase(siter); // post increment to maintain a valid iterator
354  else
355  ++siter;
356  }
357 
358  /* Clear the ordered items vector */
359  _ordered_items.clear();
360 
361  // Put the independent items into the first set in _ordered_items
362  std::vector<T> next_set(_independent_items.begin(), _independent_items.end());
363 
364  /* Topological Sort */
365  while (!depends.empty())
366  {
367  /* Work with sets since set_difference doesn't always work properly with multi_map due
368  * to duplicate keys
369  */
370  std::set<T, DependencyResolverComparator<T>> keys(
371  typename DependencyResolver<T>::template key_iterator<dep_multimap>(depends.begin()),
372  typename DependencyResolver<T>::template key_iterator<dep_multimap>(depends.end()),
373  comp);
374 
375  std::set<T, DependencyResolverComparator<T>> values(
376  typename DependencyResolver<T>::template value_iterator<dep_multimap>(depends.begin()),
377  typename DependencyResolver<T>::template value_iterator<dep_multimap>(depends.end()),
378  comp);
379 
380  std::vector<T> current_set(next_set);
381  next_set.clear();
382 
383  /* This set difference creates a set of items that have no dependencies in the depend map*/
384  std::set<T, DependencyResolverComparator<T>> difference(comp);
385 
386  std::set_difference(values.begin(),
387  values.end(),
388  keys.begin(),
389  keys.end(),
390  std::inserter(difference, difference.end()),
391  comp);
392 
393  /* Now remove items from the temporary map that have been "resolved" */
394  if (!difference.empty())
395  {
396  for (auto iter = depends.begin(); iter != depends.end();)
397  {
398  if (difference.find(iter->second) != difference.end())
399  {
400  T key = iter->first;
401  depends.erase(iter++); // post increment to maintain a valid iterator
402 
403  // If the item is at the end of a dependency chain (by being an orphan) AND
404  // is not still in the depends map because it still has another unresolved link
405  // insert it into the next_set
406  if (orphans.find(key) != orphans.end() && depends.find(key) == depends.end())
407  next_set.push_back(key);
408  }
409  else
410  ++iter;
411  }
412  /* Add the current set of resolved items to the ordered vector */
413  current_set.insert(current_set.end(), difference.begin(), difference.end());
414  _ordered_items.push_back(current_set);
415  }
416  else
417  {
418 
419  /* If the last set difference was empty but there are still items that haven't come out then
420  * there is a cyclic dependency somewhere in the map.
421  */
422  if (!depends.empty())
423  {
424  std::ostringstream oss;
425  oss << "Cyclic dependency detected in the Dependency Resolver. Remaining items are:\n";
426  for (auto j : depends)
427  oss << j.first << " -> " << j.second << "\n";
428  // Return a multimap without a weird comparator, to avoid
429  // dangling reference problems and for backwards compatibility
430  std::multimap<T, T> cyclic_deps(depends.begin(), depends.end());
431  throw CyclicDependencyException<T>(oss.str(), cyclic_deps);
432  }
433  }
434  }
435 
436  if (next_set.empty())
437  {
438  if (!_independent_items.empty() || !depends.empty())
439  mooseError("DependencyResolver error: next_set shouldn't be empty!");
440  }
441  else
442  {
443  _ordered_items.push_back(next_set);
444  }
445 
446  return _ordered_items;
447 }
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 495 of file DependencyResolver.h.

496 {
497  _values_vector.clear();
498 
499  auto ret = _depends.equal_range(key);
500 
501  for (auto it = ret.first; it != ret.second; ++it)
502  _values_vector.push_back(it->second);
503 
504  return _values_vector;
505 }
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 220 of file DependencyResolver.h.

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

221 {
222  auto k = std::make_pair(key, value);
223  if (_unique_deps.count(k) > 0)
224  return;
225  _unique_deps.insert(k);
226 
227  if (dependsOn(value, key))
228  {
230  "DependencyResolver: attempt to insert dependency will result in cyclic graph", _depends);
231  }
232  _depends.insert(k);
233  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), key) == _ordering_vector.end())
234  _ordering_vector.push_back(key);
235  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), value) == _ordering_vector.end())
236  _ordering_vector.push_back(value);
237 }
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 509 of file DependencyResolver.h.

510 {
511  if (_ordered_items_vector.empty())
512  getSortedValues();
513 
514  auto a_it = std::find(_ordered_items_vector.begin(), _ordered_items_vector.end(), a);
515  auto b_it = std::find(_ordered_items_vector.begin(), _ordered_items_vector.end(), b);
516 
524  if (b_it == _ordered_items_vector.end())
525  return false;
526  if (a_it == _ordered_items_vector.end())
527  return true;
528  else
534  return a_it < b_it;
535 }
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 137 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 146 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 154 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 157 of file DependencyResolver.h.

◆ _ordering_vector

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

Definition at line 151 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 143 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 160 of file DependencyResolver.h.


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