This PRD outlines the development of the "Ralph Wiggum Loop execution" feature for the Parallel Hypothesis Tester (GEN-Q-011), specifically enhancing the Hypothesis Dependency Graph (GEN-Q-111). The primary goal is to detect and manage circular dependencies (Ralph Wiggum Loops) within the hypothesis execution flow, preventing infinite loops or incorrect testing outcomes.

---

## Product Requirements Document: Ralph Wiggum Loop Execution

**Product:** Parallel Hypothesis Tester (GEN-Q-011)
**Feature:** Ralph Wiggum Loop Execution (GEN-Q-111 Enhancement)
**Version:** 1.0
**Date:** 2023-10-27

### 1. Introduction

The Parallel Hypothesis Tester relies on a robust dependency graph to orchestrate the execution of hypotheses. A critical failure mode arises when circular dependencies, or "Ralph Wiggum Loops," are introduced into this graph. This PRD details the development of a system to detect, report, and prevent execution based on such loops, ensuring the stability and correctness of the testing framework.

### 2. Goals

*   **Detect Circular Dependencies:** Accurately identify all circular dependencies within the hypothesis dependency graph.
*   **Prevent Erroneous Execution:** Block hypothesis execution when circular dependencies are detected to avoid infinite loops or undefined behavior.
*   **Provide Clear Feedback:** Inform users about detected loops, including the specific hypotheses involved, to facilitate resolution.
*   **Maintain Performance:** Ensure loop detection adds minimal overhead to the overall hypothesis testing process.

### 3. Story Breakdown

Below are 32 atomic stories, progressively building the feature, including core implementation, testing, integration, documentation, and optimization.

---

### GPM-001: Define Hypothesis DTO for Dependency Graph
**Goal:** Establish a data structure to represent a hypothesis, specifically including its dependencies, for graph construction.
**Acceptance Criteria:**
- A `Hypothesis` DTO/model exists in `core/models/hypothesis.py`.
- The `Hypothesis` DTO includes fields for `id` (unique identifier), `name`, and `dependencies` (a list of hypothesis IDs it depends on).
**Files:** `core/models/hypothesis.py`
**Spawns:** Basic graph node representation.

### GPM-002: Create Graph Node Representation
**Goal:** Implement a generic graph node class to encapsulate hypothesis data within the graph structure.
**Acceptance Criteria:**
- A `Node` class is created in `core/graph/node.py`.
- The `Node` class constructor accepts a `hypothesis_id` and optionally `data` (e.g., the `Hypothesis` DTO instance).
- The `Node` class has properties to access its `hypothesis_id`.
**Files:** `core/graph/node.py`
**Spawns:** Graph edge representation.

### GPM-003: Create Graph Edge Representation
**Goal:** Implement a generic graph edge class to represent directed dependencies between hypothesis nodes.
**Acceptance Criteria:**
- An `Edge` class is created in `core/graph/edge.py`.
- The `Edge` class constructor accepts `source_node_id` and `target_node_id`.
- The `Edge` class has properties to access its `source_node_id` and `target_node_id`.
**Files:** `core/graph/edge.py`
**Spawns:** Adjacency list graph structure.

### GPM-004: Implement Adjacency List Graph Structure
**Goal:** Set up the basic `DependencyGraph` class using an adjacency list for efficient representation of connections between hypotheses.
**Acceptance Criteria:**
- A `DependencyGraph` class is created in `core/graph/dependency_graph.py`.
- The `DependencyGraph` class internally uses a dictionary for `nodes` (mapping `id` to `Node` objects) and an adjacency list (e.g., `adj` dictionary mapping `source_id` to a list of `target_id`s).
- The constructor initializes these internal structures as empty.
**Files:** `core/graph/dependency_graph.py`
**Spawns:** Method to add nodes to the graph.

