Uninformed (Blind) Search

Depth-First Search (DFS)

Depth-First Search (DFS) is a classic algorithm for traversing or searching through tree and graph data structures. As the name suggests, DFS explores as far down a branch as possible before backtracking to examine other paths. This behavior makes DFS particularly useful in scenarios where exploring deep hierarchies or paths is necessary. It relies on a stack data structure — either explicitly (using a manual stack) or implicitly (via recursion) — to manage the nodes being visited.
Example of class UninformedSearchGraph (with DFS search):

<?php

namespace app\classes\search;

use InvalidArgumentException;
use SplPriorityQueue;
use SplQueue;

class UninformedSearchGraph {
    private array $adjacencyList;
    private array $vertexLabels;
    private array $levels;
    // Store edge weights
    private array $weights;

    public function __construct() {
        $this->adjacencyList = [];
        $this->vertexLabels = [];
        $this->levels = [];
        $this->weights = [];
    }

    public function addVertex(string $vertex, int $level = -1, float $heuristic = 0.0, string $label = ''): void {
        if (!isset($this->adjacencyList[$vertex])) {
            $this->adjacencyList[$vertex] = [];
            $this->vertexLabels[$vertex] = $label;
            $this->levels[$vertex] = $level;
        }
    }

    public function getVertexLabel(string $vertex = ''): string {
        return $this->vertexLabels[$vertex] ?? $vertex;
    }

    public function addEdge(string $vertex1, string $vertex2, float $weight = 1.0): void {
        if (!isset($this->adjacencyList[$vertex1]) || !isset($this->adjacencyList[$vertex2])) {
            throw new InvalidArgumentException("Both vertices must exist in the graph.");
        }

        $this->adjacencyList[$vertex2][] = $vertex1;
        // For undirected graph
        $this->adjacencyList[$vertex1][] = $vertex2;

        // Store weights for both directions
        $this->weights["$vertex1->$vertex2"] = $weight;
        $this->weights["$vertex2->$vertex1"] = $weight;
    }

    public function bfs(string $startVertex): array {
        if (!isset($this->adjacencyList[$startVertex])) {
            throw new InvalidArgumentException("Start vertex does not exist in the graph.");
        }

        $visited = [];
        $queue = new SplQueue();
        $path = [];

        // Mark the starting vertex as visited and enqueue it
        $visited[$startVertex] = true;
        $queue->enqueue($startVertex);

        while (!$queue->isEmpty()) {
            $currentVertex = $queue->dequeue();

            // Add vertex to path
            $path[] = [
                'vertex' => $currentVertex,
                'level' => $this->levels[$currentVertex],
                'visits' => $visited[$currentVertex] ?? 0
            ];

            // Get all adjacent vertices of the dequeued vertex
            foreach ($this->adjacencyList[$currentVertex] as $neighbor) {
                if (!isset($visited[$neighbor])) {
                    $visited[$neighbor] = true;
                    $queue->enqueue($neighbor);
                }
            }
        }

        return $path;
    }

    public function dfs(string $startVertex, string $target = null): array {
        if (!isset($this->adjacencyList[$startVertex])) {
            throw new InvalidArgumentException("Start vertex does not exist in the graph.");
        }

        $visited = [];
        $path = [];

        // Helper function for recursive DFS
        $dfsRecursive = function(string $vertex) use (&$dfsRecursive, &$visited, &$path, $target): bool {
            // Mark current vertex as visited
            $visited[$vertex] = true;

            // Add vertex to path
            $path[] = [
                'vertex' => $vertex,
                'level' => $this->levels[$vertex]
            ];

            // If we found the target, stop the search
            if ($vertex === $target) {
                return true; // Target found
            }

            // Visit all adjacent vertices
            foreach ($this->adjacencyList[$vertex] as $neighbor) {
                if (!isset($visited[$neighbor])) {
                    if ($dfsRecursive($neighbor)) {
                        return true; // Target found in this path
                    }
                }
            }

            return false; // Target not found in this path
        };

        // Start DFS from the given vertex
        $dfsRecursive($startVertex);
        return $path;
    }

    public function dls(string $startVertex, int $maxDepth, string $target = null, bool $pathOnly = false): array {
        if (!isset($this->adjacencyList[$startVertex])) {
            throw new InvalidArgumentException("Start vertex does not exist in the graph.");
        }

        $visited = [];
        $path = [];
        $found = false;

        // Helper function for recursive DLS
        $dlsRecursive = function(string $vertex, int $depth) use (&$dlsRecursive, &$visited, &$path, &$found, $maxDepth, $target): void {
            // Mark current vertex as visited
            $visited[$vertex] = true;

            // Add vertex to path
            $path[] = [
                'vertex' => $vertex,
                'level' => $this->levels[$vertex],
                'depth' => $depth
            ];

            // If we found the target, mark as found
            if ($vertex === $target) {
                $found = true;
                return;
            }

            // If we've reached max depth, stop exploring this path
            if ($depth >= $maxDepth) {
                return;
            }

            // Visit all adjacent vertices
            foreach ($this->adjacencyList[$vertex] as $neighbor) {
                if (!isset($visited[$neighbor]) && !$found) {
                    $dlsRecursive($neighbor, $depth + 1);
                }
            }

            // If this path didn't lead to the target and we're backtracking,
            // we can optionally remove this vertex from visited to allow it
            // to be visited again through a different path
            if (!$found) {
                unset($visited[$vertex]);
            }
        };

        // Start DLS from the given vertex at depth 0
        $dlsRecursive($startVertex, 0);

        if ($pathOnly) {
            return $path;
        }

        return [
            'path' => $path,
            'found' => $found,
            'maxDepth' => $maxDepth
        ];
    }

    public function iddfs(string $startVertex, string $target = null, int $maxIterations = 100, bool $pathOnly = false): array {
        if (!isset($this->adjacencyList[$startVertex])) {
            throw new InvalidArgumentException("Start vertex does not exist in the graph.");
        }

        $allPaths = [];
        $depth = 0;

        // Iteratively increase depth until target is found or max depth is reached
        while ($depth < $maxIterations) {
            $result = $this->dls($startVertex, $depth, $target);
            $allPaths[] = [
                'depth_limit' => $depth,
                'path' => $result['path'],
                'found' => $result['found']
            ];

            // If target is found, return all paths explored
            if ($result['found']) {
                if ($pathOnly) {
                    return $allPaths[$depth]['path'];
                }

                return [
                    'success' => true,
                    'final_depth' => $depth,
                    'paths' => $allPaths
                ];
            }

            $depth++;
        }

        // If target wasn't found within maxIterations
        return [
            'success' => false,
            'final_depth' => $depth - 1,
            'paths' => $allPaths
        ];
    }

    public function ucs(string $startVertex, string $targetVertex = null, bool $pathOnly = false): array {
        if (!isset($this->adjacencyList[$startVertex])) {
            throw new InvalidArgumentException("Start vertex does not exist in the graph");
        }

        $pq = new SplPriorityQueue();
        $pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

        $costs = [$startVertex => 0];
        $visited = [];
        $previous = [$startVertex => null];  // Track the previous node
        $path = [];
        $explored = [];  // Track all explored nodes

        $pq->insert($startVertex, 0);

        while (!$pq->isEmpty()) {
            $current = $pq->extract();
            $currentVertex = $current['data'];
            $currentCost = -$current['priority'];

            if (isset($visited[$currentVertex])) {
                continue;
            }

            $visited[$currentVertex] = true;
            $explored[] = [
                'vertex' => $currentVertex,
                'level' => $this->levels[$currentVertex],
                'cost' => $currentCost
            ];

            if ($currentVertex === $targetVertex) {
                break;
            }

            foreach ($this->adjacencyList[$currentVertex] as $neighbor) {
                $weight = $this->weights["$currentVertex->$neighbor"] ?? 1.0;
                $newCost = $costs[$currentVertex] + $weight;

                if (!isset($costs[$neighbor]) || $newCost < $costs[$neighbor]) {
                    $costs[$neighbor] = $newCost;
                    $previous[$neighbor] = $currentVertex;  // Store the previous node
                    $pq->insert($neighbor, -$newCost);
                }
            }
        }

        // Reconstruct the optimal path
        $optimalPath = [];
        $current = $targetVertex;
        while ($current !== null) {
            $optimalPath[] = [
                'vertex' => $current,
                'level' => $this->levels[$current],
                'cost' => $costs[$current]
            ];
            $current = $previous[$current];
        }

        if ($pathOnly){
            return array_reverse($optimalPath);
        }

        return [
            'success' => isset($visited[$targetVertex]),
            'explored' => $explored,  // All nodes explored during search
            'optimalPath' => array_reverse($optimalPath),  // The actual optimal path
            'cost' => $costs[$targetVertex] ?? INF
        ];
    }

    public function bds(string $startVertex, string $targetVertex, bool $pathOnly = false): array {
        if (!isset($this->adjacencyList[$startVertex]) || !isset($this->adjacencyList[$targetVertex])) {
            throw new InvalidArgumentException("Both start and target vertices must exist in the graph.");
        }

        // Initialize forward and backward search queues
        $forwardQueue = new SplQueue();
        $backwardQueue = new SplQueue();

        // Initialize visited sets and parent tracking for both directions
        $forwardVisited = [$startVertex => true];
        $backwardVisited = [$targetVertex => true];
        $forwardParent = [$startVertex => null];
        $backwardParent = [$targetVertex => null];

        // Initialize path tracking
        $forwardPath = [];
        $backwardPath = [];
        $intersectionVertex = null;

        // Add start and target vertices to their respective queues
        $forwardQueue->enqueue($startVertex);
        $backwardQueue->enqueue($targetVertex);

        while (!$forwardQueue->isEmpty() && !$backwardQueue->isEmpty()) {
            // Process forward search
            $intersectionVertex = $this->processBdsQueue(
                $forwardQueue,
                $forwardVisited,
                $backwardVisited,
                $forwardParent,
                $forwardPath,
                'forward'
            );

            if ($intersectionVertex !== null) {
                if ($pathOnly) {
                    return [...$forwardPath, ...$backwardPath];
                }

                $result = $this->constructBdsPath(
                    $intersectionVertex,
                    $forwardParent,
                    $backwardParent,
                    $forwardPath,
                    $backwardPath
                );
            }

            // Process backward search
            $intersectionVertex = $this->processBdsQueue(
                $backwardQueue,
                $backwardVisited,
                $forwardVisited,
                $backwardParent,
                $backwardPath,
                'backward'
            );

            if ($intersectionVertex !== null) {
                if ($pathOnly) {
                    return [...$forwardPath, ...$backwardPath];
                }

                return $this->constructBdsPath(
                    $intersectionVertex,
                    $forwardParent,
                    $backwardParent,
                    $forwardPath,
                    $backwardPath
                );
            }
        }

        // No path found
        return [
            'success' => false,
            'path' => [],
            'forwardExplored' => $forwardPath,
            'backwardExplored' => $backwardPath
        ];
    }

