.netalgorithmbinary-treegenealogy

Detect cycles in a genealogy graph during a Depth-first search


I'm loading horse genealogical data recursively. For some wrong sets of data my recursion never stops... and that is because there are cycles in the data.

How can I detect those cycles to stop recurring?

I thought of while recurring maintain a hashTable with all "visited" horses. But that will find some false positives, because a horse CAN be twice in a tree.

What cannot happen is that a horse appear as a father or grandfather or great grandfather of ITSELF.


Solution

  • Pseudo code:

    void ProcessTree(GenTreeNode currentNode, Stack<GenTreeNode> seen)
    {
       if(seen.Contains(currentNode)) return;
       // Or, do whatever needs to be done when a cycle is detected
    
       ProcessHorse(currentNode.Horse); // Or whatever processing you need
    
       seen.Push(currentNode);
    
       foreach(GenTreeNode childNode in currentNode.Nodes)
       {
          ProcessTree(childNode, seen);
       }
    
       seen.Pop();
    }
    

    The basic idea is to keep a list of all of the nodes that we've already seen on our way down to the current node; if was get back to a node that we already went through, then you know that we've formed a cycle (and we should skip the value, or do whatever needs to be done)