Recursive PHP function for adjacency-list display

Question

I have a DB like so:

id  text           parent
1   Parent 1        0   
2   Child of 1      1   
3   Sibling         1   
4   Another Parent  0 
5   A first child   4

So I'm trying to capture a tree structure my listing the parents. I'm aware of the other option (nested sets I think?) but I'm going to stick with this for now. I'm now trying to get the data out of the DB and into a nested array structure in PHP. I have a function like this:

class Data_Manager
{   
    public $connection = '';
    public $collection = array();

    function __construct() {
        $this->connection = mysql_connect('localhost', 'root', 'root');
        $thisTable = mysql_select_db('data');
            // error handling truncated
    }


    function get_all() {
        $arr = &$this->collection;

        $this->recurseTree('', 0, $arr);
        var_dump($arr);
    }

    function recurseTree($parent, $level, $arrayNode) {
        $result = mysql_query('SELECT * FROM tasks WHERE parent="' . $parent . '";');

        while ($row = mysql_fetch_array($result)) {
            $row['children'] = array(); //where I'd like to put the kids    
            $arrayNode[$row['id']]= $row;
            $this->recurseTree($row['id'], $level+1, $arrayNode[$row['id']]);
        }
    }
}

So what I'd like to come out with is some kind of nested tree of associative arrays, but I can't figure out quite how to do that. Nothing seems to be writing to the array I pass in, and I'm sort of losing track of myself in the recursion. Can anyone help get me over this last hump that will result in something like:

[
Parent1 => [
               children => ['Child of 1', 'Sibling']
           ],
AnotherParent => [
                     children => ['First Child']
                 ]
]

And I'm less concerned with the specific form of the output. It will be turned into JSON and I haven't dealt with writing up the client-side handler yet, so no worries on exact structure.

Thanks!

I do when I pass in the original instance variable $collection; I don't know much about how that works, but should I use that all through recursion to always edit the 'mother' array? — Alex Mcp, Nov 22 '10 at 04:31
see http://stackoverflow.com/questions/3627878/php-mysql-retrieve-a-single-path-in-the-adjacency-list-model for a lot of reference — , Nov 22 '10 at 04:34
before even getting into your algorithm, you are never altering/buidling any data here. you NEED to either have an argument of recurseTree called &$arr ($arr by reference so it changes when you alter it) or return values from recurseTree and do $arr = recurseTree(...) in get_all. I recommend the 2nd way. I also strongly recommend you stop querying the database in recurseTree - you're already passing in all the data. use array_filter on the value of parent if you must - DONT query the database unnecessarily just to filter by parent's value. — jon_darkstar, Nov 22 '10 at 04:43

jon_darkstar · Answer 1 · 2010-11-22T14:45:03.133

Try this.

$sql = "SELECT * FROM tasks";
$r = mysql_query($sql, $conn);
$arr = array();
while ($row = mysql_fetch_assoc($r))
   $arr[] = $row

function build($arrayIn, $parent)
{
    $makeFilter = function($p) {return function($x) use ($p) {return $x['parent'] == $p;};};
    $f = $makeFilter($parent);
    $these = array_filter($arrayIn, $f);
    $remaining = array_diff_assoc($arrayIn, $these);
    $ans = array();

    foreach($these as $cur)
    {
       $ans[$cur['text']] = build($remaining, $cur['id']);
    }
    return $ans ? $ans : null;
}

$tree = build($arr, 0)
echo_r($arr);
echo "becomes<br />";
echo_r($tree);

Here is my output:

Array
(
[0] => Array
    (
        [text] => a
        [id] => 1
        [parent] => 0
    )

[1] => Array
    (
        [text] => b
        [id] => 2
        [parent] => 0
    )

[2] => Array
    (
        [text] => c
        [id] => 3
        [parent] => 1
    )

[3] => Array
    (
        [text] => d
        [id] => 4
        [parent] => 2
    )

[4] => Array
    (
        [text] => e
        [id] => 5
        [parent] => 2
    )

[5] => Array
    (
        [text] => f
        [id] => 6
        [parent] => 3
    )

)

becomes

Array
(
[a] => Array
    (
        [c] => Array
            (
                [f] => 
            )

    )

[b] => Array
    (
        [d] => 
        [e] => 
    )

)

score 0 · Answer 2 · answered Dec 03 '12 at 04:16

0

Here is a PHP class I wrote for handling all kinds of Adjacency list tasks.

http://www.pdvictor.com/?sv=&category=just+code&title=adjacency+model

answered Dec 03 '12 at 04:16

Peter Drinnan

4,344
1
36
29

score 0 · Answer 3 · answered Nov 22 '10 at 04:35

This bit of pseudo code should help.

function getTasks($parent = 0){
    $tasks = array();
    $query = mysql_query("select * from table where parent = $parent");
    $rows = array();
    while(($row = mysql_fetch_assoc($query)) !== FALSE){ $rows[] = $row; }
    if(count($rows)){
        $tasks[$parent][] = getTasks($parent);
    } else {
        return $tasks;
    }
}

$tasks = getTasks();

score 0 · Answer 4 · edited May 23 '17 at 11:45

You really don't need a recursive function here. Get all the data using one database query and loop over it. It will be much faster then multiple database calls.

Assuming you're storing the data in MySQL, see the answer to this question for instructions on how to write a SELECT statement against an Adjacency List table that returns everything in a hierarchy. In short, use MySQL session variables. Then take the resultset and loop over it, use a stack to push - pop - peek the last parent id to determine indentation of your data structures.

Recursive PHP function for adjacency-list display

4 Answers4

Linked