base-dag 0.1.2

A simple base implementation of a Directed Acyclic Graph, intended to be subclassed for more specific functionality.

base-dag

A simple base implementation of a DAG. Users should feel free to subclass this DAG class to provide their desired functionality. The API is intended to be similar to the NetworkX API, though not an exact replica. Note that multiple edges between the same two nodes are not supported by this package.

Creating a DAG.

from base_dag import DAG

# Initialize the DAG
dag = DAG()

# Add nodes and edges
dag.add_nodes_from([1, 2])
dag.add_node(3)
dag.add_edge((1, 2))
dag.add_edge((2, 3))

# Remove nodes and edges
dag.remove_edge((2, 3))
dag.remove_node(3)

Subgraph

# Re-add a third node.
dag.add_node(3)
# Extract the subgraph of nodes 1 and 2.
sub_dag = dag.subgraph([1, 2])

Other Operations

Successors and Predecessors

successors = dag.successors(1) # [2]
predecessors = dag.predecessors(2) # [1]

Indegree and Outdegree

in_degree = dag.indegree(2) # 1
out_degree = dag.outdegree(1) # 1

Descendants

descendants = dag.descendants(1) # [2, 3]
ancestors = dag.ancestors(2) # [1]

All nodes & edges

all_nodes = dag.nodes() # (1, 2, 3)
all_edges = dag.edges() # ( (1, 2), (2, 3) )

Reverse

# Reverse the direction of the edges in the graph in place, without affecting the nodes at all.
dag.reverse()

Topological sort

sorted_nodes = dag.topological_sort()

Topological generations

generations = dag.topological_generations()

Sorted topological generations

sorted_generations = dag.sorted_topological_generations()

has_path

has_path = dag.has_path(1, 3) # True

is_acyclic

is_acyclic = dag.is_acyclic() # True