Base class for TaskGraph, a collection of TaskNode's. Maintains nodes, adjacencyList, and invAdjacencyList. More...
#include <imstkTaskGraph.h>
Public Member Functions | |
| TaskGraph (std::string sourceName="Source", std::string sinkName="Sink") | |
| std::shared_ptr< TaskNode > | getSource () const |
| std::shared_ptr< TaskNode > | getSink () const |
| TaskNodeVector & | getNodes () |
| Get the nodes belonging to this graph HS This is bad, there are algorithms that change the nodes of the graph from the outside. | |
| const TaskNodeAdjList & | getAdjList () const |
| Get the edges belonging to this graph. | |
| const TaskNodeAdjList & | getInvAdjList () const |
| Get the inverse edges belonging to this graph. | |
| TaskNodeVector::iterator | findNode (std::string name) |
| Linear search for node by name within this graph. | |
| TaskNodeVector::const_iterator | findNode (std::string name) const |
| TaskNodeVector::iterator | findNode (std::shared_ptr< TaskNode > node) |
| Linear search for node within this graph. | |
| TaskNodeVector::const_iterator | findNode (std::shared_ptr< TaskNode > node) const |
| bool | containsNode (std::shared_ptr< TaskNode > node) const |
| Check if node exists in this graph. | |
| TaskNodeVector::iterator | endNode () |
| Returns the start of the node container. | |
| TaskNodeVector::const_iterator | endNode () const |
| TaskNodeVector::iterator | beginNode () |
| Returns the start of the node container. | |
| TaskNodeVector::const_iterator | beginNode () const |
| bool | addNode (std::shared_ptr< TaskNode > node) |
| Adds a node to the graph, returns if successful. Returns false and fails if node already exists in graph. | |
| void | addNodes (const std::vector< std::shared_ptr< TaskNode >> &nodes) |
| Adds a series of nodes at the same time Use with {} initializer for easier graph construction. | |
| std::shared_ptr< TaskNode > | addFunction (std::string name, std::function< void()> func) |
| Creates a node for the function, adds it to the graph. | |
| bool | removeNode (std::shared_ptr< TaskNode > node) |
| Removes node from the graph and all relevant edges Returns false and fails if node is not present in graph. | |
| bool | removeNodeAndRedirect (std::shared_ptr< TaskNode > node) |
| Removes node from the graph and all relevant edges. Any incoming edges to the node are redirected to all its outputs. | |
| void | insertAfter (std::shared_ptr< TaskNode > refNode, std::shared_ptr< TaskNode > newNode) |
| newNode gets placed after refNode & added to the graph. newNode takes on refNode's outputs | |
| void | insertBefore (std::shared_ptr< TaskNode > refNode, std::shared_ptr< TaskNode > newNode) |
| newNode gets placed before refNode & added to the graph. newNode takes on refNode's inputs | |
| bool | containsEdge (std::shared_ptr< TaskNode > srcNode, std::shared_ptr< TaskNode > destNode) const |
| Returns whether or not this graph contains the given directed edge. | |
| void | addEdge (std::shared_ptr< TaskNode > srcNode, std::shared_ptr< TaskNode > destNode) |
| Adds a directed edge to the graph both the source and target have to exist in the graph. | |
| void | addEdges (const std::vector< std::pair< std::shared_ptr< TaskNode >, std::shared_ptr< TaskNode >>> &edges) |
| Adds a series of directed edges {source, target} to the graph both the source and target of the edge have to exist in the graph. | |
| void | nestGraph (std::shared_ptr< TaskGraph > subgraph, std::shared_ptr< TaskNode > source, std::shared_ptr< TaskNode > sink) |
| Attaches another TaskGraph as a subgraph (copies nodes and edges, then connects source->subgraph::source, subgraph::sink->sink), source and sink must exist in this graph. Also serves as a graph sum between this and subgraph. | |
| void | removeEdge (std::shared_ptr< TaskNode > srcNode, std::shared_ptr< TaskNode > destNode) |
| Removes an edge from the graph (removes from adjList and invAdjList, cleans) | |
| bool | isReachable (std::shared_ptr< TaskNode > srcNode, std::shared_ptr< TaskNode > destNode) |
| Returns true if srcNode reaches destNode. | |
| void | clear () |
| Removes all nodes & edges from the graph. Source and sink nodes maintained. | |
| void | clearEdges () |
| Removes all edges from the graph. | |
Static Public Member Functions | |
| static std::shared_ptr< TaskNodeList > | topologicalSort (std::shared_ptr< TaskGraph > graph) |
| Graph sum, shared references are considered identical nodes, source/sink of results invalidated/nullptr. More... | |
| static std::shared_ptr< TaskGraph > | transitiveReduce (std::shared_ptr< TaskGraph > graph) |
| Remove redundant edges. Removal is such that all vertices are still reachable and graph goes from source->sink returns nullptr if failed. Only fails if graph is cyclic. | |
| static std::shared_ptr< TaskGraph > | removeRedundantNodes (std::shared_ptr< TaskGraph > graph) |
| Removes nullptr/nonfunctional TaskNode's that don't split/join. | |
| static std::shared_ptr< TaskGraph > | reduce (std::shared_ptr< TaskGraph > graph) |
| Simplifies the graph in a way that retains functionality Performs transitive reduction then redundant node removal to remove redundant nodes and edges. | |
| static std::shared_ptr< TaskGraph > | removeUnusedNodes (std::shared_ptr< TaskGraph > graph) |
| static bool | isCyclic (std::shared_ptr< TaskGraph > graph) |
| Returns if Graph is cyclic or not. | |
| static TaskNodeNameMap | getUniqueNodeNames (std::shared_ptr< TaskGraph > graph, bool apply=false) |
| Nodes may not have unique names. Iterates the names with numeric postfix to generate uniques. | |
| static std::unordered_map< std::shared_ptr< TaskNode >, double > | getNodeStartTimes (std::shared_ptr< TaskGraph > graph) |
| Gets the completion times of each node (source = ~0s) | |
| static TaskNodeList | getCriticalPath (std::shared_ptr< TaskGraph > graph) |
| Computes the critical path. | |
Protected Attributes | |
| TaskNodeVector | m_nodes |
| TaskNodeAdjList | m_adjList |
| This gives the outputs of every node. | |
| TaskNodeAdjList | m_invAdjList |
| This gives the inputs of every node. | |
| std::shared_ptr< TaskNode > | m_source = nullptr |
| std::shared_ptr< TaskNode > | m_sink = nullptr |
Detailed Description
Base class for TaskGraph, a collection of TaskNode's. Maintains nodes, adjacencyList, and invAdjacencyList.
Definition at line 61 of file imstkTaskGraph.h.
Member Function Documentation
◆ topologicalSort()
|
static |
Graph sum, shared references are considered identical nodes, source/sink of results invalidated/nullptr.
Topological sort of all nodes within graph
Definition at line 415 of file imstkTaskGraph.cpp.
Here is the caller graph for this function:
The documentation for this class was generated from the following files:
- Source/Common/TaskGraph/imstkTaskGraph.h
- Source/Common/TaskGraph/imstkTaskGraph.cpp
