EllisLab text mark
Advanced Search
1 of 3
1
   
Nested Set library (aka MPTT, aka Hierarchy DB Trees)
Posted: 01 October 2008 02:58 AM
Avatar
Joined: 2007-08-03
62 posts

Hey everyone. Last year I found Thunder’s Nested Set class, implemented as a model.
Thunder’s original class was great, but there were a few things I felt were lacking.

Thunder’s Nested Set thread

Some basic info before proceeding:
- This class implements Joe Celko’s Nested Set data model, also known as MPTT or Modified Preorder Tree Traversal.
- Nested Sets are great for storing hierarchical data in a database.
- This data model is a better alternative to the Adjacency List model.

Changes:

* Now implemented as a Library as opposed to Model (but could easily be converted back if needed)
* PHP 4 support dropped
* CI db class & active record used as extensively as possible, replacing ALL manual SQL queries
* Table prefixes now supported
* Code cleanup (i.e. - single quotes now replace double quotes when possible)
* Added support for a “parent” column (i.e. - parent_id), enables a DBA to easily
  see which child values belong to which parent values, gives ability to speedily
  request immediate children only, etc. (plans in the future to expand on this)
* Multiple root nodes now supported. The original class assumed only 1 root node
  existed in a table, now multiple roots can exist (or you can view the table itself
  as the root node, with multiple direct children allowed)

Attempts were made to keep this class compatible with Thunder’s original class,
and it is compatible in almost every way, EXCEPT for the following:

- getRoot no longer exists, now getRootNodes is required, which returns an array of nodes
- parent column is now expected to exist, default name is “parent_id”, type should be integer

The library is attached to this post.

Example DB structure:

