Build dynamic menu using Nested Sets

Question

I am trying to build a dynamic menu in my PHP CMS; the pages/categories are organized using the nested sets model.

Full tree:

root
 A
 B
  B1
   B1.1
   B1.2
  B2
   B2.1
   B2.1
 C
  C1
  C2
  C3
 D

I want to convert this result set to an unordererd list, which only displays a part of the tree. For example: If I click on B, I want to show only the following part of the list:

A
B
 B1
 B2
C
D

Next, if I click on B1 I want the to show this list:

A
B
 B1
  B1.1
  B1.2
 B2
C
D

etc.

I use the following SQL query to get all nodes from the (mysql) database:

SELECT node.id, node.lft, node.rgt, node.name, 
GROUP_CONCAT(parent.name ORDER BY parent.lft  SEPARATOR "/" ) AS path, 
(COUNT(parent.lft) - 1) AS depth 
FROM pages AS node, pages AS parent 
WHERE node.lft BETWEEN parent.lft AND parent.rgt 
AND ( parent.hidden = "no" AND node.hidden = "no")  AND parent.lft > 1 
GROUP BY node.id ORDER BY node.lft

I managed to create the full list without recursion (using the depth column), but I can't filter the menu like I have shown above; I think I need to get the parent's lft and rgt value for each node and filter out the elements using PHP. But how can I get these values in the same query?

Are there any other suggestions on how to achieve this?

Thanks in advance!

Answer 1

Would it fit in the scope of your project to just hide the unwanted elements? eg (css):

• .menu li > ul {display: none;}
• .menu li.clicked > ul {display: block;}

Then use javascript to add the class "clicked" to any <li> element that was clicked. Note that this CSS will not work in IE6.

Answer 2

Hi,

The following query will allow you to open any path (or sets of paths) by taking advantage of SQL's having clause and MySQL's group_concat function.

The following is the table definition and sample data I used:

drop table nested_set;

CREATE TABLE nested_set (
 id INT,
 name VARCHAR(20) NOT NULL,
 lft INT NOT NULL,
 rgt INT NOT NULL
);

INSERT INTO nested_set (id, name, lft, rgt) VALUES (1,'HEAD',1,28);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (2,'A',2,3);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (3,'B',4,17);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (4,'B1',5,10);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (5,'B1.1',6,7);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (6,'B1.2',8,9);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (7,'B2',11,16);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (8,'B2.1',12,13);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (9,'B2.2',14,15);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (10,'C',18,25);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (11,'C1',19,20);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (12,'C2',21,22);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (13,'C3',23,24);
INSERT INTO nested_set (id, name, lft, rgt) VALUES (14,'D',26,27);

The following query gives you the entire tree (except for the HEAD):

SELECT
  node.id
, node.lft
, node.rgt
, node.name
,  GROUP_CONCAT(parent.name ORDER BY parent.lft  SEPARATOR "/" ) AS path
,  (COUNT(parent.lft) - 1) AS depth
FROM nested_set AS node
inner join nested_set AS parent
on node.lft BETWEEN parent.lft AND parent.rgt
where parent.lft > 1
GROUP BY node.id

With an output of the following when run against the sample data:

+------+-----+-----+------+-----------+-------+
| id   | lft | rgt | name | path      | depth |
+------+-----+-----+------+-----------+-------+
|    2 |   2 |   3 | A    | A         |     0 |
|    3 |   4 |  17 | B    | B         |     0 |
|    4 |   5 |  10 | B1   | B/B1      |     1 |
|    5 |   6 |   7 | B1.1 | B/B1/B1.1 |     2 |
|    6 |   8 |   9 | B1.2 | B/B1/B1.2 |     2 |
|    7 |  11 |  16 | B2   | B/B2      |     1 |
|    8 |  12 |  13 | B2.1 | B/B2/B2.1 |     2 |
|    9 |  14 |  15 | B2.2 | B/B2/B2.2 |     2 |
|   10 |  18 |  25 | C    | C         |     0 |
|   11 |  19 |  20 | C1   | C/C1      |     1 |
|   12 |  21 |  22 | C2   | C/C2      |     1 |
|   13 |  23 |  24 | C3   | C/C3      |     1 |
|   14 |  26 |  27 | D    | D         |     0 |
+------+-----+-----+------+-----------+-------+

The following additions to the above query will give you the control you need to open the various sections:

