Creating a nested list based on mysql data

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
Walid
Forum Commoner
Posts: 33
Joined: Mon Mar 17, 2008 8:43 am

Creating a nested list based on mysql data

Post 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.
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Creating a nested list based on mysql data

Post 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.
Hannes2k
Forum Contributor
Posts: 102
Joined: Fri Oct 24, 2008 12:22 pm

Re: Creating a nested list based on mysql data

Post 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
?>
 
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Creating a nested list based on mysql data

Post by Eran »

You do realize that every path() call is a new mysql query..
Walid
Forum Commoner
Posts: 33
Joined: Mon Mar 17, 2008 8:43 am

Re: Creating a nested list based on mysql data

Post 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!
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Creating a nested list based on mysql data

Post 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;
 
Walid
Forum Commoner
Posts: 33
Joined: Mon Mar 17, 2008 8:43 am

Re: Creating a nested list based on mysql data

Post by Walid »

I would love to get hold of that class. Any chance?
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Creating a nested list based on mysql data

Post 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.
Walid
Forum Commoner
Posts: 33
Joined: Mon Mar 17, 2008 8:43 am

Re: Creating a nested list based on mysql data

Post by Walid »

Thanks for the help. I'll try and put something together tomorrow.
Hannes2k
Forum Contributor
Posts: 102
Joined: Fri Oct 24, 2008 12:22 pm

Re: Creating a nested list based on mysql data

Post 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.
Last edited by Hannes2k on Fri Nov 14, 2008 12:42 pm, edited 1 time in total.
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Creating a nested list based on mysql data

Post 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).
Walid
Forum Commoner
Posts: 33
Joined: Mon Mar 17, 2008 8:43 am

Re: Creating a nested list based on mysql data

Post 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.
jfer3
Forum Newbie
Posts: 1
Joined: Fri Aug 01, 2014 11:03 am

Re: Creating a nested list based on mysql data

Post 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
Post Reply