Easiest way to build a tree from a list of Ancestors

Question

In my heart, I feel that there must be a super simple recursive solution to this, but I cannot immediately grok it.

I have a tree stored in SQL as a closure table. The tree looks like: (1 (2 (3), 4)), and the languages are MySQL's SQL and PHP 5.3.

The closure table is thus:

+----------+------------+
| ancestor | descendant |
+----------+------------+
|        1 |          1 | 
|        2 |          2 | 
|        3 |          3 | 
|        4 |          4 | 
|        1 |          2 | 
|        1 |          3 | 
|        1 |          4 | 
|        2 |          3 | 
+----------+------------+

I can query the ancestors quite easily with:

 SELECT descendant AS id, GROUP_CONCAT(ancestor) as ancestors FROM
 closure GROUP BY (descendant);

 +----+-----------+
 | id | ancestors |
 +----+-----------+
 |  1 | 1         | 
 |  2 | 2,1       | 
 |  3 | 3,1,2     | 
 |  4 | 4,1       | 
 +----+-----------+

How can I easily build a tree in PHP with this data? Can I use a smarter query to pull more of the data from MySQL?

Answer 1

I've used a closure table (the term sounds strange to me... I forgot what/where I heard it called something else) but I had a 3rd column of "distance" between ancestor and descendant, which lets you distinguish between direct descendants (children) and indirect descendants (grandchildren etc).

Technically the table you listed can record data in a directed acyclic graph, so it may not be possible to construct a hierarchical tree w/o duplicate sections.

edit:

If I were querying in PHP, I'd probably just SELECT on the table itself w/o using GROUP_CONCAT -- you're going to be processing things procedurally anyway, so why not just get the appropriate subset of the closure table in its rawest form?

Note also that a closure table will not store ordering information (if that is important).

If the tree aspects of this hierarchical data are very important, and you have a choice of how to store data, consider the nested set model which can maintain ordering and is much easier to reconstruct a tree.

Answer 2

The first key is to sort the SQL results by the number of ancestors. I did this in PHP since I avoid the complexities of multi-digit numbers.

This provides a list of nodes in an order in which they can be validly inserted.

Array
(
    [1] => Array
        (
            [0] => 1
        )

    [4] => Array
        (
            [0] => 4
            [1] => 1
        )

    [2] => Array
        (
            [0] => 2
            [1] => 1
        )

    [3] => Array
        (
            [0] => 3
            [1] => 1
            [2] => 2
        )

)

At this point, I don't care about the keys, only the lists of ancestors. The path through the tree can be found between the intersection of available nodes and the remaining ancestors.

  function add_node($ancestors, &$tree) {
    if (count($ancestors) == 1) {
      $tree[array_pop($ancestors)] = array();
      return;
    }   
    $next_node = array_intersect($ancestors, array_keys($tree));
    $this->add_node(
        array_diff($ancestors, $next_node) , 
        $tree[array_pop($next_node)]
        );  
  }