    public function rws(string $startVertex, string $targetVertex = null, int $maxSteps = 1000, bool $pathOnly = false): array {
        if (!isset($this->adjacencyList[$startVertex])) {
            throw new InvalidArgumentException("Start vertex does not exist in the graph.");
        }

        $path = [];
        $visited = [];
        $currentVertex = $startVertex;
        $steps = 0;
        $found = false;

        // Add start vertex to path
        $path[] = [
            'vertex' => $currentVertex,
            'level' => $this->levels[$currentVertex],
            'step' => $steps
        ];

        while ($steps < $maxSteps) {
            // Check if we've found the target
            if ($targetVertex !== null && $currentVertex === $targetVertex) {
                $found = true;
                break;
            }

            // Get neighbors of current vertex
            $neighbors = $this->adjacencyList[$currentVertex];

            // If no neighbors, break
            if (empty($neighbors)) {
                break;
            }

            // Randomly select next vertex
            $nextVertex = $neighbors[array_rand($neighbors)];
            $steps++;

            // Track visited nodes (optional, can be removed if you want pure random walk)
            $visited[$currentVertex] = ($visited[$currentVertex] ?? 0) + 1;

            // Add to path
            $path[] = [
                'vertex' => $nextVertex,
                'level' => $this->levels[$nextVertex],
                'step' => $steps,
                'visits' => $visited[$nextVertex] ?? 0
            ];

            $currentVertex = $nextVertex;
        }

        if ($pathOnly) {
            return $path;
        }

        return [
            'success' => $found,
            'path' => $path,
            'steps' => $steps,
            'maxSteps' => $maxSteps,
            'visited' => $visited
        ];
    }

    private function processBdsQueue(
        SplQueue $queue,
        array &$currentVisited,
        array $oppositeVisited,
        array &$parentMap,
        array &$pathTracking,
        string $direction
    ): ?string {
        if ($queue->isEmpty()) {
            return null;
        }

        $currentVertex = $queue->dequeue();

        // Add to path tracking
        $pathTracking[] = [
            'vertex' => $currentVertex,
            'level' => $this->levels[$currentVertex],
            'direction' => $direction
        ];

        // Check neighbors
        foreach ($this->adjacencyList[$currentVertex] as $neighbor) {
            // If we've found intersection with opposite search
            if (isset($oppositeVisited[$neighbor])) {
                return $neighbor;
            }

            // If not visited in current direction, add to queue
            if (!isset($currentVisited[$neighbor])) {
                $currentVisited[$neighbor] = true;
                $parentMap[$neighbor] = $currentVertex;
                $queue->enqueue($neighbor);
            }
        }

        return null;
    }

    private function constructBdsPath(
        string $intersectionVertex,
        array $forwardParent,
        array $backwardParent,
        array $forwardExplored,
        array $backwardExplored
    ): array {
        $path = [];

        // Construct path from start to intersection
        $current = $intersectionVertex;
        $forwardPath = [];
        while ($current !== null) {
            $forwardPath[] = [
                'vertex' => $current,
                'level' => $this->levels[$current]
            ];
            $current = $forwardParent[$current] ?? null;
        }
        $forwardPath = array_reverse($forwardPath);

        // Construct path from intersection to target
        $current = $backwardParent[$intersectionVertex] ?? null;
        $backwardPath = [];
        while ($current !== null) {
            $backwardPath[] = [
                'vertex' => $current,
                'level' => $this->levels[$current]
            ];
            $current = $backwardParent[$current] ?? null;
        }

        // Combine paths
        $path = array_merge($forwardPath, $backwardPath);

        return [
            'success' => true,
            'path' => $path,
            'forwardExplored' => $forwardExplored,
            'backwardExplored' => $backwardExplored,
            'intersectionVertex' => $intersectionVertex
        ];
    }

    // Add this helper method to print BDS results
    public function printBdsPath(array $result): void {
        if (!$result['success']) {
            echo "No path found between vertices!\n";
            return;
        }

        echo "\nNodes explored from start (forward direction):\n";
        foreach ($result['forwardExplored'] as $node) {
            echo sprintf("Node: %s (Level %d, Direction: %s)\n",
                $node['vertex'],
                $node['level'],
                $node['direction']
            );
        }

        echo "\nNodes explored from target (backward direction):\n";
        foreach ($result['backwardExplored'] as $node) {
            echo sprintf("Node: %s (Level %d, Direction: %s)\n",
                $node['vertex'],
                $node['level'],
                $node['direction']
            );
        }

        echo "\nFinal path found (intersection at {$result['intersectionVertex']}):\n";
        foreach ($result['path'] as $node) {
            echo sprintf("Node: %s (Level %d)\n",
                $node['vertex'],
                $node['level']
            );
        }
    }

