Let's take a look at what a directed acyclic graph (DAG) is first. A directed acyclic graph is a graph that is directed, which means that the edges from a given vertex A to B will be directed in a particular direction (A->B or B->A) and is acyclic. Acyclic graphs are those graphs that are not cyclic, which also means that there is no cycle (they don't go around in cycle).

What is a good example of a DAG? A tree or even a trie. We all know what they are because it was discussed in one of the previous chapters of this book. A good example of using trie is to store the words of dictionaries and have a spell check algorithm. We will not go further into details about this, but in the context of visualization and to check whether a graph is acyclic or not, we will determine the Python packages that offer methods to test whether a graph is acyclic or not.

NetworkX has a convenient function called is_directed_acyclic_graph (Graph). Here is an example of a graph that is acyclic; using this function, we will test to see whether it returns true:

import matplotlib.pyplot as plt
import pylab
from pylab import rcParams

import networkx as nx
import numpy as np

# set the graph display size as 10 by 10 inches
rcParams['figure.figsize'] = 10, 10

G = nx.DiGraph()

# Add the edges and weights
G.add_edges_from([('K', 'I'),('R','T'),('V','T')], weight=3)
G.add_edges_from([('T','K'),('T','H'),('T','H')], weight=4)
# these values to determine node colors
val_map = {'K': 1.5, 'I': 0.9, 'R': 0.6, 'T': 0.2}
values = [val_map.get(node, 1.0) for node in G.nodes()]

edge_labels=dict([((u,v,),d['weight'])
                 for u,v,d in G.edges(data=True)])

#set edge colors
red_edges = [('R','T'),('T','K')]
edge_colors = ['green' if not edge in red_edges else 'red' for edge in G.edges()]

pos=nx.spring_layout(G)

nx.draw_networkx_edges(G,pos,width=2.0,alpha=0.65)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)

nx.draw(G,pos, node_color = values, node_size=1500,
 edge_color=edge_colors, edge_cmap=plt.cm.Reds)

pylab.show()
nx.is_directed_acyclic_graph(G) 

True

The acyclic graph from this example is displayed in the following diagram: