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.

void	addEdge (const T &a, const T &b)
	Add an edge between nodes 'a' and 'b'.

void	removeEdge (const T &a, const T &b)
	Remove an edge between nodes 'a' and 'b'.

void	removeEdgesInvolving (const T &a)
	Remove edges drawn from 'a'.

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

void	deleteDependency (const T &key, const T &value)
	Delete a dependency (only the edge) between items in the resolver.

void	deleteDependenciesOfKey (const T &key)
	Removes dependencies of the given key.

void	addItem (const T &value)
	Add an independent item to the set.

void	clear ()
	Clear Items from the resolver.

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

const std::vector< std::vector< T > > &	getSortedValuesSets ()
	Returns a vector of sets that represent dependency resolved values.

const std::vector< T > &	getSortedValues ()
	This function also returns dependency resolved values but with a simpler single vector interface.

bool	dependsOn (const T &key, const T &value)
	Return true if key depends on value.

bool	dependsOn (const std::vector< T > &keys, const T &value)
	Return true if any of elements of keys depends on value.

std::list< T >	getAncestors (const T &key)
	Returns a list of all values that a given key depends on.

std::size_t	size () const
	Returns the number of unique items stored in the dependency resolver.

Protected Member Functions
bool	dependsOnFromNode (const T &root, const T &item)
	depth first search from a root node, searching for a specific item

bool	dfsFromNode (const T &root)
	Perform a depth-first-search from the specified `root` node.

Protected Attributes
std::map< T, std::list< T >, Compare >	_adj
	adjacency lists (from leaves to roots)

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

std::size_t	_num_visited = 0
	number of visited nodes; used to avoid iterating through _visited

std::map< T, bool, Compare >	_rec_stack
	recursive stack

std::vector< T >	_sorted_vector
	"sorted" vector of nodes

std::vector< std::vector< T > >	_ordered_items
	The sorted vector of sets.

std::vector< T >	_insertion_order
	Container for keeping track of the insertion order.

T	_circular_node = T{}
	Data member for storing nodes that appear circularly in the graph.

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.

{
  addNode(a);
  addNode(b);
 
  _adj[a].push_back(b);
  _inv_adj[b].push_back(a);
}

Referenced by MeshGeneratorSystem::createAddedMeshGenerators(), MeshGeneratorSystem::createMeshGeneratorOrder(), FEProblemBase::executeControls(), DependencyResolver< T, Compare >::insertDependency(), MFEMProblem::resolveMFEMSolvers(), DependencyResolverInterface::sortDFS(), and ActionWarehouse::sortUserObjectActions().

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

80{ addNode(value); }

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

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

{
#ifndef NDEBUG
  bool new_adj_insertion = false, new_inv_insertion = false;
#endif
  if (_adj.find(a) == _adj.end())
  {
#ifndef NDEBUG
    new_adj_insertion = true;
#endif
    _adj[a] = {};
    _insertion_order.push_back(a);
  }
 
  if (_inv_adj.find(a) == _inv_adj.end())
  {
#ifndef NDEBUG
    new_inv_insertion = true;
#endif
    _inv_adj[a] = {};
  }
  mooseAssert(new_adj_insertion == new_inv_insertion,
              "We should have symmetric behavior between adjacent and inverse-adjacent "
              "insertion/non-insertion.");
}

Referenced by DependencyResolver< T, Compare >::addItem(), MFEMProblem::resolveMFEMSolvers(), and DependencyResolverInterface::sortDFS().

◆ clear()

template<class T , class Compare >

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

Clear Items from the resolver.

Definition at line 250 of file DependencyResolver.h.

{
  _adj.clear();
  _inv_adj.clear();
  _insertion_order.clear();
}

Referenced by Syntax::clearTaskDependencies().

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

75{ removeEdgesInvolving(key); }

DependencyResolver::removeEdgesInvolving

void removeEdgesInvolving(const T &a)

Remove edges drawn from 'a'.

Definition DependencyResolver.h:234

