An Example of a Directed Acyclic Graph in Python


What is a directed acyclic graph?

In mathematics, a directed graph is a set with a not necessarily symmetric binary relation, meaning given any two elements x and y in that set, if x is related to y, it is not always the case that y is related to x.

Pictorially, a directed graph is represented as nodes for the elements and arrows between the nodes for the binary relation.

A directed graph has a cycle if it has a collection of elements such that each x of them is related to exactly one element in that collection and exactly one element in that collection is related to x.

A directed acyclic graph is a directed graph with no cycle.

A directed acyclic graph in Python

We use the Python package Networkx to define a directed acyclic graph and the package Matplotlib to output the image of that graph.

import networkx as nx
import matplotlib.pyplot as plt

# Create an empty directed graph
graph = nx.DiGraph()

# Add nodes to the graph
graph.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])

# Add edges to the graph
graph.add_edges_from([('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'E'), ('C', 'E'), ('C', 'F'),
('D', 'F'), ('E', 'G'), ('F', 'G'), ('G', 'H'), ('H', 'I')])

# Check if the graph is acyclic
if nx.is_directed_acyclic_graph(graph):
print("The graph is acyclic.")
print("The graph contains cycles.")

# Plot the graph
pos = nx.spring_layout(graph) # Layout the graph nodes
nx.draw(graph, pos, with_labels=True, node_color='lightblue', node_size=1000, font_size=10, arrows=True)
plt.title("Acyclic Directed Graph")

We add nodes ‘A’ to ‘I’ using the add_nodes_from() method, which takes a list of nodes as input.

We then define the edges of the graph using the add_edges_from() method. Each tuple in the list represents an edge, where the first element is the source node and the second element is the target node.

After adding the nodes and edges, we check if the graph is acyclic using is_directed_acyclic_graph() function. If it is acyclic, it will print “The graph is acyclic.” Otherwise, it will print “The graph contains cycles.”

Finally, we plot the graph using the spring_layout algorithm for node positioning and visualize it using networkx and matplotlib. The nodes are labeled, and the graph is displayed with arrows indicating the direction of the edges.

The directed acyclic graph from the Python code

directed acyclic graph python