CREATE TABLE `nested_set_tree` (
  `
idint(10unsigned NOT NULL auto_increment,
  `
lftint(10unsigned NOT NULL default '0',
  `
rgtint(10unsigned NOT NULL default '0',
  `
parent_idint(10unsigned NOT NULL default '0',
  
PRIMARY KEY  (`id`),
  
KEY `lft` (`lft`),
  
KEY `rgt` (`rgt`),
  
KEY `parent_id` (`parent_id`)
ENGINE=MyISAM

Example basic PHP usage:

<?php
class Example {
    
public function __construct() {
        
        $this
->load->library('nested_set');
        
        
# If you are using nested_set in multiple locations, it's best to create a new instance
        
        # Using original instance
        
$this->nested_set->setControlParams('nested_set_tree');
        
        
# Using new instance
        
$this->new_nested_set = new Nested_set();
        
$this->new_nested_set->setControlParams('nested_set_tree2');
        
        
# Alternatively, you can use the original $this->nested_set for multiple tables, 
        # but you must call setControlParams before each separate table use
         
        
$this->nested_set->setControlParams('nested_set_tree');
        
$root_nodes1 $this->nested_set->getRootNodes();
         
        
$this->nested_set->setControlParams('nested_set_tree2');
        
$root_nodes2 $this->nested_set->getRootNodes();
       
    
}
}
?> 

I already have this class in use with Backend Pro. Had to modify Backend Pro of course, and also modified KHACL to use this class (as KHACL stores it’s data using nested sets, but was managing the data itself, instead of using a dedicated class).
Works great so far.

Let me know if you have any questions/comments.

 Signature 

PHP Site Solutions | Nested Set library for CI

 
Posted: 04 November 2008 01:10 PM   [ # 1 ]   [ Rating: 0 ]
Avatar
Joined: 2008-09-14
24 posts

hello,

Have you updated this for 1.6/7?


anton

 Signature 

” ...the announcement of a vast project is always its betrayal” - Bataille

 
Posted: 10 November 2008 08:22 AM   [ # 2 ]   [ Rating: 0 ]
Avatar
Joined: 2007-04-16
113 posts

There is a error at line 605:

public function getTreeNext($tree_handle

should be:

public function getTreeNext(&$tree_handle


...anyways, its seems to work well under 1.6/1.7.


There could probably be made some improvements. Additional helpers/methods.:

- Rendering out ol/ul of entire tree and/or sub-tree.
- Rendering out other types of important navigation elements, with easy steps. Ex. bredcrumbs etc.

 Signature 

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

 
Posted: 10 November 2008 09:00 AM   [ # 3 ]   [ Rating: 0 ]
Avatar
Joined: 2007-04-16
113 posts

Though.. the AR-statements should be updated, since some of them are deprecated.

 Signature 

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

 
Posted: 10 November 2008 09:21 AM   [ # 4 ]   [ Rating: 0 ]
Avatar
Joined: 2007-04-16
113 posts

There is also an error in function/method getSubTreeAsHTML, somewhere around line 691.

if(isset($nodes[0]) && !is_array($nodes[0])) {
            $nodes 
= array($nodes);
        

Should be:

if(isset($nodes[0]) && !is_array($nodes[0])) {
            $nodes 
= array($this->getNodeFromId($nodes));
        
 Signature 

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

 
Posted: 10 November 2008 10:03 AM   [ # 5 ]   [ Rating: 0 ]
Avatar
Joined: 2007-04-16
113 posts

Actually.. here is quite a few errors, If im not mistaken.

 Signature 

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

 
Posted: 10 February 2009 06:17 PM   [ # 6 ]   [ Rating: 0 ]
Joined: 2009-02-10
39 posts

Hi. I think this seems promising (as well as CodeIgniter itself). (Also thanks to Thunder for the first contribution)

I have one issue though: how to generate a valid unordered list/navigation menu. It’s probably similar to this:

public function getSubTreeAsHTML($nodes$fields = array()) {
        
if(isset($nodes[0]) && !is_array($nodes[0])) {
            $nodes 
= array($nodes);
        
}
    
        $retVal 
'';
    
        foreach(
$nodes AS $node{
    
            $tree_handle 
$this->getTreePreorder($node);
        
            while(
$this->getTreeNext($tree_handle))
            
{
                
// print indentation
                
$retVal .= (str_repeat('&nbsp;'$this->getTreeLevel($tree_handle)*4));

                
// print requested fields
                
$field reset($fields);
                while(
$field){
                    $retVal 
.= $tree_handle['row'][$field] "\n";
                    
$field next($fields);
                
}
                $retVal 
.= "<br />\n";

            
}
        }

        
return $retVal;
    

But other than that, I’m confused, so I would really appreciate any help!

Thanks,

Asylmottaket

 Signature 

I’m Luke Skywalker. I’m here to rescue you.

 
Posted: 13 February 2009 12:08 PM   [ # 7 ]   [ Rating: 0 ]
Avatar
Joined: 2007-08-03
62 posts

I’m working with this class outside of CI, and I’m cleaning up any issues I find as I go along.
I’ll be posting back an updated version in a week or so.

Cheers

 Signature 

PHP Site Solutions | Nested Set library for CI

 
Posted: 26 June 2009 04:05 PM   [ # 8 ]   [ Rating: 0 ]
Joined: 2007-06-05
10 posts

Hello Jon,
I was wondering if you had made any additional progress with this?


Regards,
Todd M. Kimball

 
Posted: 02 October 2009 10:35 AM   [ # 9 ]   [ Rating: 0 ]
Joined: 2009-09-24
13 posts

Why did you convert it to a library? I think a model is much easier, or not? I mean, if I create a model for nested categories,

class Cat extends Model 
, I tend to copy many methods of the nested set library that use the (same) methods in the library. E.g. concerning creation and moving of nodes. If the nested set library was actually a model, I could do
class Cat extends Nested_Set 

, and I get many admin methods “for free”. I don’t see benefits of library, why did you make that choice?

 
Posted: 02 October 2009 12:46 PM   [ # 10 ]   [ Rating: 0 ]
Avatar
Joined: 2007-04-16
113 posts

Hi Dirkpostma.

I have been thinking about the same thing, to switch it back to a model.

And add some extra query methods, also serve along a extension class to deal with recursion and general generation of navigation lists, dropdowns, breadcrumbs etc. Here I have already started.

I think this library is a good place to start.. but it has to be further developed.

Would you do the honour of making it into a model again?

 Signature 

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

 
Posted: 02 October 2009 01:20 PM   [ # 11 ]   [ Rating: 0 ]
Joined: 2009-09-24
13 posts

There are also some other issues, e.g.: setNodeAsFirstChild does not check whether the target is a child of the node to move. If that’s the case, the tree is broken at the current time. I will add a method “isDescendant” to check whether this is the case and if so, either return false or first move the target node to the [node to move]‘s parent to make sure the tree won’t be broken.

Here some code I created:

/**
     * Test to determine whether a node (A) is an ancestor ([grand]*parent) of some other node (B) 
     * @param array $a The node to use as the initial focus of enquiry
   * @param array $b The node prototype to use for the comparison
     * @return boolean
     */
    
public function isAncestor($a$b{
    
// Node A is an ancestor of node B if A.lft < B.lft AND A.rgt > B.rgt
        
return (($a[$this->left_column_name]<$b[$this->left_column_name]) and ($a[$this->right_column_name]>$b[$this->right_column_name]));
    
}

    
/**
     * Test to determine whether a node (A) is a descedant ([grand]*child) of some other node (B) 
     * @param array $a The node to use as the initial focus of enquiry
   * @param array $b The node prototype to use for the comparison
     * @return boolean
     */
    
public function isDescendant($a$b{
    
// Node A is a descendant of node B if A.lft > B.lft AND A.rgt < B.rgt
        
return (($a[$this->left_column_name]>$b[$this->left_column_name]) and ($a[$this->right_column_name]<$b[$this->right_column_name]));
    

 

And, some method names are not intuitive. E.g. the code of method “getAncestor” actually performs a “getParent”. I renamed that:

/**
     * Returns the node that represents the parent of the given node
     * @param array $currNode The node to use as the initial focus of enquiry
     * @return array $resultNode the node returned
     */
    
public function getParent($currNode{
        
return $this->getNodeWhere($this->primary_key_column_name ' = "' $currNode[$this->parent_column_name] '"');
    

 


I’m not promising anything, but IF I adapt the class and is suitable for sharing, I certainly will smile

 
Posted: 02 October 2009 07:32 PM   [ # 12 ]   [ Rating: 0 ]
Avatar
Joined: 2007-04-16
113 posts

UPDATED POST

Also one thing might come in handy.. exspecially for making breadcrumbs

/**
     * Find the path of a given node
     * @param array $node The node to start with
     * @param boolean $includeSelf Wheter or not to include given node in result
     * @param boolean $returnAsArray Wheter or not to return array or unordered list
     * @return array or unordered list
     */
    
public function getPath($node$includeSelf=FALSE$returnAsArray=FALSE{
        
        
if(emtpy($node)) return FALSE;
        
        
$leftcol    =       $this->left_column_name;
        
$rightcol   =       $this->right_column_name;
        
$leftval    = (int) $node[$leftcol];
        
$rightval   = (int) $node[$rightcol];
        
        if(
$includeSelf)
        
{
            $this
->db->where($leftcol ' <= ' $leftval ' AND ' $rightcol ' >= ' $rightval);
        
}
        
else
        
{
            $this
->db->where($leftcol ' < ' $leftval ' AND ' $rightcol ' > ' $rightval);
        
}
        
        $this
->db->order_by($leftcol);
        
$query $this->db->get($this->table_name);

        if(
$query->num_rows() > 0
        
{
            
if($returnAsArray)
            
{
                
return $query->result_array();
            
}
            
else
            
{
                
return $this->buildCrumbs($query->result_array());
            
}
        }
        
        
return FALSE;
    


Also the generation of the list if not array is returned

function buildCrumbs($crumbData)
    
{
        $retVal 
'';

        
$retVal '<ul>';

        foreach (
$crumbData as $itemId)
        
{

            $retVal 
.= '<li>' anchor(
                
$itemId['id']
                
$itemId['title'],
                array(
'title' => $itemId['title'])
                );
                
            
$retVal .= '</li>';
        
}

        $retVal 
.= '</ul>';

        return 
$retVal;
    
 Signature 

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

 
Posted: 02 October 2009 07:54 PM   [ # 13 ]   [ Rating: 0 ]
Avatar
Joined: 2007-04-16
113 posts

Also getSubTree (maybe added AsList to the method name)

Could certainly be further developed….. but its a start
Maybe the list generation could have some settings for id/class names.. max depth etc.

/**
     * Renders the tree starting from given node
     * @param array $node The node to start with
     * @return string Unordered HTML list of the tree
     */
    
public function getSubTree($node{
        
        
if(empty($node)) return FALSE;
            
        
$tree_handle $this->getTreePreorder($node);
        
        
$menuData = array(
            
'items' => array(),
            
'parents' => array()
        );
        
        foreach (
$tree_handle['result_array'as $menuItem
        
{
            $menuData[
'items'][$menuItem['id']] $menuItem;
            
$menuData['parents'][$menuItem['parent_id']][] $menuItem['id'];
        
}

        
return $this->buildMenu($node['parent_id']$menuData);
    
}
    
    
function buildMenu($parentId$menuData$depth=0)
    
{
        $retVal 
'';

        if (isset(
$menuData['parents'][$parentId]))
        
{
            $retVal 
'<ul>';
    
            foreach (
$menuData['parents'][$parentId] as $itemId)
            
{
            
                $retVal 
.= '<li class="depth-'.$depth.'">' anchor(
                    
$menuData['items'][$itemId]['id']
                    
$menuData['items'][$itemId]['title'],
                    array(
'title' => $menuData['items'][$itemId]['title'])
                );

                
$retVal .= $this->buildMenu($itemId$menuData$depth+1);

                
$retVal .= '</li>';
            
}
    
            $retVal 
.= '</ul>';
        
}

        
return $retVal;
    
 Signature 

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

 
Posted: 14 October 2009 01:38 PM   [ # 14 ]   [ Rating: 0 ]
Joined: 2009-10-14
5 posts

This is a fantastic contribution / discussion.

It would be great if someone could upload a version with all the fixes in place.

Many thanks in advance.

 
Posted: 07 September 2010 07:13 AM   [ # 15 ]   [ Rating: 0 ]
Joined: 2010-09-07
5 posts

I had just spent a week programming the nested sets in CI with out finding this, now i have i’d like to ask ifthunders code is based on every thing being encapsulated by a top node so every thing lies within the hierachy.

I ask becouse i had been writting mine based on the top level being seperate nodes
eg
1-2
3-6 parent to 4-5
7-8

where i belive this cod eis based on everything laying between
eg
1
2-3
4 7 parent to 5-6
8-9
10

This is from reading through teh code i just want some one to confirm my conclusion who knows.

 
1 of 3
1