Finding a path in a multidimensional array for a certain ID

Question

I have an array that's stored like this:

[0] => Array
    (
        [id] => 1
        [cat_name] => c1
    )

[1] => Array
    (
        [id] => 2
        [cat_name] => c2
        [copii] => Array
            (
                [0] => Array
                    (
                        [id] => 5
                        [cat_name] => c21
                    )

                [1] => Array
                    (
                        [id] => 6
                        [cat_name] => c22
                    )

            )

    )

[2] => Array
    (
        [id] => 3
        [cat_name] => c3
        [copii] => Array
            (
                [0] => Array
                    (
                        [id] => 7
                        [cat_name] => c31
                        [copii] => Array
                            (
                                [0] => Array
                                    (
                                        [id] => 9
                                        [cat_name] => c311
                                    )

                            )

                    )

                [1] => Array
                    (
                        [id] => 8
                        [cat_name] => c32
                    )

            )

    )

I'm trying to find an easier way of finding a route to a certain ID. Now I'm using foreach to iterate through all possible arrays and finding the route.

Example:

id = 1:
     route[0][id]=1,route[0][cat_name]=c1
id = 5:
    route[0][id]=2,route[0][cat_name]=c2
    route[1][id]=5,route[1][cat_name]=c21
id = 9:
    route[0][id]=3,route[0][cat_name]=c3
    route[1][id]=7,route[1][cat_name]=c31
    route[2][id]=9,route[2][cat_name]=c311

If my question makes no sense, I blame it on the hours spent trying to find a nice solution to it...

Answer 1

Your question indeed makes no sense. What does "Finding the route" mean?

It looks like your array has a recursive structure describing a graph; a graph traversal algorithm for finding the shortest path might be more appropriate (i.e. convert your array into a graph data structure - maybe a node list + edge list, and run a graph algo on it).

Answer 2

In lieu of posting a bunch of code, I'd suggest you read up on recursion if you don't know about it. PHP isn't too great at recursion, but it's really your only option.

Basically you'd call a function that takes the array, id to find, and a string/array representing the path. Initially call that with a blank string or empty array for the latter parameter.

In the function you would do this:

• Run a foreach through the top level of $array
• If you find the $id you're looking for, return the $path.
• If one of the array values is a sub array, add the current ID node and call the function again with that - something like $foundPath = findPath( $array, $id, $path ).
• If $foundPath returns something, then you've got your path and can return.
• If it didn't find anything ($foundPath is false or null as below), leave it and move on to the next iteration of the loop.
• At the end of the loop, if you haven't found anything, return false or null.

Hope that helps!

Answer 3

Recursion is what you want:

<?php

    function walk_array(array $a, &$ra, $path, $depth = 0) {
     $id= isset($path[$depth]) ? $path[$depth] : null;
     if (!is_null($id)) {
      foreach ($a as $a2) {
       if ($a2['id'] == $id) {
        $ra[$depth]= $a2;
        unset($ra[$depth]['copii']);
        // This is the key bit - recursion is simply a function calling itself:
        if (isset($a2['copii']))
         walk_array($a2['copii'], $ra, $path, ++$depth);
       }
      }
     }
    }

    $complex_array= array(
      array('id'=> 1, 'name'=> 'Node #1', 'copii'=> array(
       array('id'=> 3, 'name'=> 'Node #3', 'copii'=> array(
         array('id'=> 4, 'name'=> 'Node #4')
       ))
      )),
      array('id'=> 2, 'name'=> 'Node #2', 'copii'=> array(
       array('id'=> 5, 'name'=> 'Node #5', 'copii'=> array(
         array('id'=> 6, 'name'=> 'Node #6',)
       ))
      )),
    );    

    // Prints out nodes 1,3,4 in order
    $ra= array();
    walk_array($complex_array, $ra, array(1, 3, 4));
    print_r($ra);

    // Prints out nodes 2,5,6 in order
    $ra= array();
    walk_array($complex_array, $ra, array(2, 5, 6));
    print_r($ra);

    // Prints out empty array
    $ra= array();
    walk_array($complex_array, $ra, array(5, 2, 4));
    print_r($ra);

    // Prints out nodes 2,5 in order
    $ra= array();
    walk_array($complex_array, $ra, array(2, 5));
    print_r($ra);
?>

Answer 4

One other way I can think of - avoiding recursion - is to use "variable variables", so you just try every possible combination of array indexes, up to a point.

$search = 3;
$ind = '$arr[0][copii][1]'; // generated somehow
if ( isset(${$ind}['id']) && ${$ind}['id'] == $search ) {
  // we found it
}

This would take just as long and you're not guaranteed to find anything. Also as I write this, I'm struggling to think of a solid way to generate the $ind values... apart from recursion. I guess you could generate 3-digit numbers like 000, 001, 002 and use each character to create the indices like $arr[0][copii][0][copii][0], $arr[0][copii][0][copii][1] and $arr[0][copii][0][copii][2].

This method is still not perfect since you will undoubtedly miss values and look for a lot of values that don't exist. To be honest, recursion is the simpler and cleaner option code-wise, and unless your array has hundreds of entries then you're not going to notice a big performance problem.