www.mooseframework.org
Public Member Functions | Protected Member Functions | Protected Attributes | Friends | List of all members
DependencyResolver< T, Compare > Class Template Reference

Class that represents the dependecy as a graph. More...

#include <DependencyResolver.h>

Public Member Functions

 DependencyResolver ()=default
 
 ~DependencyResolver ()=default
 
void addNode (const T &a)
 Add a node 'a' to the graph. More...
 
void addEdge (const T &a, const T &b)
 Add an edge between nodes 'a' and 'b'. More...
 
void removeEdge (const T &a, const T &b)
 Remove an edge between nodes 'a' and 'b'. More...
 
void removeEdgesInvolving (const T &a)
 Remove edges drawn from 'a'. More...
 
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< T > & dfs ()
 Do depth-first search from root nodes to obtain order in which graph nodes should be "executed". 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...
 
std::list< T > getAncestors (const T &key)
 Returns a list of all values that a given key depends on. More...
 
std::size_t size () const
 Returns the number of unique items stored in the dependency resolver. More...
 

Protected Member Functions

bool dependsOnFromNode (const T &root, const T &item)
 depth first search from a root node, searching for a specific item More...
 
bool dfsFromNode (const T &root)
 Perform a depth-first-search from the specified root node. More...
 

Protected Attributes

std::map< T, std::list< T >, Compare > _adj
 adjacency lists (from leaves to roots) More...
 
std::map< T, std::list< T >, Compare > _inv_adj
 adjacency lists (from roots to leaves) More...
 
std::map< T, bool, Compare > _visited
 vector of visited nodes More...
 
std::size_t _num_visited = 0
 number of visited nodes; used to avoid iterating through _visited More...
 
std::map< T, bool, Compare > _rec_stack
 recursive stack More...
 
std::vector< T > _sorted_vector
 "sorted" vector of nodes More...
 
std::vector< std::vector< T > > _ordered_items
 The sorted vector of sets. More...
 
std::vector< T > _insertion_order
 Container for keeping track of the insertion order. More...
 
_circular_node = T{}
 Data member for storing nodes that appear circularly in the graph. More...
 

Friends

class CyclicDependencyException< T, Compare >
 

Detailed Description

template<class T, class Compare = std::less<T>>
class DependencyResolver< T, Compare >

Class that represents the dependecy as a graph.

Definition at line 35 of file DependencyResolver.h.

Constructor & Destructor Documentation

◆ DependencyResolver()

template<class T, class Compare = std::less<T>>
DependencyResolver< T, Compare >::DependencyResolver ( )
default

◆ ~DependencyResolver()

template<class T, class Compare = std::less<T>>
DependencyResolver< T, Compare >::~DependencyResolver ( )
default

Member Function Documentation

◆ addEdge()

template<class T, class Compare >
void DependencyResolver< T, Compare >::addEdge ( const T &  a,
const T &  b 
)

Add an edge between nodes 'a' and 'b'.

Definition at line 209 of file DependencyResolver.h.

Referenced by MeshGeneratorSystem::createAddedMeshGenerators(), MeshGeneratorSystem::createMeshGeneratorOrder(), FEProblemBase::executeControls(), DependencyResolver< std::string >::insertDependency(), and DependencyResolverInterface::sortDFS().

210 {
211  addNode(a);
212  addNode(b);
213 
214  _adj[a].push_back(b);
215  _inv_adj[b].push_back(a);
216 }
std::map< T, std::list< T >, Compare > _inv_adj
adjacency lists (from roots to leaves)
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)
void addNode(const T &a)
Add a node &#39;a&#39; to the graph.

◆ addItem()

template<class T, class Compare = std::less<T>>
void DependencyResolver< T, Compare >::addItem ( const T &  value)
inline

Add an independent item to the set.

Definition at line 80 of file DependencyResolver.h.

Referenced by MeshGeneratorSystem::createAddedMeshGenerators(), MeshGeneratorSystem::createMeshGeneratorOrder(), FEProblemBase::executeControls(), and Syntax::registerTaskName().

80 { addNode(value); }
void addNode(const T &a)
Add a node &#39;a&#39; to the graph.

◆ addNode()

template<class T, class Compare >
void DependencyResolver< T, Compare >::addNode ( const T &  a)

Add a node 'a' to the graph.

Definition at line 181 of file DependencyResolver.h.

Referenced by DependencyResolver< std::string >::addItem(), and DependencyResolverInterface::sortDFS().

