Detection of cycles in the genealogy chart during a depth search

Question

I recursively download the genealogy of the horse. For some incorrect datasets, my recursion never stops ... and this is because there are loops in the data.

How can I find that these cycles stop repeating?

I thought I repeat, keep hashTable with all the "visited" horses. But it will find false positives because the horse MAY be twice in the tree.

What cannot happen is that the horse appears as a father or grandfather or great-grandfather of MYSELF.

Answer 1

Pseudocode:

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 main idea is to keep a list of all the nodes that we already saw on our way to the current node; if we went back to the node that we already passed, then you know that we created a loop (and we must skip the value or do whatever we need to do)

Answer 2

Keep a stack of all the elements leading to the root of the tree.

Each time you push the tree, scan the stack for the child. If you find a match, you will find a cycle and should skip this child. Otherwise, push the child on the stack and continue. Whenever you return to the tree, pull an item from the stack and discard.

(In the case of genealogy data, the “child” node in the tree is presumably the biological parent of the “parent” node.)

Answer 3

This is similar to the case when you can finally apply this question about interview trivia: find the loop in a linked list using only O (1) memory.

In this case, your “linked list” is a sequence of elements that you list. Use two counters, start them at half speed, and if fast speed runs to slow, then you have a cycle. It will also be O (n), not O (n ^ 2), required to check the "noticed" list. The disadvantage is that you only learn about the loop after several processed nodes several times.

In this example, I replaced the half speed method with the simpler 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 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 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); } } 

Answer 4

A very easy way to detect this is to check this restriction:

What cannot happen is that the horse appears as the father or grandfather or the great father of SELF.

Whenever you insert a node into your tree, go to the root of the tree to make sure that the horse does not exist like any parent.

To speed this up, you can associate a hash table with each node where you cache the response of such a search. Then you do not need to search all the way the next time you insert a horse under this node.

Answer 5

Your hash table solution should work if you track nodes instead of horses. Just make sure that every time you read a new horse, you create a new node, even if the value / horse matches the previous node / horse value.

Answer 6

You are dealing with an oriented acyclic graph , not a tree. There should not be any cycles, since the descendant of a horse also cannot be his ancestor.

Knowing this, you should apply code methods specific to oriented acyclic graphs.