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...
 
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...
 
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::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...
 

Detailed Description

template<typename T>
class DependencyResolver< T >

Definition at line 59 of file DependencyResolver.h.

Constructor & Destructor Documentation

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

Definition at line 62 of file DependencyResolver.h.

62 {}
template<typename T>
DependencyResolver< T >::~DependencyResolver ( )
inline

Definition at line 64 of file DependencyResolver.h.

64 {}

Member Function Documentation

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

Add an independent item to the set.

Definition at line 213 of file DependencyResolver.h.

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

214 {
215  _independent_items.push_back(value);
216  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), value) == _ordering_vector.end())
217  _ordering_vector.push_back(value);
218 }
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. ...
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 382 of file DependencyResolver.h.

383 {
384  if (key == value)
385  return true;
386 
387  // recursively call dependsOn on all the things that key depends on
388  std::pair<typename std::multimap<T, T>::iterator, typename std::multimap<T, T>::iterator> ret;
389  ret = _depends.equal_range(key);
390  for (typename std::multimap<T, T>::iterator it = ret.first; it != ret.second; ++it)
391  if (dependsOn(it->second, value))
392  return true;
393 
394  // No dependencies were found,
395  // or the key is not in the tree (so it has no dependencies).
396  // In this latter case, the only way that key depends on value is if key == value,
397  // but we've already checked that
398  return false;
399 }
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.
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 403 of file DependencyResolver.h.

404 {
405  for (auto key : keys)
406  if (dependsOn(key, value))
407  return true;
408  return false;
409 }
bool dependsOn(const T &key, const T &value)
Return true if key depends on value.
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 368 of file DependencyResolver.h.

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

369 {
370  _ordered_items_vector.clear();
371 
373 
374  for (auto subset : _ordered_items)
375  std::copy(subset.begin(), subset.end(), std::back_inserter(_ordered_items_vector));
376 
377  return _ordered_items_vector;
378 }
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.
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 222 of file DependencyResolver.h.

Referenced by Syntax::getSortedTaskSet().