182 {
183 #ifndef NDEBUG
184  bool new_adj_insertion = false, new_inv_insertion = false;
185 #endif
186  if (_adj.find(a) == _adj.end())
187  {
188 #ifndef NDEBUG
189  new_adj_insertion = true;
190 #endif
191  _adj[a] = {};
192  _insertion_order.push_back(a);
193  }
194 
195  if (_inv_adj.find(a) == _inv_adj.end())
196  {
197 #ifndef NDEBUG
198  new_inv_insertion = true;
199 #endif
200  _inv_adj[a] = {};
201  }
202  mooseAssert(new_adj_insertion == new_inv_insertion,
203  "We should have symmetric behavior between adjacent and inverse-adjacent "
204  "insertion/non-insertion.");
205 }
std::vector< T > _insertion_order
Container for keeping track of the insertion order.
std::map< T, std::list< T >, Compare > _inv_adj
adjacency lists (from roots to leaves)
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)

◆ clear()

template<class T , class Compare >
void DependencyResolver< T, Compare >::clear ( )

Clear Items from the resolver.

Definition at line 250 of file DependencyResolver.h.

Referenced by Syntax::clearTaskDependencies().

251 {
252  _adj.clear();
253  _inv_adj.clear();
254  _insertion_order.clear();
255 }
std::vector< T > _insertion_order
Container for keeping track of the insertion order.
std::map< T, std::list< T >, Compare > _inv_adj
adjacency lists (from roots to leaves)
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)

◆ deleteDependenciesOfKey()

template<class T, class Compare = std::less<T>>
void DependencyResolver< T, Compare >::deleteDependenciesOfKey ( const T &  key)
inline

Removes dependencies of the given key.

Definition at line 75 of file DependencyResolver.h.

Referenced by Syntax::deleteTaskDependencies().

75 { removeEdgesInvolving(key); }
void removeEdgesInvolving(const T &a)
Remove edges drawn from &#39;a&#39;.

◆ deleteDependency()

template<class T, class Compare = std::less<T>>
void DependencyResolver< T, Compare >::deleteDependency ( const T &  key,
const T &  value 
)
inline

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

Definition at line 70 of file DependencyResolver.h.

70 { removeEdge(value, key); }
void removeEdge(const T &a, const T &b)
Remove an edge between nodes &#39;a&#39; and &#39;b&#39;.

◆ dependsOn() [1/2]

template<class T, class Compare >
bool DependencyResolver< T, Compare >::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 361 of file DependencyResolver.h.

Referenced by MeshGeneratorSystem::createAddedMeshGenerators().

362 {
363  if (_adj.find(value) == _adj.end())
364  return false;
365 
366  for (auto & n : _adj)
367  _visited[n.first] = false;
368 
369  return dependsOnFromNode(key, value);
370 }
bool dependsOnFromNode(const T &root, const T &item)
depth first search from a root node, searching for a specific item
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)
std::map< T, bool, Compare > _visited
vector of visited nodes

◆ dependsOn() [2/2]

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

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

Definition at line 374 of file DependencyResolver.h.

375 {
376  if (_adj.find(value) == _adj.end())
377  return false;
378 
379  for (auto & n : _adj)
380  _visited[n.first] = false;
381 
382  for (const auto & key : keys)
383  if (dependsOnFromNode(key, value))
384  return true;
385 
386  return false;
387 }
bool dependsOnFromNode(const T &root, const T &item)
depth first search from a root node, searching for a specific item
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)
std::map< T, bool, Compare > _visited
vector of visited nodes

◆ dependsOnFromNode()

template<class T, class Compare >
bool DependencyResolver< T, Compare >::dependsOnFromNode ( const T &  root,
const T &  item 
)
protected

depth first search from a root node, searching for a specific item

Parameters
rootThe node we start from
itemThe node we are searching for

Definition at line 411 of file DependencyResolver.h.

412 {
413  if (root == item)
414  return true;
415 
416  _visited[root] = true;
417 
418  auto & my_dependencies = _inv_adj[root];
419 
420  for (auto & i : my_dependencies)
421  if (!_visited.at(i) && dependsOnFromNode(i, item))
422  return true;
423 
424  return false;
425 }
bool dependsOnFromNode(const T &root, const T &item)
depth first search from a root node, searching for a specific item
std::map< T, std::list< T >, Compare > _inv_adj
adjacency lists (from roots to leaves)
std::map< T, bool, Compare > _visited
vector of visited nodes

