recursively search a hierarchial array and return all ancestors of found child, not just child

[eluser]CroNiX[/eluser]
Hi, I have a multidimensional array where each array has a parent id node to create a hierarchical tree.

Code:

$hierarchy[] = array('id' => 1, 'parent_id' => 0, 'name' = 'root1');
$hierarchy[] = array('id' => 2, 'parent_id' => 0, 'name' = 'root2');
$hierarchy[] = array('id' => 3, 'parent_id' => 1, 'name' = 'root1-1');
$hierarchy[] = array('id' => 4, 'parent_id' => 1, 'name' = 'root1-2');
$hierarchy[] = array('id' => 5, 'parent_id' => 3, 'name' = 'root1-1-1');
$hierarchy[] = array('id' => 6, 'parent_id' => 2, 'name' = 'root2-1');

I'm trying to come up with a recursive key/value search routine that will return all ancestor arrays of the found item without knowing the depth of the tree. All nodes with 0 for the parent_id are root level nodes.

Basically I want to search for something like "where key = name and value = xxx" and have it return all ancestors of that node.

So if I wanted to search for "key = name and value = root1-1", it should return and array like:

Code:

array[0] = array('id' => 1, 'parent_id' => 0, 'name' = 'root1'); //parent node first
array[1] = array('id' => 3, 'parent_id' => 1, 'name' = 'root1-1');  //first child after parent and the found node

if I was to search for "key = name and value = root1-1-1", it should return:

Code:

array[0] = array('id' => 1, 'parent_id' => 0, 'name' = 'root1'); //parent node first
array[1] = array('id' => 3, 'parent_id' => 1, 'name' = 'root1-1');  //first child after parent
array[2] = array('id' => 5, 'parent_id' => 3, 'name' = 'root1-1-1'); //first grandchild and the found node

So the main problem comes in the iteration and keeping track of parents. If I just want the array with the answer I can get that node, but I can't get it with all of the ancestors attached. How would you go about this? Any good ideas out there?

Thanks!

[eluser]WanWizard[/eluser]
Since you are talking about a where clause, I assume you want a query? In that case, you should check out http://dev.mysql.com/tech-resources/arti...-data.html.

Alternatively, if the list is not too big, you can read it all into an array, and use a recusive function to retrieve the required list.

[eluser]CroNiX[/eluser]
[quote author="WanWizard" date="1282265324"]Since you are talking about a where clause, I assume you want a query? In that case, you should check out http://dev.mysql.com/tech-resources/arti...-data.html.

Alternatively, if the list is not too big, you can read it all into an array, and use a recusive function to retrieve the required list.[/quote]
It is already retrieved from the db and in array form. And as far as a "where" clause it would just be something like:

Code:

if($array[$search_key] == $search_value) //found the node

I can get the node I'm looking for, I just can't get all of its ancestors. Its the recursive function that Im having problems with.

Thanks.

[eluser]bretticus[/eluser]
I've already spent too much time in this forum today (seems to be my escape from real work.) I have nothing to offer right now (may look at this tonight again and try to help.) Except, consider alternatives to recursion when possible. Iteration often solves the problem and you'll get much better performance when data is deeply nested or there is a lot of data. (Wow, sorry. I'll come back for sure tonight and offer a suggestion or two. Now I feel obligated after this post.)

[eluser]CroNiX[/eluser]
I'd appreciate it. I have a way to do it manually and only if I know how deep the tree is, but I want something generic that will work for any tree size.

This is the current working code that I'm trying to update, and in this case I'm searching for the array key 'full_url', although I want to make the key searchable as well as the value. Right now Im just searching for the value.

This is a little more confusing than my above example because its for a specific case. But as you can see, here is the basic flow.

1) search first parent, if found, store result as first entry in found array.
2) parent not found, go to next level if exists(children of parent). If found here, create parent entry from #1 as first entry in array, put this match second.
3) child not found, go to next level if exists (grandchildren). If found here, create parent entry from #1 as first entry in array, put child from #2 as second entry in array, put this third.
4) Continue searching branch...if not found in this branch, move to next parent and start over

Also, in this case, 'nav_id' is the same as 'id' in my original example.

Code:

function get_location($source_array, $search_value)
{
    $original = $source_array['items'];  //this is an array of all of the items
    $hierarchy = $source_array['parents'];//this is an array of keys of parent items

    $found = array();

    foreach($hierarchy[0] as $parent_id)
    {
        if($original[$parent_id]['full_url'] == $search_value)
        {
            $found['parent'] = $original[$parent_id]['nav_id'];
        } else {
            $children = get_location_children($source_array, $parent_id);
            foreach($children as $child)
            {
                if($child['full_url'] == $search_value)
                {
                    $found['parent'] = $original[$parent_id]['nav_id'];
                    $found['child'] = $original[$child['nav_id']]['nav_id'];
                } else {
                    $grandchildren = get_location_children($source_array, $child['nav_id']);
                    foreach($grandchildren as $grandchild)
                    {
                        if($grandchild['full_url'] == $search_value)
                        {
                            $found['parent'] = $original[$parent_id]['nav_id'];
                            $found['child'] = $original[$child['nav_id']]['nav_id'];
                            $found['grandchild'] = $original[$grandchild['nav_id']]['nav_id'];
                        }
                    }
                }
            }
        }
    }
    return $found;
}
function get_location_children($source_array, $search_id)
{
    $matches = array();
    if(array_key_exists($search_id, $source_array['parents']))
    {
        foreach($source_array['parents'][$search_id] as $key)
        {
            $matches[] = $source_array['items'][$key];
        }
    }
    return $matches;
}

[eluser]CroNiX[/eluser]
This seems to work:

Code:

$hierarchy[] = array('id' => 1, 'parent_id' => 0, 'name' => 'root1');
$hierarchy[] = array('id' => 2, 'parent_id' => 0, 'name' => 'root2');
$hierarchy[] = array('id' => 3, 'parent_id' => 1, 'name' => 'root1-1');
$hierarchy[] = array('id' => 4, 'parent_id' => 1, 'name' => 'root1-2');
$hierarchy[] = array('id' => 5, 'parent_id' => 3, 'name' => 'root1-1-1');
$hierarchy[] = array('id' => 6, 'parent_id' => 2, 'name' => 'root2-1');
if( ! function_exists('find_pat'))
{
    function find_pat($a, $n, $key='name' ){
        $out = array();
        foreach ($a as $r){
            if ($r[$key] == $n){
                $out = find_pat($a, $r['parent_id'],'id');
                $out[]=$r;
            }
        }
        return $out;
    }
}

$a = find_pat($hierarchy, 'root1-1-1');
echo '<pre>';
print_r($a);

correctly produces

Code:

Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 0
            [name] => root1
        )

    [1] => Array
        (
            [id] => 3
            [parent_id] => 1
            [name] => root1-1
        )

    [2] => Array
        (
            [id] => 5
            [parent_id] => 3
            [name] => root1-1-1
        )

)

[eluser]WanWizard[/eluser]
Or without a recusive function:

Code:

// storage for the results
$result = array();

// find the start node
foreach ( $hierarchy as $node )
{
    // is this the node we're looking for?
    if( isset($node[$search_key]) && $node[$search_key] == $search_value )
    {
        // add the node itself
        $result[] = $node;

        // first all ancestors
        while ( $node['parent_id'] != 0 )
        {
            // indicator to deal with broken hierarchies
            $tree_broken = TRUE;

            // find the parent of the node
            foreach ( $hierarchy as $parent )
            {
                // is this the parent?
                if ( $parent['id'] == $node['parent_id'] )
                {
                    // add it to the results
                    array_unshift($result, $parent);

                    // and make this the new start node
                    $node = $parent;

                    // tree structure is still ok
                    $tree_broken = FALSE;

                    // terminate the foreach
                    break;
                }
            }

            // if no parent could be found, the tree structure is broken
            if ( $tree_broken )
            {
                // break out of the while
                break;
            }
        }

        // and terminate the foreach
        break;
    }
}

[eluser]CroNiX[/eluser]
Thanks for working on it also. Correct me if Im wrong, but without using a recursive function you can't use this approach where the depth of the tree is unknown.

[eluser]mddd[/eluser]
That's not correct. WanWizard's code keeps going until the top (parent==0) is reached.
This is because of the " while ( $node['parent_id'] != 0 ) " loop.

[eluser]mddd[/eluser]
My thought was: why not get the information simply from the database. I assume there is a table with the fields 'id' and 'parent_id' as given in the first post.
Then you could simply get the list of "parents" by this sql statement:

Code:

SELECT t1.id id1, t2.id id2, t3.id id3, t4.id id4
FROM table t1
LEFT JOIN table t2 on t2.id=t1.parent
LEFT JOIN table t3 on t3.id=t2.parent
LEFT JOIN table t4 on t4.id=t3.parent

This will give you a nice list of ids. The only thing is that you need to JOIN on as many tables as you know is the maximum depth of the tree. I know you said this wasn't known, but in a practical sense there probably is a maximum you can safely use. It doesn't matter if you join on too many tables, they will simply give 'null' as a result because no node will be found with id=0.
In CI you could very simply build such a query:

Code:

$this->db->select('t1.id id1');
$this->db->from('table t1');
for($i=2;$i<=$max_depth;$i++)
{
  $this->db->select('t'.$i.'.id id'.$i);
  $this->db->join('table t'.$i, 't'.$i.'.id=t'.($i-1).'.parent', 'left');
}
$path = $this->db->get()->result_array();