having
depth = 0
or ('<PATH_TO_OPEN>' =  left(path, length('<PATH_TO_OPEN>'))
   and depth = length('<PATH_TO_OPEN>') - length(replace('<PATH_TO_OPEN>', '/', '')) + 1)

The having clause applies filters to the results of the group by query. The "depth = 0" part is to ensure that we always have out base menu nodes (A, B, C, and D). The next part is the part that controls which nodes are open. It compares the path of the nodes with a set path you want to open ('') to see if it matches and it also makes sure that it only opens level into the path. The entire or section with the '' logic can be duplicated and added as needed to open multiple paths as needed. Make sure that '' does not end in a trailing slash (/).

The following are some output examples to show you how you would construct queries to get the outputs you wanted:

=========Open B==========

SELECT
  node.id
, node.lft
, node.rgt
, node.name
,  GROUP_CONCAT(parent.name ORDER BY parent.lft  SEPARATOR "/" ) AS path
,  (COUNT(parent.lft) - 1) AS depth
FROM nested_set AS node
inner join nested_set AS parent
on node.lft BETWEEN parent.lft AND parent.rgt
where parent.lft > 1
GROUP BY node.id
having
depth = 0
or ('B' =  left(path, length('B'))
   and depth = length('B') - length(replace('B', '/', '')) + 1)

+------+-----+-----+------+------+-------+
| id   | lft | rgt | name | path | depth |
+------+-----+-----+------+------+-------+
|    2 |   2 |   3 | A    | A    |     0 |
|    3 |   4 |  17 | B    | B    |     0 |
|    4 |   5 |  10 | B1   | B/B1 |     1 |
|    7 |  11 |  16 | B2   | B/B2 |     1 |
|   10 |  18 |  25 | C    | C    |     0 |
|   14 |  26 |  27 | D    | D    |     0 |
+------+-----+-----+------+------+-------+

=========Open B and B/B1==========

SELECT
  node.id
, node.lft
, node.rgt
, node.name
,  GROUP_CONCAT(parent.name ORDER BY parent.lft  SEPARATOR "/" ) AS path
,  (COUNT(parent.lft) - 1) AS depth
FROM nested_set AS node
inner join nested_set AS parent
on node.lft BETWEEN parent.lft AND parent.rgt
where parent.lft > 1
GROUP BY node.id
having
depth = 0
or ('B' =  left(path, length('B'))
   and depth = length('B') - length(replace('B', '/', '')) + 1)
or ('B/B1' =  left(path, length('B/B1'))
   and depth = length('B/B1') - length(replace('B/B1', '/', '')) + 1)

+------+-----+-----+------+-----------+-------+
| id   | lft | rgt | name | path      | depth |
+------+-----+-----+------+-----------+-------+
|    2 |   2 |   3 | A    | A         |     0 |
|    3 |   4 |  17 | B    | B         |     0 |
|    4 |   5 |  10 | B1   | B/B1      |     1 |
|    5 |   6 |   7 | B1.1 | B/B1/B1.1 |     2 |
|    6 |   8 |   9 | B1.2 | B/B1/B1.2 |     2 |
|    7 |  11 |  16 | B2   | B/B2      |     1 |
|   10 |  18 |  25 | C    | C         |     0 |
|   14 |  26 |  27 | D    | D         |     0 |
+------+-----+-----+------+-----------+-------+

=========Open B and B/B1 and C==========

SELECT
  node.id
, node.lft
, node.rgt
, node.name
,  GROUP_CONCAT(parent.name ORDER BY parent.lft  SEPARATOR "/" ) AS path
,  (COUNT(parent.lft) - 1) AS depth
FROM nested_set AS node
inner join nested_set AS parent
on node.lft BETWEEN parent.lft AND parent.rgt
where parent.lft > 1
GROUP BY node.id
having
depth = 0
or ('B' =  left(path, length('B'))
   and depth = length('B') - length(replace('B', '/', '')) + 1)
or ('B/B1' =  left(path, length('B/B1'))
   and depth = length('B/B1') - length(replace('B/B1', '/', '')) + 1)
or ('C' =  left(path, length('C'))
   and depth = length('C') - length(replace('C', '/', '')) + 1)