◆ dfs()

template<class T , class Compare >
const std::vector< T > & DependencyResolver< T, Compare >::dfs ( )

Do depth-first search from root nodes to obtain order in which graph nodes should be "executed".

Definition at line 259 of file DependencyResolver.h.

Referenced by DependencyResolver< std::string >::getSortedValues(), and DependencyResolverInterface::sortDFS().

260 {
261  _sorted_vector.clear();
262  _visited.clear();
263  _num_visited = 0;
264  _rec_stack.clear();
265  _circular_node = T{};
266 
267  for (auto & n : _adj)
268  {
269  _visited[n.first] = false;
270  _rec_stack[n.first] = false;
271  }
272 
273  bool is_cyclic = false;
274 
275  // If there are no adjacencies, then all nodes are both roots and leaves
276  bool roots_found = _adj.empty();
277  for (auto & n : _insertion_order)
278  if (_adj[n].size() == 0)
279  {
280  roots_found = true;
281  is_cyclic = dfsFromNode(n);
282  if (is_cyclic)
283  break;
284  }
285 
286  if (roots_found)
287  {
288  // At this point, if we have any sub-graphs that are cyclic that do not have any
289  // roots _and_ we have found one more or more separate sub-graphs with a root,
290  // we will have never visited the aforementioned cyclic sub-graphs. Therefore,
291  // at this point if we haven't visited something it's a part of a cyclic sub-graph
292  if (!is_cyclic && _num_visited != _insertion_order.size())
293  {
294  for (const auto & [n, visited] : _visited)
295  if (!visited && (is_cyclic = dfsFromNode(n)))
296  break;
297 
298  mooseAssert(is_cyclic, "Should have found a cyclic dependency");
299  }
300  }
301  // Didn't find any roots
302  else
303  {
304  is_cyclic = true;
305  // Create a cycle graph
306  for (auto & n : _insertion_order)
307  if (dfsFromNode(n))
308  break;
309  }
310 
311  if (is_cyclic)
312  throw CyclicDependencyException<T, Compare>("cyclic graph detected", *this);
313 
314  mooseAssert(_sorted_vector.size() == _insertion_order.size(), "Unexpected sorted size");
315  mooseAssert(_num_visited == _insertion_order.size(), "Did not visit all nodes");
316 
317  return _sorted_vector;
318 }
std::map< T, bool, Compare > _rec_stack
recursive stack
std::size_t size() const
Returns the number of unique items stored in the dependency resolver.
bool dfsFromNode(const T &root)
Perform a depth-first-search from the specified root node.
std::vector< T > _insertion_order
Container for keeping track of the insertion order.
T _circular_node
Data member for storing nodes that appear circularly in the graph.
std::size_t _num_visited
number of visited nodes; used to avoid iterating through _visited
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)
std::vector< T > _sorted_vector
"sorted" vector of nodes
std::map< T, bool, Compare > _visited
vector of visited nodes

◆ dfsFromNode()

template<class T, class Compare >
bool DependencyResolver< T, Compare >::dfsFromNode ( const T &  root)
protected

Perform a depth-first-search from the specified root node.

Populates _visited and _sorted_vector data members

Returns
whether a cyclic graph was detected while performing the depth-first-search from the root node

Definition at line 429 of file DependencyResolver.h.

430 {
431  bool cyclic = false;
432  auto & visited = libmesh_map_find(_visited, root);
433  if (!visited)
434  {
435  ++_num_visited;
436  visited = true;
437  }
438  _rec_stack[root] = true;
439 
440  for (auto & i : _inv_adj[root])
441  {
442  if (!_visited.at(i) && dfsFromNode(i))
443  {
444  cyclic = true;
445  break;
446  }
447  else if (_rec_stack.at(i))
448  {
449  _circular_node = i;
450  _sorted_vector.push_back(i);
451  cyclic = true;
452  break;
453  }
454  }
455 
456  _sorted_vector.push_back(root);
457  _rec_stack[root] = false;
458  return cyclic;
459 }
std::map< T, bool, Compare > _rec_stack
recursive stack
bool dfsFromNode(const T &root)
Perform a depth-first-search from the specified root node.
T _circular_node
Data member for storing nodes that appear circularly in the graph.
std::map< T, std::list< T >, Compare > _inv_adj
adjacency lists (from roots to leaves)
std::size_t _num_visited
number of visited nodes; used to avoid iterating through _visited
std::vector< T > _sorted_vector
"sorted" vector of nodes
std::map< T, bool, Compare > _visited
vector of visited nodes

◆ getAncestors()

template<class T, class Compare >
std::list< T > DependencyResolver< T, Compare >::getAncestors ( const T &  key)

Returns a list of all values that a given key depends on.

Definition at line 391 of file DependencyResolver.h.

Referenced by MeshGeneratorSystem::createMeshGeneratorOrder().

392 {
393  std::vector<T> ret_vec;
394  // Our sorted vector is our work vector but we also return references to it. So we have to make
395  // sure at the end that we restore the original data we had in it
396  ret_vec.swap(_sorted_vector);
397 
398  for (auto & n : _adj)
399  _visited[n.first] = false;
400 
401  dfsFromNode(key);
402 
403  ret_vec.swap(_sorted_vector);
404  mooseAssert(ret_vec.back() == key, "Our key should be the back of the vector");
405 
406  return {ret_vec.begin(), ret_vec.end()};
407 }
bool dfsFromNode(const T &root)
Perform a depth-first-search from the specified root node.
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)
std::vector< T > _sorted_vector
"sorted" vector of nodes
std::map< T, bool, Compare > _visited
vector of visited nodes

◆ getSortedValues()

template<class T, class Compare = std::less<T>>
const std::vector<T>& DependencyResolver< T, Compare >::getSortedValues ( )
inline

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

Referenced by MeshGeneratorSystem::createMeshGeneratorOrder(), FEProblemBase::executeControls(), and Syntax::getSortedTask().

106 { return dfs(); }
const std::vector< T > & dfs()
Do depth-first search from root nodes to obtain order in which graph nodes should be "executed"...

◆ getSortedValuesSets()

template<class T , class Compare >
const std::vector< std::vector< T > > & DependencyResolver< T, Compare >::getSortedValuesSets ( )

Returns a vector of sets that represent dependency resolved values.

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

Definition at line 322 of file DependencyResolver.h.

Referenced by MeshGeneratorSystem::createAddedMeshGenerators(), MeshGeneratorSystem::createMeshGeneratorOrder(), and Syntax::getSortedTaskSet().

323 {
324  _ordered_items.clear();
325 
326  const auto & flat_sorted = dfs();
327 
328  std::vector<T> current_group;
329  for (const auto & object : flat_sorted)
330  {
331  if (current_group.empty())
332  {
333  current_group.push_back(object);
334  continue;
335  }
336 
337  const auto & prev_adj_list = _adj[current_group.back()];
338  const bool depends_on_prev =
339  std::find(prev_adj_list.begin(), prev_adj_list.end(), object) != prev_adj_list.end();
340 
341  if (depends_on_prev)
342  {
343  _ordered_items.push_back({object});
344  auto & finalized_group = _ordered_items.back();
345  // Swap the current-group into the back of our ordered items container, and now our newest
346  // object becomes the current group
347  finalized_group.swap(current_group);
348  }
349  else
350  current_group.push_back(object);
351  }
352 
353  if (!current_group.empty())
354  _ordered_items.push_back(std::move(current_group));
355 
356  return _ordered_items;
357 }
std::vector< std::vector< T > > _ordered_items
The sorted vector of sets.
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)
const std::vector< T > & dfs()
Do depth-first search from root nodes to obtain order in which graph nodes should be "executed"...

◆ insertDependency()

template<class T, class Compare = std::less<T>>
void DependencyResolver< T, Compare >::insertDependency ( const T &  key,
const T &  value 
)
inline

Insert a dependency pair - the first value or the "key" depends on the second value or the "value".

Definition at line 65 of file DependencyResolver.h.

Referenced by Syntax::addDependency().

65 { addEdge(value, key); }
void addEdge(const T &a, const T &b)
Add an edge between nodes &#39;a&#39; and &#39;b&#39;.

◆ removeEdge()

template<class T, class Compare >
void DependencyResolver< T, Compare >::removeEdge ( const T &  a,
const T &  b 
)

Remove an edge between nodes 'a' and 'b'.

Definition at line 220 of file DependencyResolver.h.

Referenced by DependencyResolver< std::string >::deleteDependency().

