Hacker News Reader

Comment by slavik81 | Hacker News Reader

> I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree.

In general, a family tree is a directed acyclic graph. Branches of the tree will always join back together if you follow the history far enough.

The number of ancestors in a generation is 2^N, with N being the number of generations back you're looking. There were only 100 billion people that ever lived, so by the time you get about a thousand years back, it becomes literally impossible for all your ancestors to appear only once.

Of course, that's just an easy upper bound to make the point that becoming a graph is unavoidable. In practice, branches will come together a lot sooner than that.

View on HN

Is it always acyclic though? https://stackoverflow.com/questions/6163683/cycles-in-family...

Yes. You cannot be your own ancestor. A graph pointing from child to parent can split and merge, but never loop.

Though, you may need a cyclic directed graph for fictional family trees and time travel paradoxes.

And data entry errors...

A family tree is an overloaded term. The tree of ancestry, which describes who beget whom, sure cannot be cyclical.

The graph of civil relationships can certainly contain cycles. If the relationship in question is "is a legal parent of", for example, then adopt your parent.

The opportunities for cycles multiply if both blood and legal relationships are taken into account.

For an actual example, Woody Allen’s marriage to his adopted daughter essentially resulted in her being her own mother.

To be clear, Allen never adopted Soon-Yi Previn; she was adopted by Mia Farrow and Andre Previn before Farrow & Allen got together.

Yea, it’s also not the best example because Mia Farrow was not legally wed though Allen was in a long term relation and they had a child. So, I am not sure if it qualified as a common law marriage before their separation.

In an August 1992 interview with Time Magazine Allen said, “I am not Soon-Yi's father or stepfather”, adding, “I’ve never even lived with Mia. I've never in my entire life slept at Mia's apartment, and I never even used to go over there until my children came along seven years ago. I never had any family dinners over there. I was not a father to her adopted kids in any sense of the word.” Adding that Soon-Yi never treated him as a father figure and that he rarely spoke to her before the affair, Allen seemed to see few issues with their relationship.[196]. https://en.wikipedia.org/wiki/Woody_Allen

However, if your mapping out relationships in software without considering the timeline it looks like a circular relationship. Further, I am sure you can find cases that are actually incestuous.

So don't mix those two things, then; keep them distinct. Work to preserve the acyclic property, rather than trying to toss new concepts in.

This works only until the concepts are the reason the problem is being tackled. A family tree based only on genetic relationships is interesting to few people outside geneticists and doctors. Most people are interested in familial ties as they are culturally defined.

Reply on news.ycombinator.com