EllisLab text mark
Advanced Search
1 of 10
1
   
MPTtree, Hieararchical trees in a database table
Posted: 11 May 2008 09:11 AM   [ # 11 ]   [ Rating: 0 ]
Joined: 2008-05-11
11 posts

Wow, talk about a fast response!  Now the error has changed to:

A PHP Error was encountered

Severity: Notice

Message: Only variable references should be returned by reference

Filename: MPTtree/MPTtree_ORM.php

Line Number: 199
A PHP Error was encountered

Severity: Notice

Message: Undefined variable: parent

Filename: controllers/wiki.php

Line Number: 48

Fatal error: Call to a member function get_all() on a non-object in /webserver/system/application/controllers/wiki.php on line 48

Do you think this could have anything to do with my version of MySQL?  Also, I neglected to mention in my previous post that I’m running the latest version of CodeIgniter.

 
Posted: 11 May 2008 09:35 AM   [ # 12 ]   [ Rating: 0 ]
Joined: 2008-05-11
11 posts

I deleted and re-entered the database in MySQL, and now it seems to be working fine.  I guess I must have typod something as I was entering it :\ :\

Anyway, thanks so much for your (extremely fast!) help and work on this code.  This is a really great plugin!

 
Posted: 16 May 2008 06:19 PM   [ # 13 ]   [ Rating: 0 ]
Avatar
Joined: 2008-03-17
64 posts

After installing MPTree in an application that uses Matchbox I get this conflict with Matchbox:

A PHP Error was encountered
Severity: Notice
Message: Undefined property: Tree_admin::$matchbox
Filename: libraries/MY_Config.php
Line Number: 81

Fatal error: Call to a member function argument() on a non-object in …/application/libraries/MY_Config.php on line 81

It would be great if this could be fixed.

Matchbox uses a library called “Loader.php” that replaces CI’s native CI_Loader with an enhanced one.
It looks like there is a loading conflict with the loading order between MPTree and Matchbox.

I tried the following fix (rather a dirty hack):
I cut the class from MY_Loader.php and pasted it into Matchbox’s Loader.php right after the CI_Loader class declaration.
Then I deleted MY_Loader.php. Works like a charme. But way too dirty to keep it that way, imho.

 
Posted: 16 May 2008 08:44 PM   [ # 14 ]   [ Rating: 0 ]
Avatar
Joined: 2008-03-17
64 posts

I myself have have written (or rather adapted) a nested tree model for CI.
I actually just turned this class to a CI model that uses CI’s native Active Record.

But unfortunately it does not have any useful editing functionality implemented.
Hence I’ll most likely have to drop it in favor of MPTree.

Nevertheless there are some features in my model wich I’d like to see in MPTree.

(bool)  isDescendantOf(…)
Would check if a given node is found in MPTree’s get_descendants()

(bool) isChildOf(…)
Would check if a given node is found in MPTree’s get_parents()

(array) getFamilyBranch(…)
Would fetch the immediately family of a node. More specifically, fetch a node’s siblings, parents, parents’ siblings, and its own direct children.

(int) getDescendantsCounts(…)
Would return MPTree’s get_descendants() with an additional field holding the node’s descendants count. (This is handy if want to print the count of descendants next to each node of a tree)

(int) getChildrenCounts(…)
Would return MPTree’s get_children() with an additional field holding the node’s children count. (This is handy if want to print the count of children next to each node of a tree)

Furthermore I’m curious why you did not add a parent_id and a nlevel field to MPTree.
Using such fields would make many of MPTree’s so more simple. Both: to understand for the user and also to maintenance.

Just take thes simple query as example:

MPTree’s approach WITHOUT a parent_id field:

function count_children($lft,$rgt){
        $result 
$this->db->query(
"SELECT COUNT(*) as num FROM
(SELECT node.*, (COUNT(parent.{
$this->id_col}) - (sub_tree.depth + 1)) AS depth
FROM {
$this->tree_table} AS node,
    {
$this->tree_table} AS parent,
    {
$this->tree_table} AS sub_parent,
    (
        SELECT node.{
$this->id_col}, (COUNT(parent.{$this->id_col}) - 1) AS depth
        FROM {
$this->tree_table} AS node,
        {
$this->tree_table} AS parent
        WHERE node.{
$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{
$this->left_col} = {$lft}
        GROUP BY node.{
$this->id_col}
        ORDER BY node.{
$this->left_col}
    )AS sub_tree
WHERE node.{
$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{
$this->left_col} BETWEEN sub_parent.{$this->left_col} AND sub_parent.{$this->right_col}
    AND sub_parent.{
$this->id_col} = sub_tree.{$this->id_col}
GROUP BY node.{
$this->id_col}
HAVING depth = 1
ORDER BY node.{
$this->left_col}) as a");
        
$result $result->row_array();
        return 
$result['num'];
    

Versus an approach WITH a parent_id field:

function count_children($lft,$rgt,$id NULL){
        
if($rgt $lft 3// leaf node, 3 here because of the possibility of a gap (4 = have children)
            
return array();
        
        
$parent_col $this->parent_col;
        if(
$id == NULL{
            $current_node 
$this->get_node($lft);
            
$id $current_node->$parent_col;
        
}
            
        $this
->db->select("COUNT({$this->id_col}) AS num",FALSE);
        
$this->db->where($this->parent_col$id);
        
$this->db->limit(1);

        
$query $this->db->get($this->table);
        
$result $query->result();
        
        
$result $result->row_array();
        return 
$result['num'];
    

Or another MPTree’s approach WITHOUT a parent_id field:

function AR_from_children_of($lft,$rgt){
        
// Circumvent the db escaping to enable a subquery
        
$this->db->ar_from[] "(SELECT node.*, (COUNT(parent.{$this->id_col}) - (sub_tree.depth + 1)) AS depth
FROM {
$this->tree_table} AS node,
    {
$this->tree_table} AS parent,
    {
$this->tree_table} AS sub_parent,
    (
        SELECT node.{
$this->id_col}, (COUNT(parent.{$this->id_col}) - 1) AS depth
        FROM {
$this->tree_table} AS node,
        {
$this->tree_table} AS parent
        WHERE node.{
$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{
$this->left_col} = {$lft}
        GROUP BY node.{
$this->id_col}
        ORDER BY node.{
$this->left_col}
    )AS sub_tree
WHERE node.{
$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{
$this->left_col} BETWEEN sub_parent.{$this->left_col} AND sub_parent.{$this->right_col}
    AND sub_parent.{
$this->id_col} = sub_tree.{$this->id_col}
GROUP BY node.{
$this->id_col}
HAVING depth = 1
ORDER BY node.{
$this->left_col}) as child";
    

Versus an approach with parent_id field:

function AR_from_children_of($lft,$rgt,$id NULL){
    
        $parent_col 
$this->parent_col;
        if(
$id == NULL{
            $current_node 
$this->get_node($lft);
            
$id $current_node->$id_col;
        
}
        
// Circumvent the db escaping to enable a subquery
        
$this->db->ar_from[] "(SELECT * FROM {$this->tree_table}
WHERE {
$this->parent_col} > $id AND {$this->left_col} > $lft AND {$this->right_col} < $rgt
ORDER BY {
$this->left_col} ASC) as descendant";
    

I highly recommend to use a parent_id field. It just makes things much easier.
And the MySQL queries should also get a significant performance boost in some cases.

 
Posted: 16 May 2008 09:07 PM   [ # 15 ]   [ Rating: 0 ]
Avatar
Joined: 2008-03-17
64 posts

And now why to add an nlevel field:

Just compare these functions for getting “A node’s descendants for up to 3 levels in depth”:

A MPTree-like approach WITHOUT an nlevel field:

function get_descendants_within_depth($lft,$rgt,$dpth){
        
if($rgt $lft 3// leaf node, 3 here because of the possibility of a gap (4 = have children)
            
return array();
            
        
$result $this->db->query(
"SELECT node.*
FROM {
$this->tree_table} AS node,
    {
$this->tree_table} AS parent,
    {
$this->tree_table} AS sub_parent,
    (
    SELECT node.{
$this->id_col}, (COUNT(parent.{$this->id_col}) - 1) AS depth
        FROM {
$this->tree_table} AS node,
            {
$this->tree_table} AS parent
        WHERE node.{
$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
            AND node.{
$this->left_col} = {$lft}
        GROUP BY node.{
$this->id_col}
        ORDER BY node.{
$this->left_col}
    )AS sub_tree
WHERE (COUNT(parent.{
$this->id_col}) - (sub_tree.depth + 1)) <= {$dpth} AND node.{$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{
$this->left_col} BETWEEN sub_parent.{$this->left_col} AND sub_parent.{$this->right_col}
    AND sub_parent.{
$this->id_col} = sub_tree.{$this->id_col}
GROUP BY node.{
$this->id_col}
HAVING depth > 0
ORDER BY node.{
$this->left_col};");
        return 
$result->num_rows() ? $result->result_array() : array();
    

Versus an approach WITH an nlevel field:

function get_descendants_within_depth($lft,$rgt,$dpth){
        
if($rgt $lft 3// leaf node, 3 here because of the possibility of a gap (4 = have children)
            
return array();
        
$level_col $this->level_col;
        
$current_node $this->get_node($lft);
        
$result $this->MPTtree->get_descendants_where($lft,$rgt,array("{$this->level_col} <=" => $current_node->$level_col $dpth));
        return 
$result;
    
 
Posted: 16 May 2008 10:01 PM   [ # 16 ]   [ Rating: 0 ]
Avatar
Joined: 2006-08-03
671 posts

How about get_parents()?
And xpath()?
And descendants()?
move and delete?

There are a lot of recursive queries there. Everything involving more than two levels next to each other would be more complicated. Plus you loose the order of the nodes and you store the same data in two places.

Some queries would be faster, but others would be a lot slower (ex. traversing the tree).

I could make a convert2adjacency_list() method, and another which does the opposite. And I’ll look at those you painted in red, but I can’t promise all of them. (I’ll also look at that with matchbox).

Thanks for the feedback!

 Signature 

RapidDataMapper: My new ORM, is now released!

IgnitedRecord: Old ORM

MPTtree: A model to handle trees in a database.

YAYParser - Yet Another YAML Parser

 
Posted: 17 May 2008 07:05 AM   [ # 17 ]   [ Rating: 0 ]
Avatar
Joined: 2008-03-17
64 posts
m4rw3r - 17 May 2008 02:01 AM

How about get_parents()?
And xpath()?
And descendants()?
move and delete?

Well, you’re right parent_id doesn’t help everywhere. But I did not ask you to get rid of nleft and nright.
I just asked you to add an additional parent_id and nlevel field to optimize certain sql queries that would be way too complex without it, imho.
get_parents() cannot get improved from how it is right now. Same for descendants(). Just keep them the way they are.
And for move & delete:
Move -> parent_id would only need to be updated once a node leaves its current parent. (nlevel would even stay the same until the node changes its parent AND level)
Delete -> the node just vanishes, so no need to update its parent_id or nlevel at all.

m4rw3r - 17 May 2008 02:01 AM

There are a lot of recursive queries there. Everything involving more than two levels next to each other would be more complicated. Plus you loose the order of the nodes and you store the same data in two places.

Some queries would be faster, but others would be a lot slower (ex. traversing the tree).

Well, as I said, take parent_id and nlevel as additional fields. Wherever parent_id or nlevel is of no help, the functions just stay the way they are right now. wink And having duplicate ID data in an additional field might be a (pretty damn small) overhead in case of memory, but it’s definitely worth it, I think.

m4rw3r - 17 May 2008 02:01 AM

I could make a convert2adjacency_list() method, and another which does the opposite.

Not sure what you mean. hmmm

m4rw3r - 17 May 2008 02:01 AM

And I’ll look at those you painted in red, but I can’t promise all of them. (I’ll also look at that with matchbox).

Thanks. smile

 
Posted: 17 May 2008 08:19 AM   [ # 18 ]   [ Rating: 0 ]
Avatar
Joined: 2006-08-03
671 posts

I could try to implement a hybrid of Modified Preorder Tree Traversal (lft and rgt) and Adjacency List (parent_id and level) (I will probably add it as an option to MPTtree).

About the getDescendantsCounts() and getChildrenCount(), should they really return an int? I believe you can use count_descendants() / count_children() otherwise, if you only need an int in return.

And the is_descendant_of() and is_child_of() I’ll probably implement in the ORM, it seems more fitting there.

Haven’t checked this with matchbox, haven’t really used matchbox before, but I’ll look into it (got some work with school, so it may take some time before I have time to do anything of those above).

 Signature 

RapidDataMapper: My new ORM, is now released!

IgnitedRecord: Old ORM

MPTtree: A model to handle trees in a database.

YAYParser - Yet Another YAML Parser

 
Posted: 17 May 2008 08:50 AM   [ # 19 ]   [ Rating: 0 ]
Avatar
Joined: 2008-03-17
64 posts
m4rw3r - 17 May 2008 12:19 PM

I could try to implement a hybrid of Modified Preorder Tree Traversal (lft and rgt) and Adjacency List (parent_id and level) (I will probably add it as an option to MPTtree).

That would be great. (else I’d have to hack it in myelf tongue wink )

m4rw3r - 17 May 2008 12:19 PM

About the getDescendantsCounts() and getChildrenCount(), should they really return an int? I believe you can use count_descendants() / count_children() otherwise, if you only need an int in return.

Well, the benefit of this method is that you do not need to run an sql query for each and every node. And having a descendants-count at hand is very handy in many situations.

m4rw3r - 17 May 2008 12:19 PM

And the is_descendant_of() and is_child_of() I’ll probably implement in the ORM, it seems more fitting there.

Right.

m4rw3r - 17 May 2008 12:19 PM

Haven’t checked this with matchbox, haven’t really used matchbox before, but I’ll look into it (got some work with school, so it may take some time before I have time to do anything of those above).

Matchbox replaces (replacing, no subclassing!) the CI_Loader with its own enhanced class. And this crashes MPTree. Dunno why, though.

 
Posted: 17 May 2008 07:32 PM   [ # 20 ]   [ Rating: 0 ]
Avatar
Joined: 2008-05-17
1073 posts

hi m4rw3r,

first of all thanks a lot for your comprehensive model!

i’ve got two questions:

i manage hierarchical pages using MPTtree, and i added a column “visible” to my table.
i am now trying to find the first VISIBLE leaf of the tree, whose parents are all VISIBLE itself.
how could i find it?

second question:
i want to echo a hierarchical menu (a <ul><li>... list) to access these pages, but in the menu should just be the pages, which are visible and whose parents are all visible.
is this possible?

thanks in advance,

peter

 
Posted: 17 May 2008 07:51 PM   [ # 21 ]   [ Rating: 0 ]
Joined: 2006-10-17
207 posts

First try to find the leaves:

select from tree where lft=rgt-

Then for each do

select from tree where visible=and lft<=$lft and rgt >=$rgt 

Then check if the lineage is correct, I don’t know a way to handle all you want in one query. This will select all visible parents. I usually store the parent_id in a column with mptt so I can derive whether a parent is missing. The other way would be to get the entire lineage of a leaf and then see with a loop in php whether all parents are visible.

I’m not sure it can be done any faster, maybe the more sql proficient know.

 
Posted: 20 May 2008 01:06 PM   [ # 22 ]   [ Rating: 0 ]
Avatar
Joined: 2007-04-16
113 posts

This looks great. Thanks for the contribution!

I wonder, is there some way of making the tree2array work nicely with CodeIgniters ol() or ul() HTML-helper?

 Signature 

EVERY TIME YOU ASK ABOUT CODEIGNITER 2.0… PHIL STURGEON KILLS A KITTEN

 
Posted: 30 May 2008 02:24 PM   [ # 23 ]   [ Rating: 0 ]
Avatar
Joined: 2006-08-03
671 posts

Ok, been busy and now I’ve noticed your question when checking all suggestions (be patient, I’ll implement some of them), so here comes the answer:

No, I’m afraid not.

You have to either convert this:

array(
    
[0] => array(
        
'id' => '1',
        
'title' => 'A name',
        
'children' => array(
            
[0] => array(
                
'id' => '2',
                
'title' => 'Another name'
            
)
        )
    )

To

array('A name' => 'Another name'); 

Or you could use something like this:

function MPTtree_ul($array){
    $str 
'<ul>';
    foreach(
$array as $data)
        
$str .= '<li>';
        
$str .= '<a href="'.$data['id'].'">'.$data['title'].'</a>'// whatever you want between the <li> </li>
        
if(isset($data['children'])){
            $str 
.= MPTtree_ul($data['children']);
        
}
        $str 
.= '</li>';
    
}
    $str 
.= '</ul>';
    return 
$str;
 Signature 

RapidDataMapper: My new ORM, is now released!

IgnitedRecord: Old ORM

MPTtree: A model to handle trees in a database.

YAYParser - Yet Another YAML Parser

 
Posted: 30 May 2008 06:12 PM   [ # 24 ]   [ Rating: 0 ]
Avatar
Joined: 2007-06-07
690 posts

Hey, I just understood the whole “MPTree” concept. I actually started implementing the same thing for the CodeExtinguisher site ( http://71.65.20.84:81/codexsite/index.php/docs/setup )

I remember you were interested in implementing this feature into CodeExtinguisher. If you still are, I’m willing to work through it with you. I haven’t actually tried MPTree yet, but it seems perfect for my use.

 Signature 

jtaby.com

 
Posted: 30 May 2008 06:57 PM   [ # 25 ]   [ Rating: 0 ]
Avatar
Joined: 2006-08-03
671 posts

I think it would be a very nice addition, both to CodeExtinguisher and MPTtree, to have a good admin interface for storing tree data in a database.

I’m going to make some other additions to MPTtree and it would be nice to make a release “with” a full admin interface, so I’ll gladly work with you.

 Signature 

RapidDataMapper: My new ORM, is now released!

IgnitedRecord: Old ORM

MPTtree: A model to handle trees in a database.

YAYParser - Yet Another YAML Parser

 
1 of 10
1