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

Error in depth_first_search algorithm incorrectly recurses on visited nodes

    XMLWordPrintable

    Details

    • Backwards Compatibility:
      Fully Compatible
    • Operating System:
      ALL
    • Backport Requested:
      v3.4
    • Sprint:
      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
      

        Attachments

          Activity

            People

            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: