Details
-
Bug
-
Resolution: Fixed
-
Major - P3
-
3.5.6
-
Fully Compatible
-
ALL
-
v3.4
-
TIG 2017-05-08
Description
In one of our CR for SERVER-28348 we missed this logic bug. The recursion should only happen for nodes that we have not visited yet.
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 |