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

Question

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

How can I detect those cycles to stop recursing?

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

What cannot happend is that a horse appear as a father or grandfather or greatgrandfather of ITSELF.

Answer 1

Maintain a stack of all elements leading up to the root of the tree.

Every time you advance down the tree, scan the stack for the child element. If you find a match, then you've discovered a loop and should skip that child. Otherwise, push the child onto the stack and proceed. Whenever you backtrack up the tree, pop an element out of the stack and discard.

(In the case of genealogical data, a "child" node in the tree is presumably the biological parent of the "parent" node.)

Answer 2

A very simple way to detect this, is by checking that constraint itself:

What cannot happend is that a horse appear as a father or grandfather or greatgrandfather of ITSELF.

Whenever you insert a node in your tree, traverse the tree to the root to make sure that the horse does not exist as a any kind of parent.

To speed this up, you can associate a hashtable to each node, where you cache the answer of such a lookup. Then you don't have to search the entire path next time you insert a horse under that node.

Consider a path of A -> B -> C (that is A is the root and B is a child of A and C is a child of C. Then you want to insert a horse B under C. then you traverse towards A and find that the same horse is a parent of C, so you add B to a hashtable in the node C. Then the next time you want to add B anywhere under C, you dont have to look further than C.

I'm not sure that whis optimization will really be an optimization, as it depends a lot on the data.

Answer 3

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)

Answer 4

Your hash table solution should work if you keep track of nodes instead of horses. Just make sure every time you read a new horse you create a new node even if the value/horse is the same as a previous node's value/horse.

Answer 5

You're dealing with a directed acyclic graph, not a tree. There should not be any cycles, as a horse's descendant cannot also be its ancestor.

Knowing this, you should apply code techniques specific to directed acyclic graphs.

Answer 6

very useful pseudo codes

Answer 7

This sounds like a case where you can finally apply that interview trivia question: find a cycle in a linked list using only O(1) memory.

In this case your "linked list" is the sequence of elements you enumerate. Use two enumerators, run one at half speed, and if the fast one ever runs into the slow one then you have a loop. This will also be O(n) time instead of the O(n^2) time required for checking a 'seen' list. The downside is you only find out about the loop after some of the nodes have been processed multiple times.

In the example I've replaced the 'half speed' method with the simpler-to-write 'drop markers' method.

class GenTreeNode {
    ...

    ///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary>
    private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) {
        long cur_track_count = 0;
        long high_track_count = 1;
        T post = default(T);
        foreach (var e in sub_enumerable) {
            yield return e;
            if (++cur_track_count >= high_track_count) {
                post = e;
                high_track_count *= 2;
                cur_track_count = 0;
            } else if (object.ReferenceEquals(e, post)) {
                throw new Exception("Infinite Loop");
            }
        }
    }

    ...

    ///<summary>Enumerates the tree's nodes, assuming no cycles</summary>
    private IEnumerable<GenTreeNode> tree_nodes_unchecked() {
        yield return this;
        foreach (var child in this.nodes)
            foreach (var e in child.tree_nodes_unchecked())
                yield return e;
    }
    ///<summary>Enumerates the tree's nodes, checking for cycles</summary>
    public IEnumerable<GenTreeNode> tree_nodes()
    {
        return CheckedEnumerable(tree_nodes_unchecked());
    }

    ...

    void ProcessTree() {
        foreach (var node in tree_nodes())
            proceess(node);
    }
}