    public function getAdjacencyList(): array {
        return $this->adjacencyList;
    }

    public function printPath(array $path): void {
        foreach ($path as $node) {
            echo sprintf("Node: %s (Level %d)\n", $node['vertex'], $node['level']);
        }
    }

    public function printUcsPath(array $result): void {
        if (!$result['success']) {
            echo "Target not found!\n";
            return;
        }

        echo "\nNodes explored during UCS (in order of exploration):\n";
        foreach ($result['explored'] as $node) {
            echo sprintf("Node: %s (Level %d, Cost %.2f)\n",
                $node['vertex'],
                $node['level'],
                $node['cost']
            );
        }

        echo "\nOptimal path found:\n";
        foreach ($result['optimalPath'] as $node) {
            echo sprintf("Node: %s (Level %d, Cost %.2f)\n",
                $node['vertex'],
                $node['level'],
                $node['cost']
            );
        }
        echo sprintf("Total Cost: %.2f\n", $result['cost']);
    }

    // Add a helper method to print random search results
    public function printRwsPath(array $result): void {
        echo sprintf("\nRandom Search %s\n",
            $result['success'] ? "found target!" : "did not find target."
        );

        echo sprintf("Total steps taken: %d/%d\n",
            $result['steps'],
            $result['maxSteps']
        );

        echo "\nPath taken:\n";
        foreach ($result['path'] as $node) {
            echo sprintf("Step %d: Node %s (Level %d, Visits: %d)\n",
                $node['step'],
                $node['vertex'],
                $node['level'],
                $node['visits'] ?? 0
            );
        }

        echo "\nVisit counts:\n";
        foreach ($result['visited'] as $vertex => $count) {
            echo sprintf("Node %s: visited %d times\n", $vertex, $count);
        }
    }

    public function searchAnalysis($searchResult): void {
        if ($searchResult === null) {
            echo "No path found!\n";
            return;
        }

        $totalCost = 0;

        echo "Path sequence:\n";
        $pathSequenceNames = array_map(function ($node) {
            $vertex = $node['vertex'] ?? $node;
            return $this->vertexLabels[$vertex] ?? $vertex;
        }, $searchResult);
        echo " -> " . implode("\n -> ", $pathSequenceNames) . "\n";

        echo "\nPath analysis:\n";
        $lastIndex = 0;
        $lastVertex = null;
        $pathSequence = array_map(function ($node) {
            $vertex = $node['vertex'] ?? $node;
            return $node['vertex'] ?? $node;
        }, $searchResult);

        foreach ($pathSequence as $index => $vertex) {
            if ($index > 0) {
                $prevVertex = $pathSequence[$index - 1];
                echo sprintf("Step %d: %s (level %d) -> %s (level %d)\n",
                    $index,
                    $prevVertex,
                    $this->levels[$prevVertex],
                    $vertex,
                    $this->levels[$vertex],
                );
            }
            $lastIndex++;
            $lastVertex = $vertex;
        }

        echo sprintf("Step %d: %s (level %d)\n",
            $lastIndex,
            $lastVertex,
            $this->levels[$vertex],
        );

        echo sprintf("\n");
    }

    // Helper method to print the adjacency list (for debugging)
    public function printGraph(): void {
        foreach ($this->adjacencyList as $vertex => $neighbors) {
            echo sprintf("%s (Level %d) -> %s\n",
                $vertex,
                $this->levels[$vertex],
                implode(', ', $neighbors)
            );
        }
    }
}