RSS
 
17. Feb. 2013

CakePHP and Tree structures

17 Feb

Some of you might alread have worked with the TreeBehavior to generate nested categories or something like that. In most cases we just want to have two or three levels and some hierarchic structure using parent_id. But trees can do way more than that. At least if you also use lft and rght (which the behavior uses internally to order the tree) and MPTT (Modified Preorder Tree Traversal).

Unfortunately, a helper for tree-structered output is not a pat of the cake core. Luckily some skilled developer(s) created a very nicely working version for 1.x which I upgraded and enhanced for 2.x. It works flawlessly with any model that uses the TreeBehavior.

What for?

Navigation, Category Tree in Shop Systems, Threaded Boards with Posts or Comments, … The list where you can use models that behave like trees is endless. In my case we needed a complex category tree including “active path” feature and breadcrumbs. Also some additional magic to keep the tree in a visible “length” (to only show the revelant branches and only to a specific level).

Setup

As always with plugins, the Tools plugin needs to be copied/cloned in your APP/Plugin folder and loaded via CakePlugin::loadAll(), for example.

The core behavior can just be attached to the model itself using $actsAs = array('Tree'), as documented. The helper we include in our controller as $helpers = array('Tools.Tree');.

Your table should have “parent_id”, “lft”, “rght” fields. If you use UUIDs, make sure that “parent_id” is UUID (char36) just as your primary key. “lft”/”rght” must be integers, though. Otherwise your tree will always be invalid as those fields have nothing to do with the ids itself, but the order inside the tree.

From the documentation: “The parent field must be able to have a NULL value! It might seem to work, if you just give the top elements a parent value of zero, but reordering the tree (and possible other operations) will fail”.

Usage

TreeBehavior

I don’t want to go into the details regarding the core Tree behavior, as it is already very well explained in the documentation.

Just remember: Do not touch the lft/rght fields. They should not be in your forms or be modified from you in any way. The behavior internally sets the right values here. You just need to tell it what parent_id you want to put it under.

If you already saved some records in your tree there are usually three ways of getting the data in a way that you can output it properly:

  1. find(all) in combination with 'order' => array('lft' => 'ASC') and maybe scope/conditions
  2. find(threaded) and 'conditions' => array('id' => $id, ...) and 'order' => array('lft' => 'ASC')
  3. children($id) if you have multiple trees in your table, for example – or if you want to retrieve only a part of the tree

The last two methods will already nest your data using parent_id/children as key. The first one you can nest yourself if needed using Hash::nest() as shown below.

Note that you must set the order yourself for both find() calls. Only children() will automatically use the correct order.

Short reference of useful behavior methods:

  • getPath: return current path to this id
  • children: get all children to an id
  • removeFromTree (with true/false to remove children or moving them up)
  • moveUp
  • moveDown
  • verify: check that the tree is valid
  • recover: if not valid, try to repair the tree (with mode return/delete)

You can put two up/down icons in your index table or threaded tree list pointing to two actions up/down which then invoke the behavior’s methods. This way you can easily sort your tree using those methods from the backend. You can also use some more sophisticated ajax dynamic tree reordering using jquery plugins etc. Then you would probably use reorder() as this method can reorder multiple items at once.

The current path is needed to build a breadcrumbs list. See the chapter for breadcrumbs below for details.

Another useful method (even though it shouldn’t be in the behavior but the view scope) is generateTreeList(). We can use it to populate our select boxes. A baked edit/add form for your categories should look like this:

...
echo $this->Form->input('parent_id');
...

It is wise to allow “empty values”, though, if the element can be a root element (or if there aren’t any tree elements yet):

echo $this->Form->input('parent_id', array('empty' => true)); // or 'empty' => ' - root element - ' etc

Just pass down $parents in your action:

$spacer = '--';
$parents = $this->Category->generateTreeList($conditions, $keyPath, $valuePath, $spacer);
$this->set(compact('parents'));

TreeHelper

Way more interesting is how we can actually output the tree in a way that allows us to style it – especially the currently active path. Also how to fully customize each tree level.

