Page 1 of 1
Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 9:25 am
by Walid
HI all,
Can anyone help me pull this off....
Imagine a knowledge base, for example, which contains many categories and a never-ending number of subcategories. In MySQL, we have a table called "Categories" in which each category has a CategoryID as well as a ParentCategoryID.
How could I use that information to create a tree view of all the categories?
I hope the question's clear. Many thanks in advance.
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 10:29 am
by Eran
Building a tree structure from a flat set with no other parameters than the parent ID is a non-trivial problem. I did get to work on a similar requirement to yours some time ago (I was working on emulating file folders structure in the same way), and I came up with a not very elegant solution, but it works:
Code: Select all
class TreeSet {
/**
* Build tree structure from array
*
* Reorganizes flat array into a tree like structure
*
* @param array $categories
* @return array
*/
public function buildTree($categories) {
$tree = array(0 => array());
foreach($categories as $category){
$tree[$category['id']][0] = $category['name'];
if(!is_null($category['parent_id'])){
if(!isset($tree[$category['parent_id']])){
$tree[$category['parent_id']] = array();
}
$tree[$category['parent_id']][$this -> findFreeIndex($tree[$category['parent_id']],1)] = $category['id'];
} else {
$tree[0][$this -> findFreeIndex($tree[0],1)] = $category['id'];
}
}
ksort($tree,SORT_ASC);
return $tree;
}
/**
* Determine next un-used array index
*
* @param array $array
* @param int $startInd
* @return int
*/
protected function findFreeIndex($array,$startInd = 0) {
return (isset($array[$startInd]) ? $this -> findFreeIndex($array,$startInd + 1) : $startInd);
}
}
It works by reorganizing a two dimensional array (ie, the result set of a MySQL query) into array that lists all the categories, with each being an array of subcategories ID's. The first index of every category array is the name of the category, and the first array of the entire tree lists the categories without a parent ID (ie, the main categories). It will look something like this:
Code: Select all
array(
0 => array(
1,
3
),
1 => array(
'cat1',
23,
34
),
3 => array(
'cat3',
6
),
6 => array(
'cat6'
10
),
10 => array(
'cat10'
),
23 => array(
'cat23'
),
34 => array(
'cat34'
)
);
Hope this helps.
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 10:32 am
by Hannes2k
Hi,
for this purpose you can use recursion:
Code: Select all
<?php
function path($id, $depth) {
$sql = "SELECT * FROM Categories WHERE ParentCategoryID = $id";
//...
while(...) {
path($row['id'], $depth+2);
echo str_pad($row['name'], $depth, " ", STR_PAD_LEFT);
}
}
//maybe: echo "<pre>";
path(0, 0); //if the main categories have as ParentCategoryID = 0
?>
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 10:34 am
by Eran
You do realize that every path() call is a new mysql query..
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 10:42 am
by Walid
pytrin - Thanks. But how do you turn that into a nested list, like
<ul>
<li>Category 1</li>
<li>Category 2
<ul>
<li>Category X which is a child of cateogy 2</li>
<li>Category Y which is a child of category 3
<ul>
<li>Category Z which is a child of Category Y
etc.
Hannes2k - Thanks, but you've lost me!
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 10:55 am
by Eran
You iterate recursively over the reorganized array. I had a couple more methods in the original class which looked something like this:
Code: Select all
class TreeSet {
/**
* Draw folder tree structure
*
* First step in a recursive drawing operation
*
* @param array $tree
* @return string
*/
public function drawTree($tree) {
$html = '<ul>';
foreach($tree[0] as $id){
$html .= $this -> drawBranch($id,$tree,true);
}
$html .= '</ul>';
return $html;
}
/**
* Recursively draw tree branches
*
* @param int $id
* @param array $tree
* @param boolean $isRoot
* @return string
*/
public function drawBranch($id,$tree,$isRoot = false) {
$branch = $tree[$id];
$name = $branch[0];
unset($branch[0]);
$html = '<li>' . $name;
if(count($branch) > 0){
$html .= '<ul>';
foreach($branch as $id){
$html .= $this -> drawBranch($id,$tree);
}
$html .= '</ul>';
}
$html .= '</li>';
return $html;
}
public function buildTree($tree) {...}
protected function findFreeIndex() {...}
}
Then you can run:
Code: Select all
//$result is a mysql query result on the categories table
$treeset = new TreeSet();
$html = $treeset -> drawTree($treeset -> buildTree($result));
echo $html;
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 10:56 am
by Walid
I would love to get hold of that class. Any chance?
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 11:06 am
by Eran
Well, as I said in the beginning it was for a slightly different purpose - emulating file folders with no limit on sub folders, and it has some file handling methods etc. The relevant methods I put here in the post.
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 11:17 am
by Walid
Thanks for the help. I'll try and put something together tomorrow.
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 11:27 am
by Hannes2k
Hi,
pytrin wrote:You do realize that every path() call is a new mysql query..
sure

