The real answer is, use an appropriate data structure. You will also want to take care when choosing which link to mark as weak sometimes you can figure out where the cycle should be broken by looking at birthdate information, but often you can't figure out anything because so much data is missing.Īnother mock serious answer for a silly question: There are a few other ways to detect cycles, such as sending out two iterators and seeing if they ever collide with the subset test, but I ended up using the local storage method.Īlso note that you don't need to actually sever the link, you can just change it from a normal link to a 'weak' link, which isn't followed by some of your algorithms. You can store paths as vector (MFMF, MFFFMF, etc.) which makes the comparison and storage very fast. If the new path contains the current path as a subpath, then it's a cycle, and should be broken. The correct way to do it is to start from each individual, and mark each ancestor with the path to that individual. This will sever potentially accurate relationships. The wrong way is to mark every ancestor from a given individual, and when traversing, if the person you're going to step to next is already marked, then cut the link. I did it on load.įinding true cycles in a tree can be done in a few ways.
You can do this in each individual algorithm, or on load. If you're traversing the tree, then cycles must be dealt with. However, you also do tend to get cycles that are invalid, just bad data. The case you have is certainly a degenerate case, but that type of thing happens all the time on larger trees.įor example, if you look at the 2^n ancestors you have at generation n, if there was no overlap, then you'd have more ancestors in 1000 AD than there were people alive.
Biologically speaking, descendancy is a directed acyclic graph (DAG). That will guarantee that there are no cycles, but is too strict. However, it looks like you're asserting that there is only one path between a person and one of their ancestors. I think the problem you're trying to solve is that you need to be able to walk the tree without getting in infinite loops - in other words, the tree needs to be acyclical.
So, I've done some work on family tree software. The lack of validations gives us a more "real world", simpler and more flexible solution.Īs for this specific case, I would suggest removing the assertions as they do not hold universally.įor displaying issues (that will arise) I would suggest drawing the same node as many times as needed, hinting at the duplication by lighting up all the copies on selecting one of them. We do not put any restrictions on these, except for logically impossible ones (for example, one can't be one's own parent, relations need two individuals, etc.) We have modeled our family tree to what happens in the real world: Events (for example, births, weddings, engagement, unions, deaths, adoptions, etc.). Which in real life happens more often than you'd imagine (especially when going back in time to the 1700-1800). GEDCOM has many issues, such as incompatibility with same sex relations, incest, etc. However this format contains some severe misconceptions about what a family tree really looks like. The problem, in our case, and I assume your case as well, comes from the GEDCOM format that is extremely opinionated about what a family should be. Let me clarify, I also work for a company that has (as one of its products) a family tree in its portfolio, and we have been struggling with similar problems. It seems you (and/or your company) have a fundamental misunderstanding of what a family tree is supposed to be.