PHP recursive adjacency list function

Question

I have a DB like this:

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 am trying to capture the tree structure in which the parents are listed. I know another option (nested sets, in my opinion?), But now I will stick to this. Now I'm trying to get data from the database and into the structure of nested arrays 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 I would like to come up with some kind of nested associative array tree, but I cannot figure out how to do this. It seems that nothing is writing to the array that I enter, and I kind of lose myself in recursion. Can someone help me get this last hump that will lead to something like:

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

And I'm less interested in the specific output form. It will be converted to JSON, and I have not yet written a client-side handler, so don't worry about the exact structure.

Thanks!

Answer 1

Try it.

 $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 conclusion:

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

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

Answer 3

You really don't need a recursive function. Get all the data using a single database query and loop into it. This will be much faster than a few database queries.

Assuming you are storing data in MySQL, see the answer to this question for instructions on how to write a SELECT statement in the Adjacency list table, which returns everything in the hierarchy . In short, use MySQL session variables. Then grab the result set and loop around it, use the stack to press - pop - look at the last parent id to determine the indentation of your data structures.

Answer 4

Here is the PHP class that I wrote to handle all kinds of Adjacency list tasks.

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