### GPM-005: Add Hypothesis to Graph
**Goal:** Implement a method within `DependencyGraph` to add a new hypothesis as a node, preventing duplicates.
**Acceptance Criteria:**
- The `DependencyGraph` class has an `add_node(hypothesis: Hypothesis)` method.
- This method adds a `Node` object to the `nodes` dictionary using the `hypothesis.id`.
- If a node with the given `hypothesis.id` already exists, the method handles it gracefully (e.g., logs a warning or does nothing).
**Files:** `core/graph/dependency_graph.py`
**Spawns:** Method to add edges to the graph.

### GPM-006: Add Dependency (Edge) to Graph
**Goal:** Implement a method within `DependencyGraph` to add a directed edge representing a dependency between two existing hypothesis nodes.
**Acceptance Criteria:**
- The `DependencyGraph` class has an `add_edge(source_id: str, target_id: str)` method.
- This method adds `target_id` to the adjacency list of `source_id`.
- If either `source_id` or `target_id` does not correspond to an existing node, the method raises an appropriate error (e.g., `ValueError`).
**Files:** `core/graph/dependency_graph.py`
**Spawns:** Initialization of DFS state tracking for cycle detection.

### GPM-007: Initialize DFS State Tracking
**Goal:** Implement data structures within a `CycleDetector` class or helper to track visited nodes and the current recursion stack for Depth-First Search (DFS).
**Acceptance Criteria:**
- A `CycleDetector` class is created in `core/graph/cycle_detector.py`.
- The `CycleDetector` constructor or a `reset_state` method initializes:
    - `_visited`: A set to store all nodes visited during the DFS.
    - `_recursion_stack`: A set to store nodes currently in the recursion path.
    - `_cycles`: A list to store detected cycle paths.
    - `_path_stack`: A list to store the current path for cycle reconstruction.
**Files:** `core/graph/cycle_detector.py`
**Spawns:** Basic recursive DFS traversal method.

### GPM-008: Basic Recursive DFS Traversal Method
**Goal:** Create a private recursive Depth-First Search method that traverses the graph, marking nodes as visited.
**Acceptance Criteria:**
- The `CycleDetector` class has a private method `_dfs(node_id: str, graph: DependencyGraph)`.
- This method marks `node_id` as visited in `_visited`.
- It iterates through the neighbors of `node_id` in the `graph`.
**Files:** `core/graph/cycle_detector.py`
**Spawns:** Logic to detect cycles during DFS.

### GPM-009: Detect Cycle During DFS Traversal
**Goal:** Implement the core logic within the DFS to identify when a back-edge (cycle) is encountered.
**Acceptance Criteria:**
- Inside `_dfs`, if a neighbor `v` is found to be in `_recursion_stack`, it signifies a cycle.
- This condition triggers the cycle detection process.
**Files:** `core/graph/cycle_detector.py`
**Spawns:** Storage of nodes in the current recursion path.

### GPM-010: Store Nodes in Current Recursion Path
**Goal:** Maintain a stack or list of nodes currently in the recursion path to enable reconstruction of detected cycles.
**Acceptance Criteria:**
- Inside `_dfs`, `node_id` is added to `_recursion_stack` and `_path_stack` upon entering the function.
- `node_id` is removed from `_recursion_stack` and `_path_stack` upon exiting the function (backtracking).
**Files:** `core/graph/cycle_detector.py`
**Spawns:** Reconstruction of the cycle path.

### GPM-011: Reconstruct and Store Detected Cycle Path
**Goal:** When a cycle is detected, extract the path of nodes forming the cycle and store it in `_cycles`.
**Acceptance Criteria:**
- When a cycle is detected (neighbor `v` in `_recursion_stack`), the `_path_stack` is used to identify the nodes involved in the cycle.
- The cycle path, starting and ending with the node that closes the loop, is extracted and appended to `_cycles`.
**Files:** `core/graph/cycle_detector.py`
**Spawns:** Public method to initiate cycle detection.

