An acyclic graph is a graph with no cycles. A cycle is a path that starts and ends at the same vertex, so an acyclic graph never allows you to follow edges and return to where you began. section 13.5
A follower graph
Imagine directed follower relationships among animals. Giraffe→Crocodile→Monkey→Giraffe forms a cycle, so that graph is not acyclic. Removing every route that eventually returns to its starting vertex produces an acyclic graph. section 13.5
Use depth-first search (DFS) to check whether a directed graph is acyclic:
- Mark each vertex white before exploration. section 13.14
- Mark a vertex gray while exploring its outgoing edges, then black after all those edges have been processed. section 13.14
- Finding a gray vertex again reveals a cycle; if no gray vertex is encountered, the graph is acyclic. section 13.14
def dfs(self, start_vertex, color=None):
if color is None:
color = {v: 'white' for v in self._adj}
acyclic = True
stack = Stack()
stack.push((False, start_vertex))
while not stack.is_empty():
(mark_as_black, v) = stack.pop()
col = color.get(v, 'white')
if mark_as_black:
color[v] = 'black'
elif col == 'grey':
acyclic = False
elif col == 'white':
color[v] = 'grey'
stack.push((True, v))
for (_, w) in self._get_vertex(v).outgoing_edges():
stack.push((False, w))
return acyclic, color
The iterative DFS implementation uses a stack, gray and black markers, and an acyclic flag to detect cycles. section 13.14