Referenced by Syntax::deleteTaskDependencies().

◆ 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); }

DependencyResolver::removeEdge

void removeEdge(const T &a, const T &b)

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

Definition DependencyResolver.h:220

◆ dependsOn() [1/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.

{
  if (_adj.find(value) == _adj.end())
    return false;
 
  for (auto & n : _adj)
    _visited[n.first] = false;
 
  for (const auto & key : keys)
    if (dependsOnFromNode(key, value))
      return true;
 
  return false;
}

◆ dependsOn() [2/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.

{
  if (_adj.find(value) == _adj.end())
    return false;
 
  for (auto & n : _adj)
    _visited[n.first] = false;
 
  return dependsOnFromNode(key, value);
}

Referenced by MeshGeneratorSystem::createAddedMeshGenerators().

◆ 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

root	The node we start from
item	The node we are searching for

Definition at line 411 of file DependencyResolver.h.

{
  if (root == item)
    return true;
 
  _visited[root] = true;
 
  auto & my_dependencies = _inv_adj[root];
 
  for (auto & i : my_dependencies)
    if (!_visited.at(i) && dependsOnFromNode(i, item))
      return true;
 
  return false;
}

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

{
  _sorted_vector.clear();
  _visited.clear();
  _num_visited = 0;
  _rec_stack.clear();
  _circular_node = T{};
 
  for (auto & n : _adj)
  {
    _visited[n.first] = false;
    _rec_stack[n.first] = false;
  }
 
  bool is_cyclic = false;
 
  // If there are no adjacencies, then all nodes are both roots and leaves
  bool roots_found = _adj.empty();
  for (auto & n : _insertion_order)
    if (_adj[n].size() == 0)
    {
      roots_found = true;
      is_cyclic = dfsFromNode(n);
      if (is_cyclic)
        break;
    }
 
  if (roots_found)
  {
    // At this point, if we have any sub-graphs that are cyclic that do not have any
    // roots _and_ we have found one more or more separate sub-graphs with a root,
    // we will have never visited the aforementioned cyclic sub-graphs. Therefore,
    // at this point if we haven't visited something it's a part of a cyclic sub-graph
    if (!is_cyclic && _num_visited != _insertion_order.size())
    {
      for (const auto & [n, visited] : _visited)
        if (!visited && (is_cyclic = dfsFromNode(n)))
          break;
 
      mooseAssert(is_cyclic, "Should have found a cyclic dependency");
    }
  }
  // Didn't find any roots
  else
  {
    is_cyclic = true;
    // Create a cycle graph
    for (auto & n : _insertion_order)
      if (dfsFromNode(n))
        break;
  }
 
  if (is_cyclic)
    throw CyclicDependencyException<T, Compare>("cyclic graph detected", *this);
 
  mooseAssert(_sorted_vector.size() == _insertion_order.size(), "Unexpected sorted size");
  mooseAssert(_num_visited == _insertion_order.size(), "Did not visit all nodes");
 
  return _sorted_vector;
}

Referenced by DependencyResolver< T, Compare >::getSortedValues(), and DependencyResolverInterface::sortDFS().

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

{
  bool cyclic = false;
  auto & visited = libmesh_map_find(_visited, root);
  if (!visited)
  {
    ++_num_visited;
    visited = true;
  }
  _rec_stack[root] = true;
 
  for (auto & i : _inv_adj[root])
  {
    if (!_visited.at(i) && dfsFromNode(i))
    {
      cyclic = true;
      break;
    }
    else if (_rec_stack.at(i))
    {
      _circular_node = i;
      _sorted_vector.push_back(i);
      cyclic = true;
      break;
    }
  }
 
  _sorted_vector.push_back(root);
  _rec_stack[root] = false;
  return cyclic;
}

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

{
  std::vector<T> ret_vec;
  // Our sorted vector is our work vector but we also return references to it. So we have to make
  // sure at the end that we restore the original data we had in it
  ret_vec.swap(_sorted_vector);
 
  for (auto & n : _adj)
    _visited[n.first] = false;
 
  dfsFromNode(key);
 
  ret_vec.swap(_sorted_vector);
  mooseAssert(ret_vec.back() == key, "Our key should be the back of the vector");
 
  return {ret_vec.begin(), ret_vec.end()};
}

Referenced by MeshGeneratorSystem::createMeshGeneratorOrder().

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

106{ return dfs(); }

DependencyResolver::dfs

const std::vector< T > & dfs()

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

Definition DependencyResolver.h:259

Referenced by MeshGeneratorSystem::createMeshGeneratorOrder(), FEProblemBase::executeControls(), Syntax::getSortedTask(), MFEMProblem::resolveMFEMSolvers(), and ActionWarehouse::sortUserObjectActions().

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

{
  _ordered_items.clear();
 
  const auto & flat_sorted = dfs();
 
  std::vector<T> current_group;
  for (const auto & object : flat_sorted)
  {
    if (current_group.empty())
    {
      current_group.push_back(object);
      continue;
    }
 
    const auto & prev_adj_list = _adj[current_group.back()];
    const bool depends_on_prev =
        std::find(prev_adj_list.begin(), prev_adj_list.end(), object) != prev_adj_list.end();
 
    if (depends_on_prev)
    {
      _ordered_items.push_back({object});
      auto & finalized_group = _ordered_items.back();
      // Swap the current-group into the back of our ordered items container, and now our newest
      // object becomes the current group
      finalized_group.swap(current_group);
    }
    else
      current_group.push_back(object);
  }
 
  if (!current_group.empty())
    _ordered_items.push_back(std::move(current_group));
 
  return _ordered_items;
}

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

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

65{ addEdge(value, key); }

DependencyResolver::addEdge

void addEdge(const T &a, const T &b)

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

Definition DependencyResolver.h:209

Referenced by Syntax::addDependency().

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

{
  auto remove_item = [](auto & list, const auto & item)
  {
    auto it = std::find(list.begin(), list.end(), item);
    mooseAssert(it != list.end(), "We should have this item");
    list.erase(it);
  };
  remove_item(_adj[a], b);
  remove_item(_inv_adj[b], a);
}

Referenced by DependencyResolver< T, Compare >::deleteDependency().

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

{
  const auto & inv_adjs = _inv_adj[a];
  for (const auto & inv_adj : inv_adjs)
  {
    auto & adj = _adj[inv_adj];
    auto it = std::find(adj.begin(), adj.end(), a);
    mooseAssert(it != adj.end(), "Should have reciprocity");
    adj.erase(it);
  }
 
  _inv_adj[a].clear();
}

Referenced by DependencyResolver< T, Compare >::deleteDependenciesOfKey().

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

135{ return _sorted_vector.size(); }

Referenced by MeshGeneratorSystem::createMeshGeneratorOrder().

Friends And Related Symbol Documentation

◆ CyclicDependencyException< T, Compare >

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

friend class CyclicDependencyException< T, Compare >

friend

Definition at line 174 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.

174{};

◆ _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< T, Compare >::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:

include/utils/DependencyResolver.h

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ DependencyResolver()

◆ ~DependencyResolver()

Member Function Documentation

◆ addEdge()

◆ addItem()

◆ addNode()

◆ clear()

◆ deleteDependenciesOfKey()

◆ deleteDependency()

◆ dependsOn() [1/2]

◆ dependsOn() [2/2]

◆ dependsOnFromNode()

◆ dfs()

◆ dfsFromNode()

◆ getAncestors()

◆ getSortedValues()

◆ getSortedValuesSets()

◆ insertDependency()

◆ removeEdge()

◆ removeEdgesInvolving()

◆ size()

Friends And Related Symbol Documentation

◆ CyclicDependencyException< T, Compare >

Member Data Documentation

◆ _adj

◆ _circular_node

◆ _insertion_order

◆ _inv_adj

◆ _num_visited

◆ _ordered_items

◆ _rec_stack

◆ _sorted_vector

◆ _visited