Dynamic Tree Building in PHP

Posted by santosj on June 1, 2009

I know of the data structure, I just never had the privilege of ever using it. It seems not many others have been intimate with building trees dynamically. Yeah sure, building a tree statically is easy and most people do so whether they realize it or not.

The problem I had is that PHP doesn’t offer built-in procedural or object-oriented tree support. Just Hash, Queue, and Stack, but you can use many of those functions with Tree data structures to traverse and edit a tree. Nothing that allows easily creating one or normalizing the tree. The Tree data structure has its own methods for easily searching for internal data that isn’t compatible with Hash types.

I decided to copy some of the resource above and also create an object-oriented Tree that better manages and searches the internal data.

Procedural Tree

To create a tree you have to first create an array and then create an reference to that array using its index.

$node = 0;
$parent[$node] = array();
$child = &$parent[$node];

It is better to create a recursive function if you are going to go into an unknown depth.

  1. Check to see if you need to continue
  2. Calculate which nodes will be children.
  3. Create a loop to add the children.
  4. Add a child to the parent.
  5. After each addition of children recursive go into the function with the previous child.

It is possible to crash PHP or use up vast amounts of memory very quickly within the infinite recursive loop. Therefore you need to make sure you allow for breaking the flow1 when the tree should not be created further. 2 is figuring out which nodes should be added to the parent and creating a loop3to add them. You’ll need to go into the recursive function5 right after adding each child4 to build the tree out.

My incorrect implementation of building a tree for Shortest Path First will give a better example of what I mean. You should not however use it, because it hasn’t been tested for correct functionality. It does build the tree, but it doesn’t do any additional checks, such as building the tree based on score and it needs to keep the coordinates somehow without going into an infinite loop. This isn’t showing how to implement the Dijkstra algorithm, or more accurately how to poorly implement the Dijkstra algorithm, but just the above algorithm.

// $Closed an array of nodes that will be used to create the tree.
// $measure is used to find the children.
// $tree is the reference to the tree data structure
// $end is used to end the recursion.
function buildTree($closed, $measure, array $tree, $coord, $end)
{
    // 1
    if(count($closed) == 0)
    {
        return;
    }

    // 2
    $perimeter = $measure->getPerimeterCells($coord);

    // bug
    // Part of 1
    $perimeterIndex = $closed->lookup($coord['x'], $coord['y'], $coord['z']);
    $closed->remove($perimeterIndex);

    // 3
    foreach($perimeter as $cell)
    {
        // This tests to see if the child node should be added
        // Part of Shortest path first so no explanation (which
        // would probably be incorrect anyway)
        $exists = $closed->lookup($cell['x'], $cell['y']);

        if($exists !== false)
        {
            // Index Creation: yes it is an string and yes it is
            // the index. Don't ask.
            $string = "$cell[x], $cell[y], 0";

            // WOOT! The end was found, no need to continue
            // The recursion, go back to the parent.
            if(($cell['x'] === $end['x']) && ($cell['y'] === $end['y']))
            {
                // The 0 would allow us to traverse the tree later to
                // find the instances where the end was found
                // and only keep those.

                // 4
                $tree[$string] = 0;
                return;
            }
            // Breed the parent
            else
            {
                // 4
                $tree[$string] = array();
                $nextNode = &$tree[$string];
            }

            // Ignore this
            $nodeCoord = $closed->seek($exists);

            // 5
            buildTree($closed, $measure, &$nextNode, $nodeCoord['node'], $end);
        }
    }
}

You would have to create the parent yourself, but the fun part is that nothing has to be returned. Since you created the parent you can then use that same parent for anything else you’ll need.

$parent[$node] = array();
$firstchild = &$parent[$node];

buildTree($closed, $measure, &$firstchild, $coord, $end);

print_r($parent);

One thing to look out for is that when doing recursion, much like loops, is that you have to give yourself a way to break out of the recursion to keep from having an infinite loop. There are a lot of ways for doing this, my example uses the easiest, but not the best.

Possibly Related Posts:


General

Comments are closed.