www.mooseframework.org
DependencyResolver.h
Go to the documentation of this file.
1 /****************************************************************/
2 /* DO NOT MODIFY THIS HEADER */
3 /* MOOSE - Multiphysics Object Oriented Simulation Environment */
4 /* */
5 /* (c) 2010 Battelle Energy Alliance, LLC */
6 /* ALL RIGHTS RESERVED */
7 /* */
8 /* Prepared by Battelle Energy Alliance, LLC */
9 /* Under Contract No. DE-AC07-05ID14517 */
10 /* With the U. S. Department of Energy */
11 /* */
12 /* See COPYRIGHT for full restrictions */
13 /****************************************************************/
14 
15 #ifndef DEPENDENCYRESOLVER_H
16 #define DEPENDENCYRESOLVER_H
17 
18 // MOOSE includes
19 #include "Moose.h"
20 #include "MooseError.h"
21 
22 // C++ includes
23 #include <map>
24 #include <set>
25 #include <string>
26 #include <vector>
27 #include <algorithm>
28 #include <sstream>
29 #include <exception>
30 
31 template <typename T>
33 {
34 public:
35  DependencyResolverComparator(const std::vector<T> & original_order)
36  : _original_order(original_order)
37  {
38  }
39 
40  bool operator()(const T & a, const T & b) const
41  {
42  auto a_it = std::find(_original_order.begin(), _original_order.end(), a);
43  auto b_it = std::find(_original_order.begin(), _original_order.end(), b);
44 
45  mooseAssert(a_it != _original_order.end(), "Bad DependencyResolverComparator request");
46  mooseAssert(b_it != _original_order.end(), "Bad DependencyResolverComparator request");
47 
51  return a_it < b_it;
52  }
53 
54 private:
55  const std::vector<T> & _original_order;
56 };
57 
58 template <typename T>
60 {
61 public:
63 
65 
70  void insertDependency(const T & key, const T & value);
71 
75  void addItem(const T & value);
76 
81  const std::vector<std::vector<T>> & getSortedValuesSets();
82 
90  const std::vector<T> & getSortedValues();
91 
103  bool dependsOn(const T & key, const T & value);
104 
108  bool dependsOn(const std::vector<T> & keys, const T & value);
109 
110  bool operator()(const T & a, const T & b);
111 
112 private:
116  template <typename map_type>
118 
119  template <typename map_type>
120  class value_iterator;
121 
123  std::multimap<T, T> _depends;
124 
126  std::vector<T> _independent_items;
127 
128  // A vector retaining the order in which items were added to the
129  // resolver, to disambiguate ordering of items with no
130  // mutual interdependencies
131  std::vector<T> _ordering_vector;
132 
134  std::vector<std::vector<T>> _ordered_items;
135 
137  std::vector<T> _ordered_items_vector;
138 };
139 
140 template <typename T>
141 class CyclicDependencyException : public std::runtime_error
142 {
143 public:
144  CyclicDependencyException(const std::string & error,
145  const std::multimap<T, T> & cyclic_items) throw()
146  : runtime_error(error), _cyclic_items(cyclic_items)
147  {
148  }
149 
151  : runtime_error(e), _cyclic_items(e._cyclic_items)
152  {
153  }
154 
156 
157  const std::multimap<T, T> & getCyclicDependencies() const { return _cyclic_items; }
158 
159 private:
160  std::multimap<T, T> _cyclic_items;
161 };
162 
166 template <typename T>
167 template <typename map_type>
168 class DependencyResolver<T>::key_iterator : public map_type::iterator
169 {
170 public:
171  typedef typename map_type::iterator map_iterator;
172  typedef typename map_iterator::value_type::first_type key_type;
173 
174  key_iterator(const map_iterator & other) : map_type::iterator(other){};
175 
176  key_type & operator*() { return map_type::iterator::operator*().first; }
177 };
178 
179 template <typename T>
180 template <typename map_type>
181 class DependencyResolver<T>::value_iterator : public map_type::iterator
182 {
183 public:
184  typedef typename map_type::iterator map_iterator;
185  typedef typename map_iterator::value_type::second_type value_type;
186 
187  value_iterator(const map_iterator & other) : map_type::iterator(other){};
188 
189  value_type & operator*() { return map_type::iterator::operator*().second; }
190 };
191 
195 template <typename T>
196 void
197 DependencyResolver<T>::insertDependency(const T & key, const T & value)
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 }
210 
211 template <typename T>
212 void
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 }
219 
220 template <typename T>
221 const std::vector<std::vector<T>> &
223 {
224  // Use the original ordering for ordering subvectors
225  DependencyResolverComparator<T> comp(_ordering_vector);
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(
289  comp);
290 
291  std::set<T, DependencyResolverComparator<T>> values(
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 }
365 
366 template <typename T>
367 const std::vector<T> &
369 {
370  _ordered_items_vector.clear();
371 
372  getSortedValuesSets();
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 }
379 
380 template <typename T>
381 bool
382 DependencyResolver<T>::dependsOn(const T & key, const T & value)
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 }
400 
401 template <typename T>
402 bool
403 DependencyResolver<T>::dependsOn(const std::vector<T> & keys, const T & value)
404 {
405  for (auto key : keys)
406  if (dependsOn(key, value))
407  return true;
408  return false;
409 }
410 
411 template <typename T>
412 bool
413 DependencyResolver<T>::operator()(const T & a, const T & b)
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 }
442 
443 #endif // DEPENDENCYRESOLVER_H
DependencyResolverComparator(const std::vector< T > &original_order)
const std::vector< T > & _original_order
std::vector< T > _ordering_vector
const std::vector< std::vector< T > > & getSortedValuesSets()
Returns a vector of sets that represent dependency resolved values.
bool operator()(const T &a, const T &b) const
std::multimap< T, T > _depends
This is our main data structure a multimap that contains any number of dependencies in a key = value ...
map_iterator::value_type::second_type value_type
void mooseError(Args &&...args)
Emit an error message with the given stringified, concatenated args and terminate the application...
Definition: MooseError.h:182
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)
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...
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.
CyclicDependencyException(const std::string &error, const std::multimap< T, T > &cyclic_items)
RankFourTensor operator*(Real a, const RankFourTensor &b)
std::multimap< T, T > _cyclic_items
key_iterator(const map_iterator &other)
const std::multimap< T, T > & getCyclicDependencies() const
void addItem(const T &value)
Add an independent item to the set.
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"...