The most simple use case – using the key/value (id and name usually) of the threaded array:

// in your view/element ctp 
echo $this->Tree->generate($categories, array('id' => 'my-tree'));

I will simply output a nested ul/li tree with the displayField (name) text.

We could also use helper callbacks (here a custom MyTreeOutputHelper::format() method) to adjust the nodes:

echo $this->Tree->generate($categories, array('id' => 'my-tree', 'callback' => array($this->MyTreeOutput, 'format')));

This method then can look like:

public function format($data) {
    if (empty($data['data']['Category']['visible'])) {
        return; // do not display
    }
    // append (active) for active path elements
    return $data['data']['Category']['name'] . ($data['activePathElement'] ? ' (active)' : '');
}

A more verbose example of the tree helper capabilities using elements:

$categories = Hash::nest($categories); // optional, if you used find(all) instead of find(threaded) or children()
 
$treeOptions = array('id' => 'main-navigation', 'model' => 'Category', 'element' => 'node', 'autoPath' => array($currentCategory['Category']['lft'], $currentCategory['Category']['rght']));
 
echo $this->Tree->generate($categories, $treeOptions);

And the /Elements/node.ctp, for example:

$category = $data['Category'];
if (!$category['active']) { // You can do anything here depending on the record content
    return;
}
echo $this->Html->link($category['name'], array('action' => 'find', 'category_id' => $category['id']));

Using autoPath we can make the tree leverage the lft/rght MPTT and automatically mark the current path as active. Styling it via css is then a piece of cake.

To enhance it further, you can use frontend js via jquery plugins (accordion or multi-level menu) or the quite powerful superfish script. If you want to divide your tree in a main top and a sub side navigation you can achieve that using the maxDepth option and only return and output specific levels of the tree per menu.

Tip: Take a look at the test cases for the helper for further details on the above options and its usage as well as the expected output for those.

Short reference for the more important settings:

  • ‘model’ => name of the model (key) to look for in the data array. defaults to the first model for the current controller. If set to false 2d arrays will be allowed/expected.
  • ‘alias’ => the array key to output for a simple ul (not used if element or callback is specified)
  • ‘type’ => type of output defaults to ul
  • ‘itemType => type of item output default to li
  • ‘id’ => id for top level ‘type’
  • ‘class’ => class for top level ‘type’
  • ‘element’ => path to an element to render to get node contents.
  • ‘callback’ => callback to use to get node contents. e.g. array(&$anObject, ‘methodName’) or ‘floatingMethod’
  • ‘autoPath’ => array($left, $right [$classToAdd = 'active']) if set any item in the path will have the class $classToAdd added. MPTT only.
  • ‘maxDepth’ => used to control the depth upto which to generate tree
  • ‘splitCount’ => the number of “parallel” types. defaults to null (disabled) set the splitCount, and optionally set the splitDepth to get parallel lists

And internally (on top of the above settings) in callbacks and elements the following information passed in as array (callback) or variables (element) is available:

  • ‘data’ => the data array itself
  • ‘depth’
  • ‘hasChildren’
  • ‘numberOfDirectChildren’
  • ‘numberOfTotalChildren’
  • ‘firstChild’
  • ‘lastChild’
  • ‘hasVisibleChildren’
  • ‘activePathElement’

Performance

Don’t forget to add some indexes on your tables to speed up the “reading” process. This is most likely the bottle neck of larger trees. Therefore you should add indexes for parent_id, lft and rght:

ALTER TABLE  `categories` ADD INDEX  `lft` (  `lft` );
ALTER TABLE  `categories` ADD INDEX  `rght` (  `rght` );
ALTER TABLE  `categories` ADD INDEX  `parent_id` (  `parent_id` );

Breadcrumbs

We can use the behavior’s method for this as mentioned above:

// controller
$treePath = $this->Model->getPath($currentCategoryId);
$this->set(compact('treePath'));

Now we just have to display the list and style it:

