-
Type: Bug
-
Resolution: Fixed
-
Priority: Major - P3
-
Affects Version/s: 3.5.6
-
Component/s: Testing Infrastructure
-
Fully Compatible
-
ALL
-
v3.4
-
TIG 2017-05-08
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