How do I traverse an adjacency list in PHP?

Question

Let's look at the table category, as an example for the concept I want to understand:

ID    NAME       PARENT_ID
1     catA       0
2     catB       0
3     childA     1
4     childC     3

What's the best practice to get something organized like this:

array(

   'byId' => array(

        1 => array(
            'name' => 'catA',
            'hasChild' => array(
                'byId' => array(
                    3 => array(
                        'name' => 'childA',
                        'hasChild' => array(
                            'byId' => array(
                                4 => array(
                                    'name' => 'childB',
                                    'hasChild' => false
                                )
                            )
                        )
                    )
                )
            )
        ),

   )

);

Have a look at [Turn database result into array](http://stackoverflow.com/questions/2794638/turn-database-result-into-array) and [How to get an hierarchical php structure from a db table, in php array, or JSON](http://stackoverflow.com/questions/2799564/how-to-get-an-hierarchical-php-structure-from-a-db-table-in-php-array-or-json) — Orbling, May 19 '11 at 16:24

score 0 · Answer 1 · answered May 19 '11 at 16:54

Just a little bit of data structures here. Right now you have a hash table with the possibility that children can go on forever, which could serve as a nightmare for the already somewhat inefficient hash-table structure PHP has for arrays. What I suggest is simply making each item it's own array element and specifying a parent. This makes it easier because you know that you can only have exactly one parent or no parents at all, but each parent can have multiple children.

array (
    0 => array(
        'name' => 'Blah',
        'parent' => false,
    )

    1 => array(
        'name' => 'Blah\'s first child',
        'parent' => 0,
    )

    2 => array(
        'name' => 'Blah\'s second child',
        'parent' => 0,
    )

    3 => array(
        'name' => 'Foo',
        'parent' => false,
    )

    4 => array(
        'name' => 'Bar',
        'parent' => 3,
    )
)

Thanks for looking. In case you want a menu from it, let's say
Parent
ChildA
ChildOfChild
, you see, how would you do that ? Does this mean, this problem can only be solved trough recursive functions ? — punkbit, May 19 '11 at 17:31

How do I traverse an adjacency list in PHP?

1 Answers1