### GPM-012: Public `find_cycles` Method in Cycle Detector
**Goal:** Create a public method that orchestrates the DFS to find all cycles in the provided graph.
**Acceptance Criteria:**
- The `CycleDetector` class has a public method `find_cycles(graph: DependencyGraph) -> List[List[str]]`.
- This method initializes the DFS state, iterates through all nodes in the graph to start DFS from unvisited nodes, and returns the list of detected cycle paths.
**Files:** `core/graph/cycle_detector.py`
**Spawns:** Unit tests for cycle detection.

### GPM-013: Unit Test for Empty Graph Cycle Detection
**Goal:** Verify that `find_cycles` returns an empty list when provided with an empty graph.
**Acceptance Criteria:**
- A test case exists in `tests/unit/graph/test_cycle_detector.py`.
- Instantiating `CycleDetector` with an empty `DependencyGraph` and calling `find_cycles` returns an empty list.
**Files:** `tests/unit/graph/test_cycle_detector.py`
**Spawns:** Unit test for acyclic graph.

### GPM-014: Unit Test for Acyclic Graph Cycle Detection
**Goal:** Verify that `find_cycles` returns an empty list for a graph that contains no cycles.
**Acceptance Criteria:**
- A test case exists in `tests/unit/graph/test_cycle_detector.py`.
- A graph like A -> B -> C is constructed.
- Calling `find_cycles` on this graph returns an empty list.
**Files:** `tests/unit/graph/test_cycle_detector.py`
**Spawns:** Unit test for simple two-node cycle.

### GPM-015: Unit Test for Simple Two-Node Cycle
**Goal:** Verify the correct detection of a direct cycle involving two nodes (e.g., A -> B -> A).
**Acceptance Criteria:**
- A test case exists in `tests/unit/graph/test_cycle_detector.py`.
- A graph with a cycle A -> B -> A is constructed.
- Calling `find_cycles` detects and returns the cycle path `[A, B, A]` (or equivalent representation).
**Files:** `tests/unit/graph/test_cycle_detector.py`
**Spawns:** Unit test for multi-node cycle.

### GPM-016: Unit Test for Multi-Node Cycle
**Goal:** Verify the correct detection of a cycle involving three or more nodes (e.g., A -> B -> C -> A).
**Acceptance Criteria:**
- A test case exists in `tests/unit/graph/test_cycle_detector.py`.
- A graph with a cycle A -> B -> C -> A is constructed.
- Calling `find_cycles` detects and returns the cycle path `[A, B, C, A]` (or equivalent).
**Files:** `tests/unit/graph/test_cycle_detector.py`
**Spawns:** Unit test for self-looping hypothesis.

### GPM-017: Unit Test for Self-Looping Hypothesis
**Goal:** Verify the correct detection of a hypothesis that depends on itself (A -> A).
**Acceptance Criteria:**
- A test case exists in `tests/unit/graph/test_cycle_detector.py`.
- A graph with a self-loop A -> A is constructed.
- Calling `find_cycles` detects and returns the cycle path `[A, A]` (or equivalent).
**Files:** `tests/unit/graph/test_cycle_detector.py`
**Spawns:** Unit test for multiple independent cycles.

### GPM-018: Unit Test for Multiple Independent Cycles
**Goal:** Verify the detection of distinct cycles that do not overlap in the same graph.
**Acceptance Criteria:**
- A test case exists in `tests/unit/graph/test_cycle_detector.py`.
- A graph with two independent cycles (e.g., A -> B -> A and C -> D -> C) is constructed.
- Calling `find_cycles` detects and returns both cycle paths (order may vary).
**Files:** `tests/unit/graph/test_cycle_detector.py`
**Spawns:** Custom exception for circular dependencies.

### GPM-019: Create `CircularDependencyError` Exception
**Goal:** Define a custom exception to be raised specifically when a circular dependency is detected, allowing for specific error handling.
**Acceptance Criteria:**
- A `CircularDependencyError` class is created in `core/exceptions.py`.
- This exception inherits from a base `Exception` class (e.g., `Exception` or a custom base error for the system).
- The exception constructor accepts a message that includes the detected cycle path(s).
**Files:** `core/exceptions.py`
**Spawns:** Integration of graph builder into HypothesisManager.

