def depth_first_search(self, node_key, nodes_visited, nodes_in_cycle=[]):
|
"""
|
The nodes_visited is a set of nodes which indicates it has been visited.
|
The node_in_cycle is a list of nodes in the potential cycle.
|
Returns the list of nodes in the cycle or None.
|
"""
|
nodes_visited.add(node_key)
|
nodes_in_cycle.append(node_key)
|
for node in self.nodes[node_key]['next_nodes']:
|
if node in nodes_in_cycle:
|
# The graph cycle starts at the index of node in nodes_in_cycle.
|
return nodes_in_cycle[nodes_in_cycle.index(node):]
|
if node in nodes_visited: <<<<------------ Should be "node not in nodes_visited"
|
dfs_nodes = self.depth_first_search(node, nodes_visited, nodes_in_cycle)
|
if dfs_nodes:
|
return dfs_nodes
|
|
# This node_key is not part of the graph cycle.
|
nodes_in_cycle.pop()
|
return None
|