Converting a PHP array of key value pairs to a hierarchical nested tree structure

Question

I have a situation where I have an array structure that consists of about 6,000 key/value pairs.

The array is in a structure like:

Array
(
[0] => Array
    (
        [parent] => parentA
        [name] => child1
    )

[1] => Array
    (
        [parent] => parentB
        [name] => childC
    )

[2] => Array
    (
        [parent] => parentA
        [name] => child2
    )

[3] => Array
    (
        [parent] => parentC
        [name] => child3
    )
[4] => Array
    (
        [parent] => child1
        [name] => child4
    )

[5] => Array
    (
        [parent] => child4
        [name] => child5
    )

From that data source I am trying to massage the output into

A) An array that I can use in later functionality
B) A table display where each row will be one full chain, and each column will be a level deeper. Essentially if you think of page navigation, this is a bread crumb display where each node would be in the next column.

I have been playing with a few approaches here

1) Using the recursive function at this stack overflow question: https://stackoverflow.com/a/2915920/997226, however I have not been able to modify this to work with my data where the parent can be the same. In their example of $tree, the left hand (key) value is always unique.

I understand in their example their key is the child, and the value (right hand side) is the parent, however I still can not get this to work for me as in my data there are multiples of the same item on both the parent side and the child side. (Think complex relationships where an article can be contained within multiple parent categories.

2) I have tried starting to create a "base array" of unique parent elements, and then creating a recursive function to do a search on the "original key value array" but this didn't quite work either.

3) I tried saving the data in a database as I'm pretty familiar with using left/right values for accessing/manipulating data as a nested set, but I'm trying to avoid having to have everything INSERT/SELECT from a database.

4) I tried working with the various PHP Iterators classes as I have used these successfully for working with the file system and building file/directory listings, so I've been playing with RecursiveArrayIterator / ParentIterator/ArrayIterator, but can't seem to figure out the proper syntax to use.

I understand that recursing may not be as efficient as using references for a data set of this size, however it seems like it provides the most flexibility, I just can't seem to get it to iterate recursively correctly.

Beyond, this specific question, I'm also trying to better understand the algorithm nature of programmatic recursion.

The more I read through other people's code examples that are trying to do something similar, but with a different data structure I just become more confused.

If anyone could help point me in the right direction it would be appreciated.

Clarification Notes

1. There will be multiple levels.
2. It has been pointed out that the data structure can be thought of as a Directed acyclic graph and that makes complete sense.

Answer 1

** Update #2 - I've redesigned using referencing (not recursion). This requires only a single pass through the data. Every parent or child is added as a top level item to an array ($a in this case) if it does not already exist. The key of this top level item is the name of the parent or child. The value is an array which contains references to its children's top level item. In addition, a second array ($p) is created with only references to the parents in the first array ($a). In a single pass which is very quick, all the relationships are discovered.

