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.