Page 1 of 1

Build Tree function using foreach pass-by-reference

Posted: Tue Jun 09, 2009 5:40 pm
by ornerybits
I want to build a tree structure from a flat array of nodes where each node contains in 'id' and a 'parent' (containing the id of the parent). The catch is I don't want to use recursion because I want to keep the algorithm complexity sub-exponential. I had an idea to do it in O(n) complexity using references, but I am thus far stumped.

I added some debug (formatted for outputting to a browser), so just try it cutting and pasting it into a test script on a development server and you'll see what I mean (hopefully).

Code: Select all

 
function build_tree($nodes) {
    $tree = array();
    foreach ($nodes as &$node) {
        if (empty($node['parent'])) {
            $tree[$node['id']] = &$node;
        } else {
            foreach($nodes as &$parent_node){
                if ($parent_node['id'] == $node['parent']){
                    if (!isset($parent_node['children'])) {
                        $parent_node['children'] = array();
                    }
                    $parent_node['children'][] =& $node;  
 
// DEBUG HERE
if ($node['id'] == 8){
echo '<br>parent node when assigning node with id 8 = ';
print_r($parent_node);
}    
// END DEBUG
 
                }   
            }   
        }
 
// DEBUG HERE
if ($node['id'] == 7){
echo '<br><br>node with id 7 = ';
print_r($node);
}    
// END DEBUG
 
    }   
    return $tree;
}
 
$nodes = array(
    array('id'=>'1'),
    array('id'=>'2', 'parent'=>'1'),
    array('id'=>'3', 'parent'=>'2'),
    array('id'=>'4', 'parent'=>'1'),
    array('id'=>'5'),
    array('id'=>'6', 'parent'=>'3'),
    array('id'=>'7'),
    array('id'=>'8', 'parent'=>'7'),
);
 
echo '<pre>';
echo 'nodes = ';
print_r($nodes);
$tree = build_tree($nodes);
echo '<br><br>tree = ';
print_r($tree);
echo '</pre>';
 
And just in case you don't want to cut and paste into a test script on a development server... here's the output...

Code: Select all

 
nodes = Array
(
    [0] => Array
        (
            [id] => 1
        )
 
    [1] => Array
        (
            [id] => 2
            [parent] => 1
        )
 
    [2] => Array
        (
            [id] => 3
            [parent] => 2
        )
 
    [3] => Array
        (
            [id] => 4
            [parent] => 1
        )
 
    [4] => Array
        (
            [id] => 5
        )
 
    [5] => Array
        (
            [id] => 6
            [parent] => 3
        )
 
    [6] => Array
        (
            [id] => 7
        )
 
    [7] => Array
        (
            [id] => 8
            [parent] => 7
        )
 
)
 
 
node with id 7 = Array
(
    [id] => 7
)
 
parent node when assigning node with id 8 = Array
(
    [id] => 7
    [children] => Array
        (
            [0] => Array
                (
                    [id] => 8
                    [parent] => 7
                )
 
        )
 
)
 
 
tree = Array
(
    [1] => Array
        (
            [id] => 1
            [children] => Array
                (
                    [0] => Array
                        (
                            [id] => 2
                            [parent] => 1
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 3
                                            [parent] => 2
                                        )
 
                                )
 
                        )
 
                    [1] => Array
                        (
                            [id] => 4
                            [parent] => 1
                        )
 
                )
 
        )
 
    [5] => Array
        (
            [id] => 5
        )
 
    [7] => Array
        (
            [id] => 7
        )
 
)
 
As you can see, it correctly builds the tree all the way down, but ONLY for the first root level node. Children of remaining root level nodes get lost somewhere. It appears that I am losing the reference assignment $parent_node['children'] after popping out of the inner foreach and attempting to assign to $tree at the beginning of the outer loop, if that makes sense. Thanks in advance.

Re: Build Tree function using foreach pass-by-reference

Posted: Tue Jun 09, 2009 8:10 pm
by requinix
Speaking of getting lost...

You need two arrays to do this. One is the tree array that has everything nested appropriately.
The second array is to know where each node is. It has the "actual" copies of everything; the tree simply builds itself with references from the lookup array.

Code: Select all