223 {
224  // Use the original ordering for ordering subvectors
226 
232  typedef std::multimap<T, T, DependencyResolverComparator<T>> dep_multimap;
233  dep_multimap depends(_depends.begin(), _depends.end(), comp);
234 
235  // Build up a set of all keys in depends that have nothing depending on them,
236  // and put it in the nodepends set. These are the leaves of the dependency tree.
237  std::set<T> nodepends;
238  for (auto i : depends)
239  {
240  T key = i.first;
241 
242  bool founditem = false;
243  for (auto i2 : depends)
244  {
245  if (i2.second == key)
246  {
247  founditem = true;
248  break;
249  }
250  }
251  if (!founditem)
252  nodepends.insert(key);
253  }
254 
255  // Remove items from _independent_items if they actually appear in depends
256  for (auto siter = _independent_items.begin(); siter != _independent_items.end();)
257  {
258  T key = *siter;
259  bool founditem = false;
260  for (auto i2 : depends)
261  {
262  if (i2.first == key || i2.second == key)
263  {
264  founditem = true;
265  break;
266  }
267  }
268  if (founditem)
269  siter = _independent_items.erase(siter); // post increment to maintain a valid iterator
270  else
271  ++siter;
272  }
273 
274  /* Clear the ordered items vector */
275  _ordered_items.clear();
276 
277  // Put the independent items into the first set in _ordered_items
278  std::vector<T> next_set(_independent_items);
279 
280  /* Topological Sort */
281  while (!depends.empty())
282  {
283  /* Work with sets since set_difference doesn't always work properly with multi_map due
284  * to duplicate keys
285  */
286  std::set<T, DependencyResolverComparator<T>> keys(
287  typename DependencyResolver<T>::template key_iterator<dep_multimap>(depends.begin()),
288  typename DependencyResolver<T>::template key_iterator<dep_multimap>(depends.end()),
289  comp);
290 
291  std::set<T, DependencyResolverComparator<T>> values(
292  typename DependencyResolver<T>::template value_iterator<dep_multimap>(depends.begin()),
293  typename DependencyResolver<T>::template value_iterator<dep_multimap>(depends.end()),
294  comp);
295 
296  std::vector<T> current_set(next_set);
297  next_set.clear();
298 
299  /* This set difference creates a set of items that have no dependencies in the depend map*/
300  std::set<T, DependencyResolverComparator<T>> difference(comp);
301 
302  std::set_difference(values.begin(),
303  values.end(),
304  keys.begin(),
305  keys.end(),
306  std::inserter(difference, difference.end()),
307  comp);
308 
309  /* Now remove items from the temporary map that have been "resolved" */
310  if (!difference.empty())
311  {
312  for (auto iter = depends.begin(); iter != depends.end();)
313  {
314  if (difference.find(iter->second) != difference.end())
315  {
316  T key = iter->first;
317  depends.erase(iter++); // post increment to maintain a valid iterator
318 
319  // If the item is at the end of a dependency chain (by being in nodepends) AND
320  // is not still in the depends map because it still has another unresolved link
321  // insert it into the next_set
322  if (nodepends.find(key) != nodepends.end() && depends.find(key) == depends.end())
323  next_set.push_back(key);
324  }
325  else
326  ++iter;
327  }
328  /* Add the current set of resolved items to the ordered vector */
329  current_set.insert(current_set.end(), difference.begin(), difference.end());
330  _ordered_items.push_back(current_set);
331  }
332  else
333  {
334 
335  /* If the last set difference was empty but there are still items that haven't come out then
336  * there is
337  * a cyclic dependency somewhere in the map
338  */
339  if (!depends.empty())
340  {
341  std::ostringstream oss;
342  oss << "Cyclic dependency detected in the Dependency Resolver. Remaining items are:\n";
343  for (auto j : depends)
344  oss << j.first << " -> " << j.second << "\n";
345  // Return a multimap without a weird comparator, to avoid
346  // dangling reference problems and for backwards compatibility
347  std::multimap<T, T> cyclic_deps(depends.begin(), depends.end());
348  throw CyclicDependencyException<T>(oss.str(), cyclic_deps);
349  }
350  }
351  }
352 
353  if (next_set.empty())
354  {
355  if (!_independent_items.empty() || !depends.empty())
356  mooseError("DependencyResolver error: next_set shouldn't be empty!");
357  }
358  else
359  {
360  _ordered_items.push_back(next_set);
361  }
362 
363  return _ordered_items;
364 }
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:182
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.
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 197 of file DependencyResolver.h.

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

198 {
199  if (dependsOn(value, key))
200  {
202  "DependencyResolver: attempt to insert dependency will result in cyclic graph", _depends);
203  }
204  _depends.insert(std::make_pair(key, value));
205  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), key) == _ordering_vector.end())
206  _ordering_vector.push_back(key);
207  if (std::find(_ordering_vector.begin(), _ordering_vector.end(), value) == _ordering_vector.end())
208  _ordering_vector.push_back(value);
209 }
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.
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 413 of file DependencyResolver.h.

414 {
415  if (_ordered_items_vector.empty())
416  getSortedValues();
417 
418  typename std::vector<T>::const_iterator a_it =
419  std::find(_ordered_items_vector.begin(), _ordered_items_vector.end(), a);
420  typename std::vector<T>::const_iterator b_it =
421  std::find(_ordered_items_vector.begin(), _ordered_items_vector.end(), b);
422 
430  if (b_it == _ordered_items_vector.end())
431  return false;
432  if (a_it == _ordered_items_vector.end())
433  return true;
434  else
440  return a_it < b_it;
441 }
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

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

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

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

The sorted vector of sets.

Definition at line 134 of file DependencyResolver.h.

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

The sorted vector (if requested)

Definition at line 137 of file DependencyResolver.h.

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

Definition at line 131 of file DependencyResolver.h.


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