$total = count($treePath);
echo '<ul id="category-breadcrumbs" class="breadcrumbs">';
echo '<li>';
echo $this->Html->link('ALL', array('action'=>'find', 'category_id' => ''));
echo '</li>';
foreach ($treePath as $key => $treeCategory) {
    if (!$treeCategory['Category']['active']) {
        continue;
    }
    echo '<li>';
    if ($total === $key + 1) {
        echo h($treeCategory['Category']['name']);
    } else {
        echo $this->Html->link($treeCategory['Category']['name'], array('action'=>'find', 'category_id' => $treeCategory['Category']['id']));
    }
    echo '</li>';
}
echo '</ul>';
}

You will notice that the last element will not be a link anymore but a normal <li> tag. This way we can style it as the current (active) node in a different way to the other path elements.

Tip: You could also use the existing helper method addCrumb() as well as getCrumbList() of the HtmlHelper and output your breadcrumbs this way. If you don’t need any special treatment of your nodes, that is.

More experimental stuff

For very large trees like in category navigation structures with >> 100 category nodes it probably makes sense to only display the current level, and all direct siblings in the “active path”. It can also be a factor for search engines to only link the “relevant” cross-links here. I experimented with the hideUnrelated option and a custom callback or element to manually hide the elements marked as 'hide' => true.

Tip: It does need a nested structure (so make sure you use the right methods from above) and the threePath passed in as option. See the test case for details.

The following keys are then also available in callbacks/elements:

  • show => if it has to be shown as part of the active path
  • parent_show => if it is a child of an active path element and should also be visible
  • hide => if it should be hidden (tops the other two settings)

Yet undecided

I have been thinking about removing the find(all) support in favor of supporting always nested array input. This would probably make the code way shorter and easier to read and maintain. As outlined above using Hash::nest() you can always form your array this way prior to passing it into the helper. So the overhead here could be removed.

Feel free to submit any ideas, criticism or PRs (pull requests). I just recently started to seriously work with tree structured data.

CakePHP and Tree structures
6 votes, 4.33 avg. rating (87% score)
 
17 Comments

Posted by Mark in CakePHP

 

Tags: , , , ,

Leave a Reply

Tip:
If you need to post a piece of code use {code type=php}...{/code}.
Allowed types are "php", "mysql", "html", "js", "css".