The Code (for update #2):

<?php
$tree_base = array(
    array('parent' => 'parentA','name' => 'child1'),
    array('parent' => 'parentB','name' => 'childC'),
    array('parent' => 'parentA','name' => 'child2'),
    array('parent' => 'parentC','name' => 'child3'),
    array('parent' => 'child1','name' => 'child4'),
    array( 'parent' => 'child4', 'name' => 'child5'),
    array( 'parent' => 'DataSelect', 'name' => 'getBaseUri'),
    array( 'parent' => 'getBaseUri', 'name' => 'getKbBaseURI')
    );

    $tree = parseTree($tree_base);
    echo '<pre>'.print_r($tree, TRUE).'</pre>';
    showresults($tree);

function parseTree($tree){
    $a = array();
    foreach ($tree as $item){
        if (!isset($a[$item['name']])){
            // add child to array of all elements
            $a[$item['name']] = array();
        }
        if (!isset($a[$item['parent']])){
            // add parent to array of all elements
            $a[$item['parent']] = array();

            // add reference to master list of parents
            $p[$item['parent']] = &$a[$item['parent']];
        }
        if (!isset($a[$item['parent']][$item['name']])){
            // add reference to child for this parent
            $a[$item['parent']][$item['name']] = &$a[$item['name']];
        }   
    }
    return $p;
}

function showresults($tree, &$loop = array()){
        if (is_array($tree) & count($tree) > 0){       
                echo "<table>";
                echo "<tr>";
                foreach ($tree as $key => $children){
                    // prevent endless recursion
                    if (!array_key_exists($key, $loop)){
                        $loop[$key] = null;
                        echo "<tr>";
                        echo "<td style='border:1px solid'>";
                        echo $key;
                        echo "<td style='border:1px solid'>";
                        showresults($children, $loop);
                        echo "</td>";
                        echo "</td>";
                        echo "</tr>";
                    }
                }
                echo "</tr>";
                echo "</table>";
        }
}

?>

The output (for update #2):

Array
(
    [parentA] => Array
        (
            [child1] => Array
                (
                    [child4] => Array
                        (
                            [child5] => Array
                                (
                                )

                        )

                )

            [child2] => Array
                (
                )

        )

    [parentB] => Array
        (
            [childC] => Array
                (
                )

        )

    [parentC] => Array
        (
            [child3] => Array
                (
                )

        )

    [DataSelect] => Array
        (
            [getBaseUri] => Array
                (
                    [getKbBaseURI] => Array
                        (
                        )

                )

        )

)

**Update #1 - I've fixed code to show multi-level children (and your new example array structure). To keep it clean, I am only using the key of the resulting array elements to store the name of parent and child. The table output becomes more visually complicated. I've used one row for each parent / child group with the first column for the parent and second column for its children. This is also recursive so that the column containing the children can show its children (if any) in a new table of the same format (easier viewed than explained).

The output (for update #1):

 Array
(
    [parentA] => Array
        (
            [child1] => Array
                (
                    [child4] => Array
                        (
                            [child5] => 
                        )

                )

            [child2] => 
        )

    [parentB] => Array
        (
            [childC] => 
        )

    [parentC] => Array
        (
            [child3] => 
        )

)

The code (for update #1):

<?php
$array = array(
    array('parent' => 'parentA',
                    'name' => 'child1'),
    array('parent' => 'parentB',
                    'name' => 'childC'),
    array('parent' => 'parentA',
                    'name' => 'child2'),
    array('parent' => 'parentC',
                    'name' => 'child3'),
    array('parent' => 'child1',
                    'name' => 'child4'),
    array( 'parent' => 'child4',
                    'name' => 'child5')
    );

    // parse array into a hierarchical tree structure
    $tree = parseTree($array);

    // Show results
    echo '<pre>';
    print_r($tree);
    echo '</pre>';  
    echo "<br>Table Format:";

    showresults($tree);

    function parseTree(& $tree, $root = null) {
        $return = null;
        // Traverse the tree and search for children of current parent
      foreach ($tree as $key=> $item){
      // A child is found
            if ($item['parent'] == $root){
                // append child into array of children & recurse for children of children
                $return[$item['name']] = parseTree($tree, $item['name']);
                // delete child so won't include again
                unset ($tree[$key]);
            }
            elseif ($root == null) {
                // top level parent - add to array 
                $return[$item['parent']] = parseTree($tree, $item['parent']);
                // delete child so won't include again
                unset ($tree[$key]);
            }
        }
        return $return;
    }

    function showresults($tree){

        if (is_array($tree)){       
            echo "<table>";
            echo "<tr>";

            foreach ($tree as $key => $children){
                echo "<tr>";

                echo "<td style='border:1px solid'>";
                echo $key;

                echo "<td style='border:1px solid'>";
                showresults($children, true);
                echo "</td>";

                echo "</td>";

                echo "</tr>";
            }

            echo "</tr>";
            echo "</table>";
        }
    }

?>