1 -> (2 -> (3, 4), 5 -> (6), 7)
$tree = array(
    1 => array(id => 1, children => array(
        2 => array(id => 2, children => array(
            3 => array(id => 3, children => array())
            4 => array(id => 4, children => array())
        )
        5 => array(id => 5, children => array(
            6 => array(id => 6, children => array())
        )
        7 => array(id => 7, children => array())
    )
);
 
$lookup = array();
$lookup[1] = root;
$tree[1] =& $lookup[1];
function addChild($parent, $addid) {
    $lookup[$addid] = array(id => $addid, children => array());
    $lookup[$parent][children][$addid] =& $lookup[$addid];
}
 
Note how the only assignment to $tree is when we set up the root. After that we deal only with $lookup - because it's easier.
You could reverse the logic if you wanted: the $tree gets the data and $lookup has a reference to a node in $tree.

astions: it's not PHP code - just looks similar.

Re: Build Tree function using foreach pass-by-reference

Posted: Wed Jun 10, 2009 10:12 am
by ornerybits
Thanks for your input, but I guess I wasn't quite clear. The idea is that $nodes is a flat array of tree nodes. For instance, if you were to store nodes in a database table and retrieve them in the following manner...

Code: Select all

 
$r = mysql_query('select id, parent from nodes');
$nodes = array();
while($node = mysql_fetch_assoc($r)){
   $nodes[] = $node;
}
 
.. .or something like that. Point being... given the $nodes array, I don't know the tree structure. That's what build_tree is for... making a tree out of a flat list of nodes.

Re: Build Tree function using foreach pass-by-reference

Posted: Wed Jun 10, 2009 12:27 pm
by mischievous
Not sure if this will help but I posted some code that works, although not as clean as I would like. Anyways it might help you out...

viewtopic.php?f=1&t=101384

Let me know... :dubious:

Re: Build Tree function using foreach pass-by-reference

Posted: Wed Jun 10, 2009 2:25 pm
by McInfo
This isn't exactly related, but it's worth a look.

Related topic: MPTT (Modified Preorder Tree Traversal)

Edit: This post was recovered from search engine cache.

Re: Build Tree function using foreach pass-by-reference

Posted: Wed Jun 10, 2009 3:14 pm
by Weirdan
ornerybits wrote:I had an idea to do it in O(n) complexity using references, but I am thus far stumped.
I think it's only possible if source array is specifically ordered, namely there's no child node coming earlier than its parent. Given that you may implement it quite simply with one 'tree' array and one flat array for node lookup, something like this:

Code: Select all

 
$nodes = array(); // flat lookup array
$tree = array(); // tree array
 
while ($node = fetch_assoc()) {
   if ($node['parent_id']) {
       if (!array_key_exists('children', $nodes[$node['parent_id']]) || !is_array($nodes[$node['parent_id']]['children'])) {
           $nodes[$node['parent_id']]['children'] = array();
       }
       $siblings =& $nodes[$node['parent_id']]['children'];
   } else { // root node
       $siblings =& $tree;
   }
   $siblings[] = $node;
   $nodes[$node['id']] =& $siblings[count($siblings) - 1];
   unset($siblings); //break reference, otherwise next iteration will destroy previous siblings in tree
}
var_dump($tree);
 

Re: Build Tree function using foreach pass-by-reference

Posted: Wed Jun 10, 2009 4:26 pm
by requinix
Weirdan wrote:I think it's only possible if source array is specifically ordered, namely there's no child node coming earlier than its parent. Given that you may implement it quite simply with one 'tree' array and one flat array for node lookup, something like this:
Even if it isn't it's still possible. Rather than simply add nodes to the tree, you check if it exists already and update if so (otherwise you add).
Then when you create the child, if the parent doesn't exist, create it first using a bare minimum amount of information.

Re: Build Tree function using foreach pass-by-reference

Posted: Wed Jun 10, 2009 5:59 pm
by ornerybits
Thank you all for your replies. I'll give some of these a shot.

I'm still curious as to where PHP is dropping the reference though (in my original post). Am I missing something obvious or is it some weird way that PHP is handling the references?

Re: Build Tree function using foreach pass-by-reference

Posted: Wed Jun 10, 2009 7:49 pm
by Weirdan
tasairis wrote:Then when you create the child, if the parent doesn't exist, create it first using a bare minimum amount of information.
And if a node has no parent (parent_id=0) then link it into the $tree array... yeah, it seems I see how that could be done. Thanks.

Re: Build Tree function using foreach pass-by-reference

Posted: Wed Jun 10, 2009 9:16 pm
by McInfo
Who knows what eval() lurks in the hearts of loops?

Code: Select all

<?php
header('Content-Type: text/plain');
 
$nodes = array
(    0 => array('title' => 'Food'     , 'parent' => null)
,    1 => array('title' => 'Fruit'    , 'parent' =>    0)
,    2 => array('title' => 'Red'      , 'parent' =>    1)
,    3 => array('title' => 'Cherry'   , 'parent' =>    2)
,    4 => array('title' => 'Yellow'   , 'parent' =>    1)
,    5 => array('title' => 'Banana'   , 'parent' =>    4)
,    6 => array('title' => 'Vegetable', 'parent' =>    0)
,    7 => array('title' => 'Meat'     , 'parent' =>    0)
,    8 => array('title' => 'Beef'     , 'parent' =>    7)
,    9 => array('title' => 'Pork'     , 'parent' =>    7)
,   10 => array('title' => 'Fresh'    , 'parent' =>    5)
,   11 => array('title' => 'Rotten'   , 'parent' =>    5)
,   12 => array('title' => 'Molding'  , 'parent' =>   11)
,   13 => array('title' => 'Clothes'  , 'parent' => null)
,   14 => array('title' => 'Cheap'    , 'parent' =>   13)
,   15 => array('title' => 'Expensive', 'parent' =>   13)
);
echo 'nodes = '; print_r($nodes);
 
$tree = array();
$backtrace = array();
$loops = 0;
while ($loops < 2 && count($nodes) > 0) {
    $remaining = array();
    foreach ($nodes as $n => $node) {
        if (is_null($node['parent'])) {
            $tree[$n] = array('title' => $node['title']);
            $backtrace[$n] = array($n);
        } elseif (array_key_exists($node['parent'], $backtrace)) {
            eval("\$tree[".implode('][', $backtrace[$node['parent']])."][\$n] = array('title' => \$node['title']);");
            $backtrace[$n] = $backtrace[$node['parent']];
            $backtrace[$n][] = $n;
        } else {
            $remaining[$n] = $node;
        }
    }
    $nodes = $remaining;
    $loops++;
}
echo 'tree = '; print_r($tree);
echo 'backtrace = '; print_r($backtrace);
?>
tree.png
tree.png (11.02 KiB) Viewed 1571 times
Edit: Attached improved code.

Edit: This post was recovered from search engine cache.