Please do not escape your post (leave all ", <, > and & as they are!). If you have encoded characters and need to reverse ("decode") it, you can do that here!
 

 
  1. Luke

    February 18, 2013 at 17:13

    Nice article. I just integrated a cake tree with ajax + jquery ui so as to allow the tree nodes to be moved for a clients custom CMS . It was quite tricky! usually these trees "Sorting" are done by serializing the whole tree and sending that bakc after a move occurs (or on a Submit press). Howver the cake tree built-in methods don't have a fromSerialize() method, so I made it work with the delta facility . The core cake tree is excellent though otherwise and keeps everytthing underneath organized.

     
  2. Mark

    February 18, 2013 at 17:20

    Do you think it would be worth adding the fromSerialize() etc as core feature? Or is it too app specific and not worth being generalized?

    Maybe you want to ouline what you did and how you got this working. Might be interesting for others, as well.

     
  3. Miles Johnson

    March 26, 2013 at 23:19

    This is pretty awesome, but seems kind of odd to be a helper. Any chance to get this into the core TreeBehavior?

     
  4. Alex

    May 16, 2013 at 21:36

    Real big thnx, i spent 2 days to learn how to make catalog menu in best way, ur article helps me on 100%. Keep doing this work for all of us :)

     
  5. Candy Q. Terrell

    June 9, 2013 at 18:23

    The previous code example can be tweaked to perform a bottom-up (postorder, leaf to root) traversal. This traversal can be used to, for example, delete nodes of a subtree from bottom to top.

     
  6. Herve

    July 24, 2013 at 08:34

    Hello,

    As yo can see with the code above, on some "internal" li and ul, I need to add a class, is this possible ?

    <a href="http://www.example.com/" rel="nofollow">Contact</a>
    <a href="http://www.example.com/" rel="nofollow">Services</a>
     
    <a href="http://www.example.com/" rel="nofollow">Service 1</a>
    	<a href="http://www.example.com/" rel="nofollow">Service 1.1</a>
    	<a href="http://www.example.com/" rel="nofollow">Service 1.2</a>
     
    <a href="http://www.example.com/" rel="nofollow">Service 2</a>
    <a href="http://www.example.com/" rel="nofollow">Service 3</a>
    <a href="http://www.example.com/" rel="nofollow">Service 4</a>
    <a href="http://www.example.com/" rel="nofollow">Service 5</a>
     
    <a href="http://www.example.com/" rel="nofollow">Help</a>

    Thanks

     
  7. Mark

    July 24, 2013 at 08:40

    Everything is possible, for some special things you need the custom callback functionality then, though.

     
  8. Herve

    July 24, 2013 at 09:35

    Ok, thanks for the answer.
    For those of you with the same question, here is the solution:
    1) I used an element
    2) In this element I used this code to add a class="dropdown" on all my ul :

    $this->Tree->addTypeAttribute('class', 'dropdown');

    3) I used this other code to add a class="has-dropdown" only on LI with children :

    if (isset($numberOfTotalChildren) && $numberOfTotalChildren > 0) {
    	$this->Tree->addItemAttribute('class', 'has-dropdown');
    }

    Thanks for the help and the code !

     
  9. Christine

    September 19, 2013 at 14:54

    Not new to cakephp but new to the treehelper – thanks for this code. Just a question. Apart from just displaying the 'name' column of my table, I would also like to display some additional columns as well as some linked items (edit current item, for example). Any suggestions on how to do this? You cannot mix the ordered list with a table, for example …

     
  10. Mark

    September 19, 2013 at 22:53

    Use either callbacks or the custom element to inject anything you want into it. It can be a div or span tag including all the information you need.

     
  11. Christine

    September 22, 2013 at 16:39

    Thanks, I have only started to look at this again today – I am still stuck with styling these. I have used the element but the problem is that the nodes display still does not want to go where I want it to
    I have the scenario where I have :

    display some related table stuff to the tree

    Display the tree belonging to the stuff in the row above

    But the tree helper and node element takes the tree view completely OUT OF the table and displays it outside the table, ABOVE the table in fact.
    How can I get the tree to display where I want it to display!

     
  12. Christine

    September 22, 2013 at 17:23

    Aarrgghh…. nevermind… had an extra closing td where I wasn't supposed to have one (blush). Please ignore..

     
  13. Guillaume

    November 23, 2013 at 01:23

    Hi,

    Unfortunately I end up with this error when calling the Tree Helper :

    Notice (8): Undefined index: name [APP/View/Helper/TreeHelper.php, line 273]

    Which is : $content = $row[$alias];

    Any idea or leads ?

    Thanks

     
  14. Mark

    November 23, 2013 at 02:32

    You need to specify ‘model’ and 'alias' if they are not the default ones.

     
  15. Frog Warrior

    January 23, 2014 at 09:39

    Brilliant tutorial. Thanks for uploading this. Its just a Tree helper that I'm after, something to help with converting the array to HTML but I'll look into that tools plugin. Why not add a tree component to the Tools plugin? I've already started one myself, I can give you the code. The component I made basically returns conditions you need to select items joined to the tree table through a relational table, you just plug the category ID into it, and it will get you all the items in that category, and in all subcategories.

     
  16. Chrill

    April 23, 2014 at 15:36

    Hi,

    I have a problem with the view when i generate tree.

    He says "Invalid Tree Structure"
    What kind of structure is necessary

     
  17. Mark

    April 23, 2014 at 15:44

    Debug the helper and find out where it throws this error. Then see what the condition is that leads to it.

    Tip: The blog post above does tell you what the format should be like.. "The last two methods will already nest your data using parent_id/children as key. The first one you can nest yourself if needed using Hash::nest() as shown below"