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.") else: 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") plt.show()
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.