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... | |
T | _circular_node = T{} |
Data member for storing nodes that appear circularly in the graph. More... | |
Friends | |
class | CyclicDependencyException< T, Compare > |
Class that represents the dependecy as a graph.
Definition at line 35 of file DependencyResolver.h.
|
default |
|
default |
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().
|
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().
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().
void DependencyResolver< T, Compare >::clear | ( | ) |
Clear Items from the resolver.
Definition at line 250 of file DependencyResolver.h.
Referenced by Syntax::clearTaskDependencies().
|
inline |
Removes dependencies of the given key.
Definition at line 75 of file DependencyResolver.h.
Referenced by Syntax::deleteTaskDependencies().
|
inline |
Delete a dependency (only the edge) between items in the resolver.
Definition at line 70 of file DependencyResolver.h.
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().
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.
|
protected |
depth first search from a root node, searching for a specific item
root | The node we start from |
item | The node we are searching for |
Definition at line 411 of file DependencyResolver.h.
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().
|
protected |
Perform a depth-first-search from the specified root
node.
Populates _visited and _sorted_vector data members
root
node Definition at line 429 of file DependencyResolver.h.
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().
|
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().
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().
|
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().
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().
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().
|
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().
|
friend |
Definition at line 176 of file DependencyResolver.h.
|
protected |
adjacency lists (from leaves to roots)
Definition at line 154 of file DependencyResolver.h.
|
protected |
Data member for storing nodes that appear circularly in the graph.
Definition at line 174 of file DependencyResolver.h.
|
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.
|
protected |
adjacency lists (from roots to leaves)
Definition at line 156 of file DependencyResolver.h.
|
protected |
number of visited nodes; used to avoid iterating through _visited
Definition at line 160 of file DependencyResolver.h.
|
protected |
The sorted vector of sets.
Definition at line 166 of file DependencyResolver.h.
|
protected |
recursive stack
Definition at line 162 of file DependencyResolver.h.
|
protected |
"sorted" vector of nodes
Definition at line 164 of file DependencyResolver.h.
Referenced by DependencyResolver< std::string >::size().
|
protected |
vector of visited nodes
Definition at line 158 of file DependencyResolver.h.