Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-28971

Error in depth_first_search algorithm incorrectly recurses on visited nodes

    • 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
      

            Assignee:
            eddie.louie Eddie Louie
            Reporter:
            eddie.louie Eddie Louie
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated:
              Resolved: