PHP/MySQL Category Hierarchy

[joebert]

October 31st, 2009, 3:05 pm

Anyone have any suggestions for stuff to read on working with categories and sub-categories with PHP and MySQL ?

Currently I use a category table like this.
I've removed fields irrelevant to category hierarchy such as "label" and "description".

MYSQL Code: [ Download ] [ Select ]

CREATE TABLE IF NOT EXISTS `categories` (
  `category_id` smallint(5) unsigned NOT NULL auto_increment,
  `parent_id` smallint(6) unsigned default NULL,
  PRIMARY KEY  (`category_id`),
  KEY `parent_id` (`parent_id`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;

1. CREATE TABLE IF NOT EXISTS `categories` (
2.   `category_id` smallint(5) unsigned NOT NULL auto_increment,
3.   `parent_id` smallint(6) unsigned default NULL,
4.   PRIMARY KEY  (`category_id`),
5.   KEY `parent_id` (`parent_id`)
6. ) ENGINE=MyISAM  DEFAULT CHARSET=utf8;

When I need to know all of the descendants of any given category, I do something like this.

PHP Code: [ Download ] [ Select ]

function lineage($branch)
{
   $decendants = array();
   foreach($branch->sub_categories as $key => $val)
   {
      $decendants[]  = $key;
      $decendants    = array_merge($decendants, lineage($val));
   }
   return $decendants;
}
 
$c = new stdClass;
$c->lineage = array();
 
$result = $db->query('SELECT category_id, parent_id FROM ' . CATEGORIES_TABLE, MYSQLI_USE_RESULT);
while($row = $result->fetch_object())
{
   $row->sub_categories = array();
   $c->lineage[$row->category_id] = $row;
}
$result->close();
foreach($c->lineage as $key => $val)
{
   if($val->parent_id)
   {
      $c->lineage[$val->parent_id]->sub_categories[$key] =& $c->lineage[$key];
   }
}
foreach($c->lineage as $key => $val)
{
   $c->lineage[$key]->decendants = lineage($val);
}

1. function lineage($branch)
2. {
3.    $decendants = array();
4.    foreach($branch->sub_categories as $key => $val)
5.    {
6.       $decendants[]  = $key;
7.       $decendants    = array_merge($decendants, lineage($val));
8.    }
9.    return $decendants;
10. }
11.  
12. $c = new stdClass;
13. $c->lineage = array();
14.  
15. $result = $db->query('SELECT category_id, parent_id FROM ' . CATEGORIES_TABLE, MYSQLI_USE_RESULT);
16. while($row = $result->fetch_object())
17. {
18.    $row->sub_categories = array();
19.    $c->lineage[$row->category_id] = $row;
20. }
21. $result->close();
22. foreach($c->lineage as $key => $val)
23. {
24.    if($val->parent_id)
25.    {
26.       $c->lineage[$val->parent_id]->sub_categories[$key] =& $c->lineage[$key];
27.    }
28. }
29. foreach($c->lineage as $key => $val)
30. {
31.    $c->lineage[$key]->decendants = lineage($val);
32. }

Which will give me something the following when I use print_r on $c->lineage.

Code: [ Download ] [ Select ]

Array
(
  [1] => stdClass Object
    (
      [category_id] => 1
      [parent_id] =>
      [sub_categories] => Array
        (
          [2] => stdClass Object
            (
              [category_id] => 2
              [parent_id] => 1
              [sub_categories] => Array
                (
                  [3] => stdClass Object
                    (
                      [category_id] => 3
                      [parent_id] => 2
                      [sub_categories] => Array
                        (
                          [4] => stdClass Object
                            (
                              [category_id] => 4
                              [parent_id] => 3
                              [sub_categories] => Array
                                (
                                  [5] => stdClass Object
                                    (
                                      [category_id] => 5
                                      [parent_id] => 4
                                      [sub_categories] => Array
                                        (
                                        )
                                      [decendants] => Array
                                        (
                                        )
                                    )
                                )
                              [decendants] => Array
                                (
                                  [0] => 5
                                )
                            )
                        )
                      [decendants] => Array
                        (
                          [0] => 4
                          [1] => 5
                        )
                    )
                )
              [decendants] => Array
                (
                  [0] => 3
                  [1] => 4
                  [2] => 5
                )
            )
        )
      [decendants] => Array
        (
          [0] => 2
          [1] => 3
          [2] => 4
          [3] => 5
        )
    )
  [2] => stdClass Object
    (
      [category_id] => 2
      [parent_id] => 1
      [sub_categories] => Array
        (
          [3] => stdClass Object
            (
              [category_id] => 3
              [parent_id] => 2
              [sub_categories] => Array
                (
                  [4] => stdClass Object
                    (
                      [category_id] => 4
                      [parent_id] => 3
                      [sub_categories] => Array
                        (
                          [5] => stdClass Object
                            (
                              [category_id] => 5
                              [parent_id] => 4
                              [sub_categories] => Array
                                (
                                )
                              [decendants] => Array
                                (
                                )
                            )
                        )
                      [decendants] => Array
                        (
                          [0] => 5
                        )
                    )
                )
              [decendants] => Array
                (
                  [0] => 4
                  [1] => 5
                )
            )
        )
      [decendants] => Array
        (
          [0] => 3
          [1] => 4
          [2] => 5
        )
    )
  [3] => stdClass Object
    (
      [category_id] => 3
      [parent_id] => 2
      [sub_categories] => Array
        (
          [4] => stdClass Object
            (
              [category_id] => 4
              [parent_id] => 3
              [sub_categories] => Array
                (
                  [5] => stdClass Object
                    (
                      [category_id] => 5
                      [parent_id] => 4
                      [sub_categories] => Array
                        (
                        )
                      [decendants] => Array
                        (
                        )
                    )
                )
              [decendants] => Array
                (
                  [0] => 5
                )
            )
        )
      [decendants] => Array
        (
          [0] => 4
          [1] => 5
        )
    )
  [4] => stdClass Object
    (
      [category_id] => 4
      [parent_id] => 3
      [sub_categories] => Array
        (
          [5] => stdClass Object
            (
              [category_id] => 5
              [parent_id] => 4
              [sub_categories] => Array
                (
                )

              [decendants] => Array
                (
                )
            )
        )
      [decendants] => Array
        (
          [0] => 5
        )
    )
  [5] => stdClass Object
    (
      [category_id] => 5
      [parent_id] => 4
      [sub_categories] => Array
        (
        )
      [decendants] => Array
        (
        )
    )
)

1. Array
2. (
3.   [1] => stdClass Object
4.     (
5.       [category_id] => 1
6.       [parent_id] =>
7.       [sub_categories] => Array
8.         (
9.           [2] => stdClass Object
10.             (
11.               [category_id] => 2
12.               [parent_id] => 1
13.               [sub_categories] => Array
14.                 (
15.                   [3] => stdClass Object
16.                     (
17.                       [category_id] => 3
18.                       [parent_id] => 2
19.                       [sub_categories] => Array
20.                         (
21.                           [4] => stdClass Object
22.                             (
23.                               [category_id] => 4
24.                               [parent_id] => 3
25.                               [sub_categories] => Array
26.                                 (
27.                                   [5] => stdClass Object
28.                                     (
29.                                       [category_id] => 5
30.                                       [parent_id] => 4
31.                                       [sub_categories] => Array
32.                                         (
33.                                         )
34.                                       [decendants] => Array
35.                                         (
36.                                         )
37.                                     )
38.                                 )
39.                               [decendants] => Array
40.                                 (
41.                                   [0] => 5
42.                                 )
43.                             )
44.                         )
45.                       [decendants] => Array
46.                         (
47.                           [0] => 4
48.                           [1] => 5
49.                         )
50.                     )
51.                 )
52.               [decendants] => Array
53.                 (
54.                   [0] => 3
55.                   [1] => 4
56.                   [2] => 5
57.                 )
58.             )
59.         )
60.       [decendants] => Array
61.         (
62.           [0] => 2
63.           [1] => 3
64.           [2] => 4
65.           [3] => 5
66.         )
67.     )
68.   [2] => stdClass Object
69.     (
70.       [category_id] => 2
71.       [parent_id] => 1
72.       [sub_categories] => Array
73.         (
74.           [3] => stdClass Object
75.             (
76.               [category_id] => 3
77.               [parent_id] => 2
78.               [sub_categories] => Array
79.                 (
80.                   [4] => stdClass Object
81.                     (
82.                       [category_id] => 4
83.                       [parent_id] => 3
84.                       [sub_categories] => Array
85.                         (
86.                           [5] => stdClass Object
87.                             (
88.                               [category_id] => 5
89.                               [parent_id] => 4
90.                               [sub_categories] => Array
91.                                 (
92.                                 )
93.                               [decendants] => Array
94.                                 (
95.                                 )
96.                             )
97.                         )
98.                       [decendants] => Array
99.                         (
100.                           [0] => 5
101.                         )
102.                     )
103.                 )
104.               [decendants] => Array
105.                 (
106.                   [0] => 4
107.                   [1] => 5
108.                 )
109.             )
110.         )
111.       [decendants] => Array
112.         (
113.           [0] => 3
114.           [1] => 4
115.           [2] => 5
116.         )
117.     )
118.   [3] => stdClass Object
119.     (
120.       [category_id] => 3
121.       [parent_id] => 2
122.       [sub_categories] => Array
123.         (
124.           [4] => stdClass Object
125.             (
126.               [category_id] => 4
127.               [parent_id] => 3
128.               [sub_categories] => Array
129.                 (
130.                   [5] => stdClass Object
131.                     (
132.                       [category_id] => 5
133.                       [parent_id] => 4
134.                       [sub_categories] => Array
135.                         (
136.                         )
137.                       [decendants] => Array
138.                         (
139.                         )
140.                     )
141.                 )
142.               [decendants] => Array
143.                 (
144.                   [0] => 5
145.                 )
146.             )
147.         )
148.       [decendants] => Array
149.         (
150.           [0] => 4
151.           [1] => 5
152.         )
153.     )
154.   [4] => stdClass Object
155.     (
156.       [category_id] => 4
157.       [parent_id] => 3
158.       [sub_categories] => Array
159.         (
160.           [5] => stdClass Object
161.             (
162.               [category_id] => 5
163.               [parent_id] => 4
164.               [sub_categories] => Array
165.                 (
166.                 )
168.               [decendants] => Array
169.                 (
170.                 )
171.             )
172.         )
173.       [decendants] => Array
174.         (
175.           [0] => 5
176.         )
177.     )
178.   [5] => stdClass Object
179.     (
180.       [category_id] => 5
181.       [parent_id] => 4
182.       [sub_categories] => Array
183.         (
184.         )
185.       [decendants] => Array
186.         (
187.         )
188.     )
189. )

Various routines like that have been able to do anything I need, so far. They're fairly simple as far as I'm concerned as well, which I like. I've looked at solutions to categories such as the "left_id, right_id" solution phpBB3 uses and that just seems really complicated to me.

But anyways, anyone have any suggestions for stuff to read on dealing with hierarchies with PHP and MySQL ?