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!

Morgen

have you tried passing by reference? – An

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? – Morgen

see #3628378 for a lot of reference – Addictive

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. – Retrench

Answer 1

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] => 
    )

)

Retrench

Answer 2

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();

Togetherness

Answer 3

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.

Toyatoyama

Answer 4

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

Septi