CODEWITHSUNDEEP
phprecursion
Steve Ives
Steve Ives

Reputation: 8134

Recursive function in PHP to find path between arbitrary nodes

I have an array representing connections between nodes.

Given a specific end node, I'd like to return a subset of the nodes that lead to this end node.

E.g. If my nodes definitions are "a-b", "a-c","c-e", "e-f", "e-k","k-z","q-z", "x-q" "k-m", "c-t" which represent the following:

Whole map

and I'd like to see the path(s) leading to 'z', which are:

critical path map

I have this PHP code:

<?php

$end   = "z";  
$items = array("a-b", "a-c", "c-e", "e-f", "e-k", "k-z", "q-z", "x-q", "k-m", "c-t"); 

$graph = getPre($items, $end);  

print_r($graph);  // This is what I want to populate

exit();

function getPre($array, $char) {  

  $predecessors = array_filter($array, function($line) use($char) {
      return strpos(substr($line, 2, 1), $char) === FALSE ? FALSE : TRUE;
            }
          );
  if (count($predecessors) == 0) {
    return;
  } else {
      print_r($predecessors)."<br>";
    echo "<br>";
    foreach ($predecessors as $pre) {getPre($array, substr($pre, 0,1));}
  }
}

?>

which outputs:

Array ( [5] => k-z [6] => q-z )
Array ( [4] => e-k )
Array ( [2] => c-e )
Array ( [1] => a-c )
Array ( [7] => x-q )

which at least is the correct nodes list, so I'm almost there.

Question: How do I have have the results returned in my $graph array?

Somewhere I need to return $predecessors; and have it merged with the previous results. I will also want to add functionality to be able to specify a start node, but I think that will just be an extra test in my recursive end test.

Upvotes: 0

Views: 428

Answers (1)

Nigel Ren
Nigel Ren

Reputation: 57141

The main thing you needed (as you said) is to build the arrays to pass the data back. This code will build a sub element if there are more elements to add or just set the return value to the item if nothing is found. Not sure if the format of the output is exactly what you are after, but you may be able to work with it.

function getPre($array, $char) {
    $graph = [];
    foreach ($array as $pre) {
        if ( $pre[2] == $char ) {
            $graph[$pre] = getPre($array, $pre[0]) ?: $pre;
        }
    }

    return $graph;
}

Note than rather than having to use substr() to extract a character, you can use the string as an array and [2] is the 3rd character.

This outputs...

Array
(
    [k-z] => Array
        (
            [e-k] => Array
                (
                    [c-e] => Array
                        (
                            [a-c] => a-c
                        )

                )

        )

    [q-z] => Array
        (
            [x-q] => x-q
        )

)

To output the codes as strings, I've processed the result of the above function using iterators. The idea being to start at the leaf nodes and then to track back (using getSubIterator()) to the base of the tree...

$graph = getPre($items, $end);
$objects = new RecursiveIteratorIterator( new RecursiveArrayIterator( $graph ), RecursiveIteratorIterator::LEAVES_ONLY );
foreach ( $objects as $name => $object )    {
    $path = $object;
    for ( $depth = $objects->getDepth() - 1; $depth >= 0; $depth-- ) {
        $path .= ",".$objects->getSubIterator( $depth )->key();
    }
    echo $path.PHP_EOL;
}

Which outputs...

a-c,c-e,e-k,k-z
x-q,q-z

Upvotes: 2

Related Questions