Cycles in family tree software
I am the developer of some family tree software (written in C++ and Qt). I had no problems until one of my customers mailed me a bug report. The problem is that the customer has two children with their own daughter, and, as a result, he can't use my software because of errors.
Those errors are the result of my various assertions and invariants about the family graph being processed (for example, after walking a cycle, the program states that X can't be both father and grandfather of Y).
How can I resolve those errors without removing all data assertions?
It seems you (and/or your company) have a fundamental misunderstanding of what a family tree is supposed to 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.
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. However this format contains some severe misconceptions about what a family tree really looks like.
GEDCOM has many issues, such as incompatibility with same sex relations, incest, etc... Which in real life happens more often than you'd imagine (especially when going back in time to the 1700-1800).
We have modeled our family tree to what happens in the real world: Events (for example, births, weddings, engagement, unions, deaths, adoptions, etc.). 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...)
The lack of validations gives us a more "real world", simpler and more flexible solution.
As for this specific case, I would suggest removing the assertions as they do not hold universally.
For 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.
Relax your assertions.
Not by changing the rules, which are mostly likely very helpful to 99.9% of your customers in catching mistakes in entering their data.
Instead, change it from an error "can't add relationship" to a warning with an "add anyway".
Here's the problem with family trees: they are not trees. They are directed acyclic graphs or DAGs. If I understand the principles of the biology of human reproduction correctly, there will not be any cycles.
As far as I know, even the Christians accept marriages (and thus children) between cousins, which will turn the family tree into a family DAG.
The moral of the story is: choose the right data structures.
链接地址: http://www.djcxy.com/p/40120.html上一篇: 澄清关于Ukkonen的后缀树
下一篇: 家庭树软件中的循环