### GPM-020: Integrate `DependencyGraph` Builder into `HypothesisManager`
**Goal:** Modify `HypothesisManager` to construct a `DependencyGraph` from loaded hypothesis definitions.
**Acceptance Criteria:**
- The `HypothesisManager` class in `core/hypothesis_manager.py` has a method (e.g., `_build_dependency_graph`) that takes a list of `Hypothesis` DTOs.
- This method uses `DependencyGraph.add_node` and `DependencyGraph.add_edge` to populate the graph based on the `dependencies` field of each hypothesis.
- `HypothesisManager`'s `load_hypotheses` or similar method calls `_build_dependency_graph` after loading.
**Files:** `core/hypothesis_manager.py`
**Spawns:** Introduction of a dedicated loop detection service.

### GPM-021: Introduce `LoopDetectionService`
**Goal:** Create a service that encapsulates the logic for orchestrating `DependencyGraph` construction and `CycleDetector` usage.
**Acceptance Criteria:**
- A `LoopDetectionService` class is created in `core/services/loop_detection_service.py`.
- This service has a public method `detect_loops(hypotheses: List[Hypothesis]) -> List[List[str]]`.
- This method internally uses `HypothesisManager`'s graph building logic (or duplicates it for separation of concerns) and `CycleDetector` to find loops.
**Files:** `core/services/loop_detection_service.py`
**Spawns:** The service raising `CircularDependencyError`.

### GPM-022: `LoopDetectionService` Raises `CircularDependencyError`
**Goal:** Configure the `LoopDetectionService` to raise the custom `CircularDependencyError` if any cycles are found.
**Acceptance Criteria:**
- The `LoopDetectionService.detect_loops` method checks if any cycles were returned by the `CycleDetector`.
- If cycles are found, it raises a `CircularDependencyError` with a message detailing the detected loops.
**Files:** `core/services/loop_detection_service.py`
**Spawns:** Pre-execution loop check in HypothesisExecutor.

### GPM-023: `HypothesisExecutor` Pre-Execution Loop Check
**Goal:** Modify `HypothesisExecutor` to invoke `LoopDetectionService` before initiating any hypothesis execution.
**Acceptance Criteria:**
- The `HypothesisExecutor` class in `core/hypothesis_executor.py` has its `execute_all()` or similar entry point modified.
- Before starting actual hypothesis execution, it instantiates and calls `LoopDetectionService.detect_loops` with the relevant hypothesis list.
**Files:** `core/hypothesis_executor.py`
**Spawns:** HypothesisExecutor handling the raised error.

### GPM-024: `HypothesisExecutor` Handles `CircularDependencyError`
**Goal:** Implement a mechanism within `HypothesisExecutor` to gracefully catch and log `CircularDependencyError`, preventing execution.
**Acceptance Criteria:**
- The `execute_all()` method in `HypothesisExecutor` includes a try-except block.
- It catches `CircularDependencyError`.
- Upon catching, it logs the error message (including cycle details) and exits gracefully without proceeding to execute any hypotheses.
**Files:** `core/hypothesis_executor.py`
**Spawns:** Full system integration test for loop detection.

### GPM-025: Integration Test: Full System Loop Detection
**Goal:** Verify that a full workflow (loading hypotheses, building graph, detecting loop, preventing execution) works as expected.
**Acceptance Criteria:**
- An integration test file `tests/integration/test_full_loop_detection.py` is created.
- This test defines a set of hypothesis configurations, including one or more with circular dependencies.
- It attempts to run the `HypothesisExecutor`.
- The test asserts that `CircularDependencyError` is raised and handled, and no actual hypothesis execution occurs.
- The system logs contain the expected error message with cycle details.
**Files:** `tests/integration/test_full_loop_detection.py`
**Spawns:** Documentation for the new error.

