Build Tree function using foreach pass-by-reference

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
User avatar
ornerybits
Forum Newbie
Posts: 18
Joined: Thu May 14, 2009 2:08 pm
Location: Kansas

Build Tree function using foreach pass-by-reference

Post 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.
Last edited by Benjamin on Tue Jun 09, 2009 11:16 pm, edited 1 time in total.
Reason: Changed code type from text to php.
User avatar
requinix
Spammer :|
Posts: 6617
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

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

Post 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.
Last edited by requinix on Wed Jun 10, 2009 4:24 pm, edited 2 times in total.
User avatar
ornerybits
Forum Newbie
Posts: 18
Joined: Thu May 14, 2009 2:08 pm
Location: Kansas

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

Post 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.
mischievous
Forum Commoner
Posts: 71
Joined: Sun Apr 19, 2009 8:59 pm

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

Post 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:
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

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

Post 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.
Last edited by McInfo on Tue Jun 15, 2010 10:45 pm, edited 1 time in total.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

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

Post 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);
 
User avatar
requinix
Spammer :|
Posts: 6617
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

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

Post 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.
User avatar
ornerybits
Forum Newbie
Posts: 18
Joined: Thu May 14, 2009 2:08 pm
Location: Kansas

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

Post 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?
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

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

Post 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.
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

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

Post 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 1570 times
Edit: Attached improved code.

Edit: This post was recovered from search engine cache.
Attachments
t-101476-tree.zip
This is an improved version of the script. It is a little more efficient, handles irregularities in the $nodes array better, and does not destroy the $nodes array.
(922 Bytes) Downloaded 59 times
Post Reply