C++ – Cycles in family tree software

assertionsccyclefamily-treegraph

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?

Best Answer

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.

Related Solutions

Jquery – Family tree design suggestions

Use the Google Visualization API, it's well documented: http://code.google.com/apis/visualization/documentation/gallery/orgchart.html#Example

Family Tree Algorithm

Update: This is not the best solution I have come up with, but I've left it because there are so many comments relating to it.

You have a set of events (birth/death), parental state (no descendants, parent, grandparent, etc) and life state (alive, dead).

I would store my data in structures with the following fields:

mother
father
generations
is_alive
may_have_living_ancestor

Sort your events by date, and then for each event take one of the following two courses of logic:

Birth:
    Create new person with a mother, father, 0 generations, who is alive and may
        have a living ancestor.
    For each parent:
        If generations increased, then recursively increase generations for
            all living ancestors whose generations increased.  While doing that,
            set the may_have_living_ancestor flag to false for anyone for whom it is
            discovered that they have no living ancestors.  (You only iterate into
            a person's ancestors if you increased their generations, and if they
            still could have living ancestors.)

Death:
    Emit the person's name and generations.
    Set their is_alive flag to false.

The worst case is O(n*n) if everyone has a lot of living ancestors. However in general you've got the sorting preprocessing step which is O(n log(n)) and then you're O(n * avg no of living ancestors) which means that the total time tends to be O(n log(n)) in most populations. (I hadn't counted the sorting prestep properly, thanks to @Alexey Kukanov for the correction.)

Best Answer

Related Solutions

Jquery – Family tree design suggestions

Family Tree Algorithm

Related Topic