Converting an existing structure to a tree structure

[rymonator]

Hello, I was wondering how I would convert an existing structure to a tree. What I want is basically a family tree. What I have is the following:

array (

array(id => 123, p1 => 567, p2 => 765),
array(id => 321, p1 => 567, p2 => 890),
array(id => 333, p1 => 123, p2 => null),
array(id => 444, p1 => null, p2 => null),
etc.

);

It's an array of associative arrays showing each element in the family tree as well the their parent(s). An element can have one, two, or zero parents. If they have one parent, it is ALWAYS p1. If an element has no parents, it is not necessarily the root, because if there are two parents, one parent can have no parents and the other can still have one or two. And of course, there doesn't necessarily have to have just one root.

What I ultimately want is to display the tree graphically, but I am way too dumb to be able to convert this into a tree structure. I actually saw a post on this site asking a similar question (http://bytes.com/topic/php/answers/4403 -algorithm-creating-tree-structure-linke d-list), but it only deals with one parent. It might be a simple transition to add another parent, but I'm just not grasping this very well. If anyone has any insight into this or can point me in the right direction it would be greatly appreciated.

Thanks.

[rymonator]

ok, doing some research I realize that because a child can have more than 1 parent this is not a tree, but rather a graph.

[Atli]

Family structures aren't really trees either. They are more like webs. What allows us to draw them as trees is only focusing on a single string of that web, and only drawing "related" connections, while ignoring branches that go outside that.

Meaning, in a typical family tree you see a target at the top; the root, and it's descendants. What you don't see is it's parents, or links to the extended family of external influences (mates). Drawing *all* the connections would be far to extensive to actually make sense on a simple tree.

And I am only talking here about a family, where you can be fairly certain descendants are only connected to the root via the tier above them, when in actuality there is nothing forbidding a distant descendant from connecting directly to the root, which would be near impossible to plot on a family-tree-like structure.

What you need to do is figure out which part of the structure you want to plot. What exactly do you want to see on you graph? What is the purpose of your drawing?

For example, if my array contained the following data:

array(
    array(id => 1, p1 => null, p2 => null),
    array(id => 2, p1 => 1, p2 => 100),
    array(id => 3, p1 => 1, p2 => 2),
    array(id => 4, p1 => 3, p2 => 1),
    array(id => 5, p1 => 100, p2 => 4)
)

If I were to draw this, it might look something like:

Drawing all the links, you couldn't really draw this as a normal family tree, and it would be nearly impossible to draw this as something like a file-tree (some nodes would have to appear in two categories). At least not without filtering out links that aren't needed.

If my goal was to select all direct descendants of the entry with the ID 1, I could simply ignore all links that aren't needed for that purpose. I would start at the top, listing all direct descendants and ignoring parent entries that aren't needed, and work my way down each branch. That could leave me with this:


The question is, what do you need to see? Once you figure that out you can start filtering the data to achieve that.

[rymonator]

Thanks. Basically, something that makes this a lot simpler than it could be is that I would be drawing a "tree" relative to only one node. For example, I would be going to the web page for node X, and the tree would be relative to that node. In other words, we would see the parents of X, the parent's parents, and so forth. We would also see siblings of X, and children and descendants of X. However, we would not need to see the parents of siblings (unless it is one of X's parents), and we would not need to see parents of descendants (unless they are X).