Uninformed (Blind) Search

Iterative Deepening Depth-First Search (IDDFS)

The Iterative Deepening Depth-First Search (IDDFS) algorithm combines the strengths of two fundamental search algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS). This hybrid approach balances memory efficiency with optimality by progressively exploring deeper levels of the search space. Unlike traditional DFS, which dives to the maximum depth at once, or BFS, which requires significant memory to maintain a queue of explored nodes, IDDFS systematically increases the search depth, ensuring thorough exploration while minimizing resource usage.
Example of class UninformedSearchGraph (with IDDFS 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)
            );
        }
    }
}