### GPM-026: Document `CircularDependencyError` and Resolution
**Goal:** Add documentation explaining the `CircularDependencyError`, its cause, and how users can resolve it.
**Acceptance Criteria:**
- A new section or entry is added to `docs/error_handling.md` (or similar documentation).
- This section describes `CircularDependencyError`, provides examples of problematic dependency configurations, and suggests steps for users to fix them.
**Files:** `docs/error_handling.md`
**Spawns:** API documentation for dependency graph.

### GPM-027: Update `HypothesisManager` API Documentation for Dependencies
**Goal:** Document the new `dependencies` field in hypothesis definitions and its impact on graph construction and execution.
**Acceptance Criteria:**
- The API documentation for `HypothesisManager` in `docs/api/hypothesis_manager.md` (or relevant file) is updated.
- This update details how to specify hypothesis dependencies and explains the role of the dependency graph.
**Files:** `docs/api/hypothesis_manager.md`
**Spawns:** Configuration options for loop detection.

### GPM-028: Add Configuration Option for Loop Detection Behavior
**Goal:** Introduce a configuration setting to allow users to enable/disable loop detection or choose its behavior (e.g., block execution, warn only).
**Acceptance Criteria:**
- A new section `loop_detection` is added to `config/system_settings.py` (or similar configuration file).
- This section includes:
    - `enabled`: A boolean (default `True`) to enable/disable the feature.
    - `on_found`: An enum-like setting (`'block'` or `'warn'`) to determine if execution should be blocked or just a warning issued.
- `LoopDetectionService` respects these settings.
**Files:** `config/system_settings.py`
**Spawns:** README update.

### GPM-029: README Update for Dependency Graph Feature
**Goal:** Add a section to the main README explaining the new dependency graph feature and its loop detection capabilities.
**Acceptance Criteria:**
- A new section titled "Hypothesis Dependencies & Loop Detection" is added to `README.md`.
- This section provides a high-level overview of how to define dependencies and what happens if a loop is detected.
- It references the more detailed documentation for error handling and API usage.
**Files:** `README.md`
**Spawns:** Optimization for early exit.

### GPM-030: Implement Early Exit for First Cycle Found
**Goal:** Optimize `CycleDetector` to stop searching and return immediately after the first cycle is identified, if desired, to save computation time.
**Acceptance Criteria:**
- The `CycleDetector.find_cycles` method has an optional parameter `return_first_cycle_only` (default `False`).
- If `return_first_cycle_only` is `True`, the method returns a list containing only the first cycle found, ceasing further graph traversal for cycles.
**Files:** `core/graph/cycle_detector.py`
**Spawns:** Caching of the dependency graph.

### GPM-031: Cache Dependency Graph for Performance
**Goal:** Implement caching of the constructed `DependencyGraph` within `HypothesisManager` to avoid rebuilding it on every check if hypothesis definitions haven't changed.
**Acceptance Criteria:**
- `HypothesisManager` stores a private attribute `_cached_dependency_graph` and a `_last_hypotheses_hash` (or similar version tracking).
- The `_build_dependency_graph` method checks if the current set of hypothesis definitions has changed since the last build.
- If no changes, it returns the `_cached_dependency_graph`; otherwise, it rebuilds and updates the cache.
**Files:** `core/hypothesis_manager.py`
**Spawns:** Performance benchmark for cycle detection.

### GPM-032: Performance Benchmark for Cycle Detection
**Goal:** Add a performance test to measure the time taken for cycle detection on graphs of varying sizes to ensure efficiency.
**Acceptance Criteria:**
- A performance test file `tests/performance/test_cycle_detection_perf.py` is created.
- This test includes benchmarks for `CycleDetector.find_cycles` on:
    - A graph with N nodes and M edges (e.g., N=1000, M=2000) with no cycles.
    - A similar-sized graph containing a few cycles.
- The test uses a profiling tool or time measurement to report execution duration.
**Files:** `tests/performance/test_cycle_detection_perf.py`