+------+-----+-----+------+-----------+-------+
| id   | lft | rgt | name | path      | depth |
+------+-----+-----+------+-----------+-------+
|    2 |   2 |   3 | A    | A         |     0 |
|    3 |   4 |  17 | B    | B         |     0 |
|    4 |   5 |  10 | B1   | B/B1      |     1 |
|    5 |   6 |   7 | B1.1 | B/B1/B1.1 |     2 |
|    6 |   8 |   9 | B1.2 | B/B1/B1.2 |     2 |
|    7 |  11 |  16 | B2   | B/B2      |     1 |
|   10 |  18 |  25 | C    | C         |     0 |
|   11 |  19 |  20 | C1   | C/C1      |     1 |
|   12 |  21 |  22 | C2   | C/C2      |     1 |
|   13 |  23 |  24 | C3   | C/C3      |     1 |
|   14 |  26 |  27 | D    | D         |     0 |
+------+-----+-----+------+-----------+-------+

That's about it. you just keep duplicating that or section for each path you need to open.

See http://dev.mysql.com/tech-resources/articles/hierarchical-data.html in case you need general info about working with nested sets in MySQL.

Let me know if you have any questions.

HTH,

-Dipin

Answer 3

I realise this might be an old question, but as i stumbled across the same problem, i decided to give some input so others can benefit too.

-Dipins answer was the one i based my progress on, an now i think i have a solution without all the 'OR''s.

Just replace the having part with:

HAVING
  depth = 1
  OR
  '".$path."' LIKE CONCAT(SUBSTRING(path, 1, (LENGTH(path) - LENGTH(menu_node_name) -1)), '%')

$path = requested path. parent node's path that the user clicked, "A/B" for example

path = the path of the current node including the nodes name "A/B/B1" for example, which is a child for the node the user clicked.

menu-node-name = the name of the node in progress, "B1" for example.

What it does, is compares the requested path, lets say A/B/B1 With the path of the node. The path of the node needed some work tough. LIKE path-of-node % did work, but it only gave the upper level and did not give any other nodes on the same level. This version does.

WE concatenate the path_of_node with a wildcard (%) which means anything can come after it. The substring REMOVES the nodes own name and the dash, making the path_of_node actually the path of it's parent's node. So A/B/B1 becomes "A/B%" which matches to our request if we click a link to open a new subtree.

The reason i have depth = 1 is that i might have multiple menus in the same tree, and i dont want people to see something like "MENU-FOR-RICH-PEOPLE", "MENU-FOR-POOR-PEOPLE", or whatever the names are anyways. My set's top level nodes are kindof holding nodes, i exclude them from the actual result.

I hope this proves to be useful for someone, at least i looked for a solution for a few hours and then came up with it.

i think, i a few days you can confirm that this worked by looking at www.race.fi

EDIT / NOTE:

I tested some more and it seems that the ordering was faulty. Here is a quick copypaste of my query with correct ordering. There is some unneccessary stuff like locales, content, and content_localised but the key points should be clear.

SELECT
      REPEAT('-',(COUNT(MENU.par_name) - 2)) as indt,
      GROUP_CONCAT(MENU.par_name ORDER BY MENU.par_lft  SEPARATOR '/' ) AS path,
      (COUNT(MENU.par_lft) - 1) AS depth,
      MENU.*,
      MENU.content
     FROM 
     (SELECT 
       parent.menu_node_name AS par_name,
      parent.lft AS par_lft,
      node.menu_node_id,
      node.menu_node_name,
      node.content_id,
      node.node_types,
      node.node_iprop,
      node.node_aprop,
      node.node_brands,
      node.rgt,
      node.lft,
      [TPF]content_localised.content

     FROM [TPF]" . $this->nestedset_table . " AS node JOIN
     [TPF]" . $this->nestedset_table . " AS parent
     ON node.lft BETWEEN parent.lft AND parent.rgt

     JOIN [TPF]content
     ON
     node.content_id = [TPF]content.content_id
     JOIN [TPF]content_localised
     ON [TPF]content.content_id = [TPF]content_localised.content_id 

     JOIN [TPF]locales ON [TPF]content_localised.locale_id = [TPF]locales.locale_id

     ORDER BY node.rgt, FIELD(locale, '" . implode("' , '", $locales) . "', locale) ASC
     ) AS MENU

     GROUP BY MENU.menu_node_id

     HAVING
     depth = 1
     OR
     '".$path."' LIKE CONCAT(SUBSTRING(path, 1, (LENGTH(path) - LENGTH(MENU.menu_node_name) -1)), '%')
     AND
     depth > 0

     ORDER BY MENU.lft

     ";

Answer 4

A good post on how to build a nested set from ground up that a friend wrote is here; Nested Set in MySQL

Maybe it is helpful to you.