but that's the easiest way and if you have ~20 categories this won't be any problem. You can also read the whole table and then create a tree, but, it's sometimes realy hard to realize simple data structures in php. And I even think this won't be faster.
You can speed up this by e.g. collecting the parantId first and then do one SQL statement, so you have just 1 sql statement per depth (or?). But it's a lot of work.
I recommend to read this articel, if the recursion version is to slow:
Managing Hierarchical Data in MySQL
If you change your database design, you can use the nested set model. This would be the fastest & best solution, because you just need one query to get the full tree:
Code: Select all
SELECT n.name, COUNT(*)-1 AS depth
FROM table AS n,table AS p
WHERE n.lft BETWEEN p.lft AND p.rgt
GROUP BY n.lft
ORDER BY n.lft;
But for this you have to change the table structure and the new structure of the table is a bit more complex.
Re: Creating a nested list based on mysql data
Posted: Fri Nov 14, 2008 11:36 am
by Eran
but that's the easiest way and if you have ~20 categories this won't be any problem. You can also read the whole table and then create a tree, but, it's sometimes realy hard to realize simple data structures in php. And I even think this won't be faster.
20 queries just to render a category tree is pretty much unacceptable in my opinion. And the solution isn't that hard, it's just not trivial. Regarding performance, I guess performing 20+ queries if you have only one user using the application might be comparable to sorting the array in php. But it will cripple the mysql server as both user count and category count goes up.
A nested set is a good solution for reading tree structures. However for dynamic data, it is a pain to maintain (as you can tell from the article you posted).
Re: Creating a nested list based on mysql data
Posted: Sun Nov 16, 2008 12:43 am
by Walid
Just to let you know, this is what I came up with:
Code: Select all
$Categories[] = array("Category A", 1, 0);
$Categories[] = array("Category B", 19, 1);
$Categories[] = array("Category C", 20, 19);
$Categories[] = array("Category D", 2, 1);
$Categories[] = array("Category E", 3, 1);
$Categories[] = array("Category F", 4, 3);
$Categories[] = array("Category G", 5, 4);
$Categories[] = array("Category H", 9, 4);
$Categories[] = array("Category I", 10, 3);
$Categories[] = array("Category J", 11, 3);
$Categories[] = array("Category K" , 12, 1);
$Categories[] = array("Category L", 25, 0);
$Categories[] = array("Category M", 26, 0);
//Go through each one and created arrays of children for each on
foreach($Categories as $Category)
{
list($CategoryName, $CategoryID, $ParentCategoryID) = $Category;
$Children[$ParentCategoryID][] = $CategoryID;
$CategoryNames[$CategoryID] = $CategoryName;
}
function PrintBranch($BranchID)
{
echo "\n<ul>";
foreach($GLOBALS[Children][$BranchID] as $ChildID)
{
echo "\n<li>$ChildID";
if(is_array($GLOBALS[Children][$ChildID])) PrintBranch($ChildID);
echo "\n</li>";
}
echo "\n</ul>";
}
PrintBranch(0);
Thanks for your help.
Re: Creating a nested list based on mysql data
Posted: Fri Aug 01, 2014 11:06 am
by jfer3
Hi this is a fantastic answer.
And works really well.
However I am totally lost as to how this is actually operating.
Can you provide some comments please as to how the children are being assigned and why are only the $id's displaying how do you display the $names.
Apologize in advance, still learning much of this technology.
thanking you
Joe