Fix a function for graph calculations

Question

I have a graph:

Here is a data:

$nodes = [
        'f' => ['d g'],
        'b' => ['a d'],
        'g' => ['i'],
        'd' => ['c e'],
        'i' => ['h']
    ];

The function below trying to find a nodes between 2 provided nodes:

function findPathBetweenNodes($start, $end, $nodes) {
        
        foreach ($nodes as $node => $edges) {
            $nodes[$node] = explode(' ', $edges[0]);
        }

        function searchPath($current, $end, $nodes, &$visited) {
            if ($current === $end) {
                return [$current];
            }
            
            $visited[$current] = true;
            foreach ($nodes as $node => $children) {
                if (in_array($current, $children) && !isset($visited[$node])) {
                    $path = searchPath($node, $end, $nodes, $visited);
                    if ($path) {
                        return array_merge([$current], $path);
                    }
                }
            }
            return null;
        }

        $visited = [];
        $path = searchPath($start, $end, $nodes, $visited);

        if ($path) {
            array_shift($path); 
            array_pop($path);   
        }

        return $path ?: []; 
    }

Test case: print_r(findPathBetweenNodes('h', 'f', $nodes)); Returns correct result:

Array
(
    [0] => i
    [1] => g
)

Test case: print_r(findPathBetweenNodes('f', 'h', $nodes)); Return empty array.

Test case: print_r(findPathBetweenNodes('a', 'c', $nodes)); Returns empty array.

How to fix a function to make it work in other cases too? Thanks.

Answer 1

I agree with Simon, your node relationship structure is not ideal for this task. The space-delimited values makes unnecessary extra work and cannot be optimized for searching performance. Instead, I recommend building a 2d lookup array because PHP is very fast at searching for keys (versus values searching).

In my recursive function, I included the feature of avoiding potential circular/infinite recursion by removing/consuming elements from the lookup array with each deeper traversal.

My snippet is not designed or tested to work in a scenario where multiple node paths may occur. If this is a possibility, please specify this in your question body and provide more challenging sample data (or ask a new question).

To differentiate complete/successful paths from unconnected nodes, I've designed my function to return null to indicate no qualifying path.

Code: (Demo)

function findWayPoints(array $lookup, $start, $end, array $path = []): ?array
{
    if (isset($lookup[$start][$end])) {
        return $path;  // full path found; no need to further recurse
    }
    foreach ($lookup[$start] ?? [] as $conn => $irrelevant) {
        $result = findWayPoints(
            array_diff_key($lookup, [$start => null]),  // eliminate circular/infinite recursion
            $conn,  // change starting node in next call
            $end,
            array_merge($path, [$conn])  // append current match to path
        );
        if ($result !== null) {
            return $result;
        }
    }
    return null;  // dead end; kill path
}

function buildLookup($nodes) {
    $lookup = [];
    foreach ($nodes as $k => [$connections]) {
        foreach (explode(' ', $connections) as $conn) {
            $lookup[$k][$conn] = true;
            $lookup[$conn][$k] = true;
        }
    }
    return $lookup;    
}

$nodes = [
    'f' => ['d g'],
    'b' => ['a d'],
    'g' => ['i'],
    'd' => ['c e'],
    'i' => ['h']
];
$lookup = buildLookup($nodes);

   
echo json_encode(findWayPoints($lookup, 'h', 'f'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'f', 'h'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'a', 'c'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'a', 'b'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'a', 'h'));
echo "\n---\n";
echo json_encode(findWayPoints($lookup, 'i', 'j'));

Output:

["i","g"]
---
["g","i"]
---
["b","d"]
---
[]
---
["b","d","f","g","i"]
---
null