0

I have some code that creates a ancestor tree created from data files uploaded by users. But in some cases there are logical errors in these trees. Like in the picture below. The situation in the red box creates a infinite loop while creating the tree.

My question is how to detect this situation when creating a tree an break the reading. The code is just a ordinary recursive function that traverse the tree, I start with the first person, then get the parents, and so on until there are no more ancestors in the tree.

First I was thinking that I could just have a flat list with all people added and check if they already exists in the tree. But that dont work since its OK for one person to exist several times, like shown in the two green boxes. Inbreeding occures.

Is there any ways to detect a infinite loop in a tree to avoid the "red situation" in the picture? Tree with infinite loop

EDIT: Maybe this picture clarifies what I need to detect. The blue dots are the same persons, and the tree above this is by logic also the same persons as the blue tree to the side. This is a functionality that I would like to keep since it dont create a infinite loop. But if the data does like the red arrow, then it becomes a infinite loop, and this is the scenario I would like to detect, but keep the blue trees. Tree with OK scenario

  • 4
    Keep a `visited` map, check that as you traverse. If current node is in the map you have a loop, otherwise add it and continue. – 500 - Internal Server Error Nov 10 '21 at 21:52
  • This is basically the same as "detecting cycles in a linked list" - you're just using the "next step in the recursive treewalk" as your "next" pointer. – Raymond Chen Nov 10 '21 at 21:57
  • [`HashSet`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1) is a good choice as a map of visited nodes, imo. – Dmitry Nov 10 '21 at 22:00
  • I might not understand the suggestions.. But would'nt that break the reading of the tree even for the green boxes in the image? One person could exist several times in the tree, that ok and don't cause any loops (if it is like the green boxes). – Mårten Swärd Nov 10 '21 at 22:06
  • 1
    Well, if the same node can appear at different positions in a graph, you don't have a tree. Can you distinguish between the to green nodes? Yes, then you can also distinguish them in a visited map. No? How will you decide whether you already visited that node or not. Ie what makes the two green boxes allowed, but the red arrow not allowed – derpirscher Nov 10 '21 at 22:26
  • Well thats my question.. It maybe not a tree in a strict meaning, but it is a ancestor tree, with a scenario that occures in real life. But the red scenario can't happen in real life, but when the data is incorrect. I added an other image with a real ancestor tree. Maybe that clarifies what I try to detect – Mårten Swärd Nov 10 '21 at 22:40
  • 1
    You [should try to use a search engine first](https://meta.stackoverflow.com/questions/261592/how-much-research-effort-is-expected-of-stack-overflow-users) to answer this question. It will help to know the proper terminology. What you are trying to find is not an "infinite loop" (that only refers to *code*), but a *cycle*. Also, something that is *supposed to* be a tree but which might contain a cycle, is instead a "directed graph". – Karl Knechtel Nov 10 '21 at 22:41
  • Thanks! I did not know that the question was incorrect. But I hope your answer could help me to search for the right answer now that I know the term for what I need to look for – Mårten Swärd Nov 10 '21 at 22:45
  • Your main problem is, that you are representing the same person with multiple nodes in the graph. And if you cannot distinguish those nodes by any property, you don't have any possibility to detect, whether you already have visited a node or not. But if you can, a simple visited list will solve your problem. – derpirscher Nov 10 '21 at 22:47

0 Answers0