runway.cfngin.dag package¶
CFNgin directed acyclic graph (DAG) implementation.
-
class
runway.cfngin.dag.
DAG
[source]¶ Bases:
object
Directed acyclic graph implementation.
Instantiate a new DAG with no nodes or edges.
-
add_edge
(ind_node, dep_node)[source]¶ Add an edge (dependency) between the specified nodes.
- Parameters
- Raises
KeyError – Either the ind_node, or dep_node do not exist.
DAGValidationError – Raised if the resulting graph is invalid.
-
add_node_if_not_exists
(node_name)[source]¶ Add a node if it does not exist yet, ignoring duplicates.
- Parameters
node_name (str) – The name of the node to add.
-
all_leaves
()[source]¶ Return a list of all leaves (nodes with no downstreams).
- Returns
A list of all the nodes with no downstreams.
- Return type
List[str]
-
delete_node_if_exists
(node_name)[source]¶ Delete this node and all edges referencing it.
Ignores any node that is not in the graph, rather than throwing an exception.
- Parameters
node_name (str) – The name of the node to delete.
-
from_dict
(graph_dict)[source]¶ Reset the graph and build it from the passed dictionary.
The dictionary takes the form of {node_name: [directed edges]}
-
ind_nodes
()[source]¶ Return a list of all nodes in the graph with no dependencies.
- Returns
A list of all independent nodes.
- Return type
List[str]
-
topological_sort
()[source]¶ Return a topological ordering of the DAG.
- Returns
A list of topologically sorted nodes in the graph.
- Return type
- Raises
ValueError – Raised if the graph is not acyclic.
-
transitive_reduction
()[source]¶ Perform a transitive reduction on the DAG.
The transitive reduction of a graph is a graph with as few edges as possible with the same reachability as the original graph.
-
transpose
()[source]¶ Build a new graph with the edges reversed.
- Returns
The transposed graph.
- Return type
-
walk
(walk_func)[source]¶ Walk each node of the graph in reverse topological order.
This can be used to perform a set of operations, where the next operation depends on the previous operation. It’s important to note that walking happens serially, and is not parallelized.
- Parameters
walk_func (
types.FunctionType
) – The function to be called on each node of the graph.
-
-
exception
runway.cfngin.dag.
DAGValidationError
[source]¶ Bases:
Exception
Raised when DAG validation fails.
-
class
runway.cfngin.dag.
ThreadedWalker
(semaphore)[source]¶ Bases:
object
Walk a DAG as quickly as the graph topology allows, using threads.
Instantiate class.
- Parameters
semaphore (threading.Semaphore) – a semaphore object which can be used to control how many steps are executed in parallel.