221 {
222  auto remove_item = [](auto & list, const auto & item)
223  {
224  auto it = std::find(list.begin(), list.end(), item);
225  mooseAssert(it != list.end(), "We should have this item");
226  list.erase(it);
227  };
228  remove_item(_adj[a], b);
229  remove_item(_inv_adj[b], a);
230 }
std::map< T, std::list< T >, Compare > _inv_adj
adjacency lists (from roots to leaves)
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)

◆ removeEdgesInvolving()

template<class T, class Compare >
void DependencyResolver< T, Compare >::removeEdgesInvolving ( const T &  a)

Remove edges drawn from 'a'.

Definition at line 234 of file DependencyResolver.h.

Referenced by DependencyResolver< std::string >::deleteDependenciesOfKey().

235 {
236  const auto & inv_adjs = _inv_adj[a];
237  for (const auto & inv_adj : inv_adjs)
238  {
239  auto & adj = _adj[inv_adj];
240  auto it = std::find(adj.begin(), adj.end(), a);
241  mooseAssert(it != adj.end(), "Should have reciprocity");
242  adj.erase(it);
243  }
244 
245  _inv_adj[a].clear();
246 }
std::map< T, std::list< T >, Compare > _inv_adj
adjacency lists (from roots to leaves)
std::map< T, std::list< T >, Compare > _adj
adjacency lists (from leaves to roots)

◆ size()

template<class T, class Compare = std::less<T>>
std::size_t DependencyResolver< T, Compare >::size ( ) const
inline

Returns the number of unique items stored in the dependency resolver.

lindsayad comment: does it really return the number of unique items?

Definition at line 135 of file DependencyResolver.h.

Referenced by MeshGeneratorSystem::createMeshGeneratorOrder().

135 { return _sorted_vector.size(); }
std::vector< T > _sorted_vector
"sorted" vector of nodes

Friends And Related Function Documentation

◆ CyclicDependencyException< T, Compare >

template<class T, class Compare = std::less<T>>
friend class CyclicDependencyException< T, Compare >
friend

Definition at line 176 of file DependencyResolver.h.

Member Data Documentation

◆ _adj

template<class T, class Compare = std::less<T>>
std::map<T, std::list<T>, Compare> DependencyResolver< T, Compare >::_adj
protected

adjacency lists (from leaves to roots)

Definition at line 154 of file DependencyResolver.h.

◆ _circular_node

template<class T, class Compare = std::less<T>>
T DependencyResolver< T, Compare >::_circular_node = T{}
protected

Data member for storing nodes that appear circularly in the graph.

Definition at line 174 of file DependencyResolver.h.

◆ _insertion_order

template<class T, class Compare = std::less<T>>
std::vector<T> DependencyResolver< T, Compare >::_insertion_order
protected

Container for keeping track of the insertion order.

We will use this to determine iteration order because it is essential that iteration order be sync'd across multiple processes. Iterating over maps with pointer keys, for example, can be out of sync on multiple processes. If dependency resolver memory usage shows up in profiling, we can consider making this a container of reference wrappers

Definition at line 172 of file DependencyResolver.h.

◆ _inv_adj

template<class T, class Compare = std::less<T>>
std::map<T, std::list<T>, Compare> DependencyResolver< T, Compare >::_inv_adj
protected

adjacency lists (from roots to leaves)

Definition at line 156 of file DependencyResolver.h.

◆ _num_visited

template<class T, class Compare = std::less<T>>
std::size_t DependencyResolver< T, Compare >::_num_visited = 0
protected

number of visited nodes; used to avoid iterating through _visited

Definition at line 160 of file DependencyResolver.h.

◆ _ordered_items

template<class T, class Compare = std::less<T>>
std::vector<std::vector<T> > DependencyResolver< T, Compare >::_ordered_items
protected

The sorted vector of sets.

Definition at line 166 of file DependencyResolver.h.

◆ _rec_stack

template<class T, class Compare = std::less<T>>
std::map<T, bool, Compare> DependencyResolver< T, Compare >::_rec_stack
protected

recursive stack

Definition at line 162 of file DependencyResolver.h.

◆ _sorted_vector

template<class T, class Compare = std::less<T>>
std::vector<T> DependencyResolver< T, Compare >::_sorted_vector
protected

"sorted" vector of nodes

Definition at line 164 of file DependencyResolver.h.

Referenced by DependencyResolver< std::string >::size().

◆ _visited

template<class T, class Compare = std::less<T>>
std::map<T, bool, Compare> DependencyResolver< T, Compare >::_visited
protected

vector of visited nodes

Definition at line 158 of file DependencyResolver.h.


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