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.
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)