Yii 1.1: nestedsetbehavior

Nested set behavior for AR models
107 followers

Note: Latest release and documentation are available from extension github page.

This extension allows managing trees stored in database as nested sets. It's implemented as Active Record behavior.

Implemented by creocoder.

Resources

Documentation

Installing and configuring

First you need to configure model as follows:

public function behaviors()
{
    return array(
        'NestedSetBehavior'=>array(
            'class'=>'ext.yiiext.behaviors.trees.NestedSetBehavior',
            'leftAttribute'=>'lft',
            'rightAttribute'=>'rgt',
            'levelAttribute'=>'level',
    );
}

There is no need to validate fields specified in leftAttribute, rightAttribute, rootAttribute and levelAttribute options. Moreover, there could be problems if there are validation rules for these. Please check if there are no rules for fields mentioned in model's rules() method.

In case of storing a single tree per database, DB structure can be built with extensions/yiiext/behaviors/trees/schema.sql. If you're going to store multiple trees you'll need extensions/yiiext/behaviors/trees/schema_many_roots.sql.

By default leftAttribute, rightAttribute and levelAttribute values are matching filed names in default DB schemas so you can skip configuring these.

There are two ways this behavior can work: one tree per table and multiple trees per table. The mode is selected based on the value of hasManyRoots option that is false by default meaning single tree mode. In multiple trees mode you can set rootAttribute option to match existing filed in the table storing the tree.

Selecting from a tree

In the following we'll use an example model Category with the following in its DB:

- 1. Mobile phones
    - 2. iPhone
    - 3. Samsung
        - 4. X100
        - 5. C200
        - 6. Motorola
- 7. Cars
    - 8. Audi
    - 9. Ford
    - 10. Mercedes

In this example we have two trees. Tree roots are ones with ID=1 and ID=7.

Getting all roots

Using NestedSetBehavior::roots():

$roots=Category::model()->roots()->findAll();

Result:

Array of Active Record objects corresponding to Mobile phones and Cars nodes.

Getting all descendants of a node

Using NestedSetBehavior::descendants():

$category=Category::model()->findByPk(1);
$descendants=$category->descendants()->findAll();

Result:

Array of Active Record objects corresponding to iPhone, Samsung, X100, C200 and Motorola.

Getting all children of a node

Using NestedSetBehavior::children():

$category=Category::model()->findByPk(1);
$descendants=$category->children()->findAll();

Result:

Array of Active Record objects corresponding to iPhone, Samsung and Motorola.

Getting all ancestors of a node

Using NestedSetBehavior::ancestors():

$category=Category::model()->findByPk(5);
$descendants=$category->ancestors()->findAll();

Result:

Array of Active Record objects corresponding to Samsung and Mobile phones.

Getting parent of a node

Using NestedSetBehavior::getParent():

$category=Category::model()->findByPk(9);
$parent=$category->parent;

Result:

Array of Active Record objects corresponding to Cars.

Getting node siblings

Using NestedSetBehavior::getPrevSibling() or NestedSetBehavior::getNextSibling():

$category=Category::model()->findByPk(9);
$nextSibling=$category->nextSibling;

Result:

Array of Active Record objects corresponding to Mercedes.

Getting the whole tree

You can get the whole tree using standard AR methods like the following.

For single tree per table:

Category::model()->findAll(array('order'=>'lft'));

For multiple trees per table:

Category::model()->findAll(array('condition'=>'root_id=?','order'=>'lft'),array($root_id));

Modifying a tree

In this section we'll build a tree like the one used in the previous section.

Creating root nodes

You can create a root node using NestedSetBehavior::saveNode(). In a single tree per table mode you can create only one root node. If you'll attempt to create more there will be CException thrown.

$root=new Root;
$root->title='Mobile Phones';
$root->saveNode();
$root=new Root;
$root->title='Cars';
$root->saveNode();

Result:

- 1. Mobile Phones
- 2. Cars

Adding child nodes

There are multiple methods allowing you adding child nodes. To get more info about these refer to API. Let's use these to add nodes to the tree we have:

$category1=new Category;
$category1->title='Ford';
$category2=new Category;
$category2->title='Mercedes';
$category3=new Category;
$category3->title='Audi';
$root=Category::model()->findByPk(1);
$category1->appendTo($root);
$category2->insertAfter($category1);
$category3->insertBefore($category1);

Result:

- 1. Mobile phones
    - 3. Audi
    - 4. Ford
    - 5. Mercedes
- 2. Cars

Logically the tree above doesn't looks correct. We'll fix it later.

$category1=new Category;
$category1->title='Samsung';
$category2=new Category;
$category2->title='Motorola';
$category3=new Category;
$category3->title='iPhone';
$root=Category::model()->findByPk(2);
$category1->appendTo($root);
$category2->insertAfter($category1);
$category3->prependTo($root);

Result:

- 1. Mobile phones
    - 3. Audi
    - 4. Ford
    - 5. Mercedes
- 2. Cars
    - 6. iPhone
    - 7. Samsung
    - 8. Motorola
$category1=new Category;
$category1->title='X100';
$category2=new Category;
$category2->title='C200';
$node=Category::model()->findByPk(3);
$category1->appendTo($node);
$category2->prependTo($node);

Result:

- 1. Mobile phones
    - 3. Audi
        - 9. С200
        - 10. X100
    - 4. Ford
    - 5. Mercedes
- 2. Cars
    - 6. iPhone
    - 7. Samsung
    - 8. Motorola

Modifying a tree

In this section we'll finally make our tree logical.

Tree modification methods

There are several methods allowing you to modify a tree. To get more info about these refer to API.

Let's start:

// move phones to the proper place
$x100=Category::model()->findByPk(10);
$c200=Category::model()->findByPk(9);
$samsung=Category::model()->findByPk(7);
$x100->moveAsFirst($samsung);
$c200->moveBefore($x100);
// now move all Samsung phones branch
$mobile_phones=Category::model()->findByPk(1);
$samsung->moveAsFirst($mobile_phones);
// move the rest of phone models
$iphone=Category::model()->findByPk(6);
$iphone->moveAsFirst($mobile_phones);
$motorola=Category::model()->findByPk(8);
$motorola->moveAfter($samsung);
// move car models to appropriate place
$cars=Category::model()->findByPk(2);
$audi=Category::model()->findByPk(3);
$ford=Category::model()->findByPk(4);
$mercedes=Category::model()->findByPk(5);
 
foreach(array($audi,$ford,$mercedes) as $category)
    $category->moveAsLast($cars);

Result:

- 1. Mobile phones
    - 6. iPhone
    - 7. Samsung
        - 10. X100
        - 9. С200
    - 8. Motorola
- 2. Cars
    - 3. Audi
    - 4. Ford
    - 5. Mercedes

Moving a node making it a new root

There is a special moveAsRoot() method that allows moving a node and making it a new root. All descendants are moved as well in this case.

Example:

$node=Category::model()->findByPk(10);
$node->moveAsRoot();

Identifying node type

There are three methods to get node type: isRoot(), isLeaf(), isDescendantOf().

Example:

$root=Category::model()->findByPk(1);
CVarDumper::dump($root->isRoot()); //true;
CVarDumper::dump($root->isLeaf()); //false;
$node=Category::model()->findByPk(9);
CVarDumper::dump($node->isDescendantOf($root)); //true;
CVarDumper::dump($node->isRoot()); //false;
CVarDumper::dump($root->isLeaf()); //true;
$samsung=Category::model()->findByPk(7);
CVarDumper::dump($node->isDescendantOf($samsung)); //true;

Useful code

Non-recursive tree traversal

$level=0;
 
foreach($categories as $n=>$category)
{
    if($category->level==$level)
        echo CHtml::closeTag('li')."\n";
    else if($category->level>$level)
        echo CHtml::openTag('ul')."\n";
    else
    {
        echo CHtml::closeTag('li')."\n";
 
        for($i=$level-$model->level;$i;$i--)
        {
            echo CHtml::closeTag('ul')."\n";
            echo CHtml::closeTag('li')."\n";
        }
    }
 
    echo CHtml::openTag('li');
    echo CHtml::encode($category->title);
    $level=$category->level;
}
 
for($i=$level;$i;$i--)
{
    echo CHtml::closeTag('li')."\n";
    echo CHtml::closeTag('ul')."\n";
}

Change Log

1.05

  • External transaction support for NestedSetBehavior::delete() method (creocoder)

1.04

  • Fix for $depth parameter of NestedSetBehavior::ancestors() method (creocoder)

1.03

  • Class renamed to NestedSetBehavior (creocoder)
  • Rare bug with cache correction after NestedSetBehavior::addNode() fixed (creocoder)
  • Readmes non-recursive tree traversal algorithm fix (creocoder)

1.02

  • Added moveAsRoot() method (creocoder)
  • Updated readmes (Sam Dark)

1.01

  • Added not integer pk support (creocoder)
  • Remove final from class (creocoder)

1.00

  • Some behavior refactoring before release (creocoder)
  • Advanced doc added (creocoder)

0.99b

  • Allow to use multiply change tree operations (creocoder)
  • Method saveNode() now create root in "single root mode" (creocoder)
  • Unit tests refactored (creocoder)
  • Some behavior refactoring (creocoder)

0.99

  • Added note about removing fields from rules (Sam Dark)
  • Added Unit tests for single root mode (creocoder)
  • All attributes are now correctly quoted (creocoder)
  • Renamed fields: 'root'=>'rootAttribute', 'left'=>'leftAttribute', 'right'=>'rightAttribute', 'level'=>'levelAttribute' (creocoder)
  • Renamed method parent() => getParent() (creocoder)

0.95

  • Unit tests added (creocoder)
  • Incorrect usage of save() and delete() instead of behavior's saveNode() and deleteNode() is now detected (creocoder)

0.90

  • Moving a node to a different root is now supported (creocoder)

0.85

  • Initial public release (creocoder)

Total 20 comments

#17952 report it
cheng.li at 2014/08/15 11:01am
Root node sorting support In many root mode

I add some code based to the nestedsetbehavior version at https://gist.github.com/max107/10723289. And now, it support root node sorting.

Move node 7 before node 1, move node 2 before node 1 (see to the first example tree mentioned before). (Here I want to post an example tree, but the final display format is crashed. )

#17159 report it
taggert at 2014/05/08 08:32am
Movement of Multiple-Roots

I don't know if I'm doing something wrong, but it seems that movement (ordering) Root Nodes is not possible? (when multiple Roots are enabled?)

Would be nice if things like:

$rootNode=NestedCategory::model()->findByPk(1); 
$nextRootNode=$rootNode->next()->find();
$rootNode->moveAfter($nextRootNode);

Would support multiple Roots. Any tips how to do that? Or is it somehow possible to use a single-root and make that root "invisible"? ...

#15040 report it
Sergiy_Voitovuch at 2013/10/01 04:36am
Non-recursive tree traversal (in this example is a bug that incorrectly displays the tree)
$level=0;
 
foreach($categories as $n=>$category)
{
    if($category->level==$level)
        echo CHtml::closeTag('li')."\n";
    else if($category->level>$level)
        echo CHtml::openTag('ul')."\n";
    else
    {
        echo CHtml::closeTag('li')."\n";
 
        //you write for($i=$level-$model->level;$i;$i--) but we don't have $model, we have $category
        for($i=$level-$category->level;$i;$i--)
        {
            echo CHtml::closeTag('ul')."\n";
            echo CHtml::closeTag('li')."\n";
        }
    }
 
    echo CHtml::openTag('li',array('data-level'=>$category->level));
    echo CHtml::encode($category->title);
    $level=$category->level;
}
 
for($i=$level;$i;$i--)
{
    echo CHtml::closeTag('li')."\n";
    echo CHtml::closeTag('ul')."\n";
}

Please correct this in the example, because many do not read the comments but simply copies the code that displays the tree is not correctly!

#14954 report it
Ferry Lukito at 2013/09/24 05:53am
nested set

@andrew1 really thanks for explanation

before, i never heard about tree algorithm such as nested set, adjacency list, closure table
overall awesome for this extension.

thanks.

#14949 report it
andrew1 at 2013/09/24 12:34am
left and right attribute

@Lukito This isn't my extension but I do use it so maybe I can help.

It looks from your question that you might perhaps be confusing the nested set model with another tree model - perhaps adjacency list - though not sure where position fits in adjacency list?

I suggest googling nested sets. Nested set models need a left and right attribute - otherwise it wouldn't be a nested set - and without checking am guessing the variable names you named probably relate to the naming of these attributes within the database table used to store the tree - i.e. guessing extension author is providing convenient way to allow you to name those attributes in the database however suits.

Once you have set up your table this extension handles the display and manipulation of the tree fantastically and if you need the ability to graphically display and re-order items then it is awesome. I haven't seen a yii extension for doing this with the adjacency list model - though haven't looked for a while. Nested sets are clever - though not as clever as a closure table - and are superior to adjacency lists for some applications by avoiding the necessity for recursive procedures e.g. to obtain a list of grandchildren for example is only one query - effectively selecting the elements between left and right at the desired level (for grandchildren second level down). To achieve that with adjacency list would first require to select elements having a parent_id of the grandparent and then iterating over these children similarly looking for their descendants.

#14948 report it
Ferry Lukito at 2013/09/23 10:18pm
leftAttribute, rightAttribute, Level for what ?

i'am confused what is purpose of leftAttribute, rightAttribute, and LevelAttribute

would not these scheme below already cover it all.
- id
- parent_id
- name
- position

#11023 report it
datevid at 2012/12/10 10:25pm
La documentacion está muy pobre

debido a que no tenemos demasiada informacion aqui, es necesario ver el código directamente, pues es el lugar donde mencionan los parametros adicionales al momento de crear nodos sin realizar la validación. here

$root = new Menu();
// $rolft = 1;
// $root->rgt = 2;
// $root->level = 1;
$root->text = 'root';
 
$root->saveNode( false );

and

$help = new Menu();
    $help->text = 'Help';
    $help->enabled = true;
    $appended = $help->appendTo( $root, false );
#10514 report it
__construct() at 2012/11/01 01:33pm
Wrong data structure visualization in this example

Just look closer to the "Selecting from tree" section and "Getting all children of a node" example.

Example data structure:

- 2. iPhone
    - 3. Samsung
        - 4. X100
        - 5. C200
        - 6. Motorola

but CORRECT example data structure shoud be:

- 2. iPhone
    - 3. Samsung
        - 4. X100
        - 5. C200
    - 6. Motorola

Please fix the extension description and the readme file on github.

BTW - this is a great extension anyway - thank you!

#9884 report it
CNGOD at 2012/09/19 04:18am
Recursive traversal how to do?

Can you give a recursive traversal of useful code?

#9620 report it
julianm at 2012/08/29 12:34pm
JOIN with Categories

Great extension. I got it work! But I have a question:

If I have a tbl_presentation and categories extension configured for these presentations. How can I get all the the categories (roots for example) for those presentations that have certain condition? (ie: tbl_presentation.status = 'active') ?

#8995 report it
CeBe at 2012/07/11 07:35pm
github page is fixed

@andrew1 just fixed the error.

#8994 report it
andrew1 at 2012/07/11 06:44pm
Can't access on github

Would love to be able to use this extension but can't access it on the link provided to github.

Getting Fatal error: Cannot use object of type stdClass as array in /var/lib/jenkins/workspace/yiiext.github.com/app/components/YiiextGithubApi.php on line 72

#7747 report it
Cstdenis at 2012/04/14 06:22am
Looks useful

Could benefit from using of Postgresql's ltree data type where available: http://www.postgresql.org/docs/9.1/static/ltree.html

#7641 report it
br0sk at 2012/04/04 07:26am
Memory problem when using a large number of models instances

The Problem

I have noticed a bit of a problem with it if you use it for exports or similar tasks where you are traversing through the whole database getting data and pushing it out to a file.

The extension has an internal cache stored in a static variable. This can be disastrous since this means that the memory of the model you just used will be stored in memory and because of that is not released when you loop through to the next element.

I was traversing through about 100000 items and after adding a call to a model that uses the nested set behaviour my export script started running out of memory.

I am using a call like this in a loop:

$ancestor = $this->ancestors(1)->find();

If you look in the afterFind Method in the nested set behaviour it does this:

$owner=$this->getOwner();
self::$_cached[get_class($owner)][$this->_id=self::$_c++]=$owner;

This stores the object in a static array. Quite quickly this will fill the memory up. This problem is probably only ever going to show up in the rare event of you traversing through a large number of nodes and I can see that this is the wanted behaviour in most cases.

The Solution

Make sure to destruct the model manually after you have used it. Like so:

$ancestor->__destruct();

The nested set behaviour has a destructor that removes the object from the static cache.

unset(self::$_cached[get_class($this->getOwner())][$this->_id]);

Suggestion

Add possibility to turn caching off in the behaviour.

Something like:

public function behaviors()
    {
      return array(
            'NestedSetBehavior'=>array(
                'class'=>'application.components.behaviors.trees.NestedSetBehavior',
                'leftAttribute'=>'left',
                'rightAttribute'=>'right',
                'levelAttribute'=>'level',
                'hasManyRoots'=>true,
                'cache'=>false
        ));
    }
#6778 report it
McSilvio at 2012/02/04 06:12pm
Multiple Users

Hi there, I'd like to attach a user_id field to this table and have 1 tree per user. Do you think this plugin will work in this way?

Thanks for the great work, Marco.

#6701 report it
naser at 2012/01/30 06:38am
use it with CMenu

hi, thanks for your great job is there a best solution to use it with CMenu?

#5491 report it
yiqing95 at 2011/10/16 12:54am
pagination with nestedset

when a top level root has too many children , if want to use the pagination . how to ? i noticed this method : public function descendants($depth=null, $self = false)

too many children means the tree may be too deep or too wide . both situation need consider how to apply pagination , any idea ?

#5003 report it
drumaddict at 2011/09/05 08:26am
Nested Set Behavior Administration GUI with jsTree

Hi,I have just uploaded an extension for Nested Set Behavior Administration with jsTree plugin.This is the Link: Nested Set Behavior Administration GUI with jsTree

#4978 report it
Spear at 2011/09/02 06:01pm
How to build a CTreeView

A very useful extension, thank you so much for sharing! Could you please help me get this clear — how exactly can I display the whole tree via CTreeView widget? What is the right way to get the whole tree, when three has many roots?

#4678 report it
yiqing95 at 2011/08/03 02:18pm
glad to see the example about how to use this fantastic extension.

the usage example is very helpful , also we can check it out from svn , in the unit test directory one can find more usage!

how about developing an extension that bridge the nestedset model and the adjacency model , we can translate one model easily to another . there are some code pieces in the internet converting the nestedset to adjacency model . you need create both table and config the mapping for two table fields( because some table may be exist earlier and may have different field name ) ,often converting take place in midnight ,it will cost a lot of time .

Leave a comment

Please to leave your comment.

Create extension
Downloads
No downloadable files yet