This article is for people stuck using the adjacency list model to store their data hierarchies. If you're just learning about data hierarchies and want to know how to do it right, please read this article, which explains the preorder tree traversal algorithm, how to handle hierarchies at the database level, and why the adjacency list model usually sucks.
This article is about drawing trees. A tree. A single tree occupied by a family of lemurs. It's important to draw lemurs so future generations can know what they looked like, and it's important to draw trees because they're a lemur's natural habitat.
(Actually, we're going to draw a tree representing bits of the Lemurinae and Hapalemurinae families of the animal kingdom, but because it helps you visualize, we're going to think of them as asexual lemurs with funny names who all live in the same tree.)
Chances are, you learned to draw trees using functions like this one, which would loop over and over all the lemurs, talking to itself as it glued branches together. Lemurs don't like this, it makes them dizzy and induces vomiting. And trust me, you don't want to spend the rest of this article cleaning up lemur vomit. I'm going to show you an alternative tree-drawing method; one so simple, you'll claim you knew it all along and will call me condescending for having written this entire article under the assumption you didn't.
Of course, by the time you've reached this conclusion, you'll be half way through the article and will want to know how it ends.
The Data
Every tree needs its family of lemurs. Here's ours:
$family =
array( array('id' =>
'Eulemur',
'parent' =>
'Lemurinae'),
array('id' =>
'Eulemur Coronatus',
'parent' =>
'Eulemur'),
array('id' =>
'Eulemur Fulvus',
'parent' =>
'Eulemur'),
array('id' =>
'Eulemur Macaco',
'parent' =>
'Eulemur'),
array('id' =>
'Eulemur Mongoz',
'parent' =>
'Eulemur'),
array('id' =>
'Eulemur Rubriventer',
'parent' =>
'Eulemur'),
array('id' =>
'Hapalemur',
'parent' =>
'Hapalemurinae'),
array('id' =>
'Hapalemur Alaotrensis',
'parent' =>
'Hapalemur'),
array('id' =>
'Hapalemur Aureus',
'parent' =>
'Hapalemur'),
array('id' =>
'Hapalemur Griseus',
'parent' =>
'Hapalemur'),
array('id' =>
'Hapalemurinae',
'parent' =>
''),
array('id' =>
'Lemur',
'parent' =>
'Lemurinae'),
array('id' =>
'Lemur Catta',
'parent' =>
'Lemur'),
array('id' =>
'Lemurinae',
'parent' =>
''),
array('id' =>
'Prolemur',
'parent' =>
'Hapalemurinae'),
array('id' =>
'Prolemur Simus',
'parent' =>
'Prolemur'),
array('id' =>
'Varecia',
'parent' =>
'Lemurinae'),
array('id' =>
'Varecia Rubra',
'parent' =>
'Varecia'),
array('id' =>
'Varecia Variegata',
'parent' =>
'Varecia'));
Looks like a collection of mysql_fetch_arrays, right? I don't know what sort of query you've been running, though. Those lemurs are all jumbled up. It looks as though they tried to assemble in alphabetical order, but that's no good to us. Probably, this is all related to the fight that recently broke out at the family dinner table.
The lemurs have a simple, sensible housing plan: older lemurs live closer to the trunk of the tree so they have the least distance to travel down the tree to the outhouse. Their children live on branches, and their children's children on branches of those branches, and so on and so forth.
The problem came last night after supper, which was held (as usual) at the foot of their tree. With full tummies and sleepy eyes, the lemurs leaned back and looked proudly up at their tree, at its mighty magnificence. Each began to point out his home on this or that branch, and each began to correct the other, and the first insisted to the second, No, really, that's my branch,
and before long, all were in such a muddle they'd each completely forgotten where they lived.
What a mess! What an argument! To settle it, they need us to draw a map of their tree, with each lemur home marked on its branch. Because we're PHP people, we'll do it in PHP. Who knows, maybe a lemur family homepage will come out of it.
Drawing Trees That Think They're Shrubs, And Bushes That Think They're Trees, And Shrubs That Think They're Bushes That Think They're Trees
Time to roll our sleeves up and get code down our aprons. Here goes:
$tree =
array();
foreach($family as $child) { extract($child);
if(!
isset($tree[$id])) $tree[$id] =
array();
if(!
empty($parent)) { if(!
isset($tree[$parent])) $tree[$parent] =
array();
$tree[$parent][$id] = &
$tree[$id];
}}print_r($tree);
Easy! And none of that nasty recursion Gijs Van Tulder recommended.
Let's get a closer look at that foreach loop. First it examines each lemur:
foreach($family as $child) { extract($child);
And adds him to the tree if he isn't already in there:
Then, it examines the lemur's parent, and adds it to the tree if it isn't already there:
What our code does next is a magic trick, a sleight of hand I learned in my days as a pickpocketing cockney street thug. Pay close attention as it references the lemur as a child of its parent:
$tree[$parent][$id] = &$tree[$id];
}
}
If you're not sure what referencing
means, or you've never used the assignment by reference operator, I recommend you read up about it from the PHP manual. Basically, in our example, it means the parent knows where to find his son, even though said son has grown up and has a branch all of his own. What fine memories those parents have!
And there it is, in all its glory. A beautiful piece of code without a trace of schizophrenia.
But wait a minute, when we step back from the easel and view our finished work, we see that something's dreadfully wrong: some of the lemurs think they belong in multiple places at once! Our code may have a clean bill of mental health, but the poor lemurs have been driven so crazy they think they're electrons and no one's watching!
Clearly, we must refine this system.
Just One Tree
Actually, it doesn't take much effort. All we need to do is separate the parents' memories from their children. Because the parents know exactly where to point when we ask for their children, we'll store their memories in an array called pointers:
$pointers =
array();
$tree =
array();
foreach($family as $child) { extract($child);
if(!
isset($pointers[$id])) $pointers[$id] =
array();
if(!
empty($parent)) { if(!
isset($pointers[$parent])) $pointers[$parent] =
array();
$pointers[$parent][$id] = &
$pointers[$id];
} else $tree[$id] = &
$pointers[$id];
}print_r($tree);
Yup, it's almost exactly the same code, we just swapped most of the references to the tree array for the new pointers array, and stuck in an extra line at the bottom of our foreach loop which asks the great grandparents where the family tree is. It turns out they already had the whole thing memorized, and all this code has simply jogged their memories.
The result? A perfect tree map! Ah, look at those lemurs dancing happily from branch to branch, waving their windy tails and singing their lemur songs. Hooray! You saved them from a long, self-referential squabble about whose branch is whose. Good for you.
But What About...
Of course, in the real world, we very rarely handle fuzzy little lemurs. The hierarchies of today's world are frequented by rabid, demonic bunny-like nodes with all sorts of data frothing at their mouths. How does all this extra data fit into our system?
Not quite so neatly or tidily, I'll admit, but it does fit. If you don't use a dedicated class to create object nodes, you'll probably make each item an array of two arrays: one for its children (as per our tree), and one for its data. Then you simply have to make sure you populate the data nodes of each item during the foreach loop, whether or not it already exists in the pointers array.
I could give you an example, but it probably wouldn't involve lemurs and therefore doesn't interest me.
