reasonkit-core 0.1.8

//! # Graph-of-Thought (GoT) Module - DAG-Based Reasoning
//!
//! Implements Graph-of-Thought reasoning as described in Besta et al. (2023) from ETH Zurich.
//! This module enables non-linear reasoning through directed acyclic graphs (DAGs), allowing
//! for branching, aggregation, and refinement of thought paths.
//!
//! ## Scientific Foundation
//!
//! Based on:
//! - **Besta et al. (2023)**: "Graph of Thoughts: Solving Elaborate Problems with Large
//!   Language Models" - ETH Zurich. Introduces the GoT framework for LLM reasoning.
//! - **Yao et al. (2023)**: "Tree of Thoughts: Deliberate Problem Solving with Large
//!   Language Models" - Extends CoT to tree structures; GoT generalizes further to DAGs.
//!
//! ## Key Concepts
//!
//! - **Thought Node**: A unit of reasoning with state, score, and validity
//! - **Graph Operations**: Generate, Aggregate, Refine, Score, KeepBestN, Backtrack
//! - **DAG Structure**: Non-linear reasoning allowing thought merging and branching
//!
//! ## Usage
//!
//! ```rust,ignore
//! use reasonkit::thinktool::modules::{GraphOfThought, GoTConfig, ThinkToolModule, ThinkToolContext};
//!
//! // Default configuration
//! let got = GraphOfThought::new();
//!
//! // Custom configuration
//! let got = GraphOfThought::with_config(GoTConfig {
//!     max_branches: 6,
//!     enable_aggregation: true,
//!     enable_refinement: true,
//!     max_refinement_rounds: 5,
//!     backtrack_threshold: 0.25,
//!     min_confidence: 0.80,
//! });
//!
//! let context = ThinkToolContext::new("Solve: What is the optimal strategy for X?");
//! let result = got.execute(&context)?;
//! ```
//!
//! ## Module Shortcut
//!
//! This module can be referenced with the shortcut code `got` in protocol execution.

use std::collections::HashMap;
use std::future::Future;
use std::pin::Pin;

use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::visit::Dfs;
use serde::{Deserialize, Serialize};
use serde_json::json;
use thiserror::Error;

use super::{ThinkToolContext, ThinkToolModule, ThinkToolModuleConfig, ThinkToolOutput};
use crate::error::{Error, Result};

// ============================================================================
// ERROR TYPES
// ============================================================================

/// Errors specific to Graph-of-Thought module execution
#[derive(Error, Debug, Clone)]
pub enum GraphOfThoughtError {
    /// Graph construction failed
    #[error("Graph construction failed: {reason}")]
    GraphConstructionFailed { reason: String },

    /// Invalid operation on the reasoning graph
    #[error("Invalid graph operation: {operation}")]
    InvalidOperation { operation: String },

    /// Maximum depth exceeded
    #[error("Maximum graph depth exceeded: {depth} > {max_depth}")]
    MaxDepthExceeded { depth: usize, max_depth: usize },

    /// No valid thoughts generated
    #[error("No valid thoughts generated after {attempts} attempts")]
    NoValidThoughts { attempts: usize },

    /// Aggregation failed
    #[error("Aggregation failed: {reason}")]
    AggregationFailed { reason: String },

    /// Refinement exceeded maximum rounds
    #[error("Refinement exceeded maximum rounds: {rounds} > {max_rounds}")]
    RefinementExceeded { rounds: usize, max_rounds: usize },

    /// Backtrack target not found
    #[error("Backtrack target not found: node {node_id}")]
    BacktrackTargetNotFound { node_id: u64 },

    /// Confidence too low after processing
    #[error("Final confidence too low: {confidence:.2} < {threshold:.2}")]
    LowConfidence { confidence: f64, threshold: f64 },

    /// Query validation failed
    #[error("Query validation failed: {reason}")]
    QueryValidationFailed { reason: String },
}

impl From<GraphOfThoughtError> for Error {
    fn from(err: GraphOfThoughtError) -> Self {
        Error::ThinkToolExecutionError(err.to_string())
    }
}

// ============================================================================
// CONFIGURATION
// ============================================================================

/// Configuration for Graph-of-Thought module behavior
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GoTConfig {
    /// Maximum number of branches to generate at each node
    pub max_branches: usize,

    /// Enable aggregation operations (merging multiple thoughts)
    pub enable_aggregation: bool,

    /// Enable refinement operations (iterative improvement)
    pub enable_refinement: bool,

    /// Maximum rounds of refinement per thought
    pub max_refinement_rounds: usize,

    /// Score threshold below which backtracking is triggered
    pub backtrack_threshold: f64,

    /// Minimum confidence required for final output
    pub min_confidence: f64,

    /// Maximum depth of the reasoning graph
    pub max_depth: usize,

    /// Enable automatic pruning of low-scoring branches
    pub auto_prune: bool,

    /// Keep top N thoughts during pruning (0 = keep all above threshold)
    pub keep_top_n: usize,

    /// Enable cycle detection and prevention
    pub prevent_cycles: bool,

    /// Maximum total nodes in the graph
    pub max_nodes: usize,

    /// Minimum query length in characters
    pub min_query_length: usize,

    /// Maximum query length in characters
    pub max_query_length: usize,

    /// Enable verbose logging of operations
    pub verbose: bool,
}

impl Default for GoTConfig {
    fn default() -> Self {
        Self {
            max_branches: 4,
            enable_aggregation: true,
            enable_refinement: true,
            max_refinement_rounds: 3,
            backtrack_threshold: 0.3,
            min_confidence: 0.75,
            max_depth: 10,
            auto_prune: true,
            keep_top_n: 5,
            prevent_cycles: true,
            max_nodes: 100,
            min_query_length: 10,
            max_query_length: 5000,
            verbose: false,
        }
    }
}

impl GoTConfig {
    /// Quick configuration for fast reasoning with limited branching
    pub fn quick() -> Self {
        Self {
            max_branches: 2,
            enable_aggregation: false,
            enable_refinement: false,
            max_refinement_rounds: 1,
            backtrack_threshold: 0.4,
            min_confidence: 0.65,
            max_depth: 5,
            auto_prune: true,
            keep_top_n: 3,
            prevent_cycles: true,
            max_nodes: 30,
            min_query_length: 5,
            max_query_length: 2000,
            verbose: false,
        }
    }

    /// Deep configuration for thorough exploration
    pub fn deep() -> Self {
        Self {
            max_branches: 6,
            enable_aggregation: true,
            enable_refinement: true,
            max_refinement_rounds: 5,
            backtrack_threshold: 0.25,
            min_confidence: 0.80,
            max_depth: 15,
            auto_prune: true,
            keep_top_n: 8,
            prevent_cycles: true,
            max_nodes: 200,
            min_query_length: 10,
            max_query_length: 10000,
            verbose: true,
        }
    }

    /// Paranoid configuration for maximum rigor
    pub fn paranoid() -> Self {
        Self {
            max_branches: 8,
            enable_aggregation: true,
            enable_refinement: true,
            max_refinement_rounds: 7,
            backtrack_threshold: 0.35,
            min_confidence: 0.90,
            max_depth: 20,
            auto_prune: true,
            keep_top_n: 10,
            prevent_cycles: true,
            max_nodes: 500,
            min_query_length: 10,
            max_query_length: 10000,
            verbose: true,
        }
    }
}

// ============================================================================
// THOUGHT NODE
// ============================================================================

/// A node in the reasoning graph representing a single thought or reasoning step
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ThoughtNode {
    /// Unique identifier for this thought node
    pub id: u64,

    /// State as key-value pairs (flexible reasoning state)
    pub state: HashMap<String, serde_json::Value>,

    /// Quality/confidence score for this thought (0.0 - 1.0)
    pub score: Option<f64>,

    /// Whether this thought passed validation
    pub valid: Option<bool>,

    /// The reasoning step or content of this thought
    pub reasoning_step: String,

    /// Child node IDs in the graph
    pub children: Vec<u64>,

    /// Parent node IDs (for DAG structure with multiple parents via aggregation)
    pub parents: Vec<u64>,

    /// Depth in the graph from the root
    pub depth: usize,

    /// Tags for categorizing thoughts
    pub tags: Vec<String>,

    /// Metadata about creation and processing
    pub metadata: ThoughtMetadata,
}

/// Metadata for a thought node
#[derive(Debug, Clone, Serialize, Deserialize, Default)]
pub struct ThoughtMetadata {
    /// Creation timestamp (milliseconds since epoch)
    pub created_at: u64,

    /// Operation that created this node
    pub created_by: Option<String>,

    /// Number of times this thought was refined
    pub refinement_count: usize,

    /// If aggregated, IDs of source thoughts
    pub aggregated_from: Vec<u64>,

    /// Processing time in milliseconds
    pub processing_time_ms: Option<u64>,
}

impl ThoughtNode {
    /// Create a new thought node with the given ID and reasoning step
    pub fn new(id: u64, reasoning_step: impl Into<String>) -> Self {
        Self {
            id,
            state: HashMap::new(),
            score: None,
            valid: None,
            reasoning_step: reasoning_step.into(),
            children: Vec::new(),
            parents: Vec::new(),
            depth: 0,
            tags: Vec::new(),
            metadata: ThoughtMetadata {
                created_at: std::time::SystemTime::now()
                    .duration_since(std::time::UNIX_EPOCH)
                    .map(|d| d.as_millis() as u64)
                    .unwrap_or(0),
                ..Default::default()
            },
        }
    }

    /// Builder: set state value
    pub fn with_state(mut self, key: impl Into<String>, value: serde_json::Value) -> Self {
        self.state.insert(key.into(), value);
        self
    }

    /// Builder: set score
    pub fn with_score(mut self, score: f64) -> Self {
        self.score = Some(score.clamp(0.0, 1.0));
        self
    }

    /// Builder: set validity
    pub fn with_valid(mut self, valid: bool) -> Self {
        self.valid = Some(valid);
        self
    }

    /// Builder: set depth
    pub fn with_depth(mut self, depth: usize) -> Self {
        self.depth = depth;
        self
    }

    /// Builder: add parent
    pub fn with_parent(mut self, parent_id: u64) -> Self {
        if !self.parents.contains(&parent_id) {
            self.parents.push(parent_id);
        }
        self
    }

    /// Builder: add tag
    pub fn with_tag(mut self, tag: impl Into<String>) -> Self {
        self.tags.push(tag.into());
        self
    }

    /// Add a child node ID
    pub fn add_child(&mut self, child_id: u64) {
        if !self.children.contains(&child_id) {
            self.children.push(child_id);
        }
    }

    /// Check if this thought is scored
    pub fn is_scored(&self) -> bool {
        self.score.is_some()
    }

    /// Check if this thought is validated
    pub fn is_validated(&self) -> bool {
        self.valid.is_some()
    }

    /// Check if this thought is valid and above a score threshold
    pub fn is_viable(&self, threshold: f64) -> bool {
        self.valid.unwrap_or(true) && self.score.unwrap_or(0.5) >= threshold
    }

    /// Get the effective score (defaults to 0.5 if unscored)
    pub fn effective_score(&self) -> f64 {
        self.score.unwrap_or(0.5)
    }
}

// ============================================================================
// GRAPH OPERATIONS
// ============================================================================

/// Operations that can be performed on the reasoning graph
#[derive(Debug, Clone, Serialize, Deserialize)]
pub enum GraphOp {
    /// Generate k new thought branches from the current frontier
    Generate {
        /// Number of branches to generate
        k: usize,
    },

    /// Aggregate multiple thoughts into a single synthesized thought
    Aggregate {
        /// IDs of source thoughts to aggregate
        source_ids: Vec<u64>,
    },

    /// Refine a thought through iterative improvement
    Refine {
        /// Maximum iterations for refinement
        max_iterations: usize,
    },

    /// Score all unscored thoughts in the graph
    Score,

    /// Keep only the best N thoughts, pruning the rest
    KeepBestN {
        /// Number of top thoughts to keep
        n: usize,
    },

    /// Backtrack to a previous thought node
    Backtrack {
        /// Target node ID to backtrack to
        to_id: u64,
    },
}

impl GraphOp {
    /// Get a description of this operation
    pub fn description(&self) -> String {
        match self {
            Self::Generate { k } => format!("Generate {} new thought branches", k),
            Self::Aggregate { source_ids } => {
                format!("Aggregate {} thoughts into one", source_ids.len())
            }
            Self::Refine { max_iterations } => {
                format!("Refine with up to {} iterations", max_iterations)
            }
            Self::Score => "Score all unscored thoughts".to_string(),
            Self::KeepBestN { n } => format!("Keep best {} thoughts", n),
            Self::Backtrack { to_id } => format!("Backtrack to node {}", to_id),
        }
    }
}

/// Record of an executed operation
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ExecutedOperation {
    /// The operation that was executed
    pub operation: GraphOp,

    /// Whether the operation succeeded
    pub success: bool,

    /// Nodes affected by this operation
    pub affected_nodes: Vec<u64>,

    /// Duration in milliseconds
    pub duration_ms: u64,

    /// Any notes or logs from execution
    pub notes: String,
}

// ============================================================================
// RESULT STRUCTURE
// ============================================================================

/// Complete Graph-of-Thought analysis result
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GoTResult {
    /// The original query
    pub query: String,

    /// Final selected/synthesized thoughts
    pub final_thoughts: Vec<ThoughtNode>,

    /// The complete reasoning graph (serializable representation)
    pub reasoning_graph: ReasoningGraphData,

    /// Operations that were executed
    pub operations_executed: Vec<ExecutedOperation>,

    /// Total nodes explored during reasoning
    pub total_nodes_explored: usize,

    /// Number of branches that were pruned
    pub pruned_branches: usize,

    /// Overall confidence in the result
    pub confidence: f64,

    /// Additional metadata
    pub metadata: GoTMetadata,
}

/// Serializable representation of the reasoning graph
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ReasoningGraphData {
    /// All nodes in the graph
    pub nodes: Vec<ThoughtNode>,

    /// Edges as (from_id, to_id) pairs
    pub edges: Vec<(u64, u64)>,

    /// Root node ID
    pub root_id: u64,

    /// IDs of leaf nodes (current frontier)
    pub leaf_ids: Vec<u64>,

    /// Maximum depth reached
    pub max_depth: usize,
}

/// Metadata about the GoT execution
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GoTMetadata {
    /// Module version
    pub version: String,

    /// Total execution duration in milliseconds
    pub duration_ms: u64,

    /// Configuration used
    pub config: GoTConfig,

    /// Number of generate operations
    pub generate_count: usize,

    /// Number of aggregate operations
    pub aggregate_count: usize,

    /// Number of refine operations
    pub refine_count: usize,

    /// Number of backtrack operations
    pub backtrack_count: usize,
}

// ============================================================================
// REASONING GRAPH
// ============================================================================

/// Internal representation of the reasoning graph using petgraph
struct ReasoningGraph {
    /// The petgraph DAG structure
    graph: DiGraph<ThoughtNode, ()>,

    /// Map from thought ID to graph node index
    id_to_index: HashMap<u64, NodeIndex>,

    /// Next available thought ID
    next_id: u64,

    /// Root node index
    root: Option<NodeIndex>,

    /// Current frontier (leaf nodes for expansion)
    frontier: Vec<NodeIndex>,
}

impl ReasoningGraph {
    /// Create a new empty reasoning graph
    fn new() -> Self {
        Self {
            graph: DiGraph::new(),
            id_to_index: HashMap::new(),
            next_id: 1,
            root: None,
            frontier: Vec::new(),
        }
    }

    /// Add a root thought node
    fn add_root(&mut self, reasoning_step: impl Into<String>) -> u64 {
        let id = self.next_id;
        self.next_id += 1;

        let node = ThoughtNode::new(id, reasoning_step).with_depth(0);
        let index = self.graph.add_node(node);
        self.id_to_index.insert(id, index);
        self.root = Some(index);
        self.frontier = vec![index];

        id
    }

    /// Add a child thought to a parent node
    fn add_child(&mut self, parent_id: u64, reasoning_step: impl Into<String>) -> Result<u64> {
        // Copy the index to avoid borrow conflicts
        let parent_index = *self.id_to_index.get(&parent_id).ok_or_else(|| {
            GraphOfThoughtError::InvalidOperation {
                operation: format!("Parent node {} not found", parent_id),
            }
        })?;

        let parent_depth = self.graph[parent_index].depth;
        let id = self.next_id;
        self.next_id += 1;

        let node = ThoughtNode::new(id, reasoning_step)
            .with_depth(parent_depth + 1)
            .with_parent(parent_id);

        let index = self.graph.add_node(node);
        self.id_to_index.insert(id, index);

        // Add edge from parent to child
        self.graph.add_edge(parent_index, index, ());

        // Update parent's children list
        self.graph[parent_index].add_child(id);

        // Update frontier
        self.frontier.retain(|&i| i != parent_index);
        self.frontier.push(index);

        Ok(id)
    }

    /// Aggregate multiple thoughts into a new synthesized thought
    fn aggregate(&mut self, source_ids: &[u64], reasoning_step: impl Into<String>) -> Result<u64> {
        if source_ids.is_empty() {
            return Err(GraphOfThoughtError::AggregationFailed {
                reason: "No source nodes to aggregate".to_string(),
            }
            .into());
        }

        // Find max depth among sources
        let max_depth = source_ids
            .iter()
            .filter_map(|id| self.id_to_index.get(id))
            .map(|idx| self.graph[*idx].depth)
            .max()
            .unwrap_or(0);

        let id = self.next_id;
        self.next_id += 1;

        let mut node = ThoughtNode::new(id, reasoning_step).with_depth(max_depth + 1);
        node.metadata.aggregated_from = source_ids.to_vec();
        node.metadata.created_by = Some("Aggregate".to_string());
        node.parents = source_ids.to_vec();

        let index = self.graph.add_node(node);
        self.id_to_index.insert(id, index);

        // Add edges from all source nodes to the aggregated node
        for source_id in source_ids {
            if let Some(&source_index) = self.id_to_index.get(source_id) {
                self.graph.add_edge(source_index, index, ());
                self.graph[source_index].add_child(id);
            }
        }

        // Update frontier
        for source_id in source_ids {
            if let Some(&source_index) = self.id_to_index.get(source_id) {
                self.frontier.retain(|&i| i != source_index);
            }
        }
        self.frontier.push(index);

        Ok(id)
    }

    /// Get a thought node by ID
    fn get(&self, id: u64) -> Option<&ThoughtNode> {
        self.id_to_index.get(&id).map(|idx| &self.graph[*idx])
    }

    /// Get a mutable thought node by ID
    fn get_mut(&mut self, id: u64) -> Option<&mut ThoughtNode> {
        self.id_to_index
            .get(&id)
            .copied()
            .map(|idx| &mut self.graph[idx])
    }

    /// Get all nodes in the graph
    fn all_nodes(&self) -> Vec<&ThoughtNode> {
        self.graph.node_weights().collect()
    }

    /// Get frontier node IDs
    fn frontier_ids(&self) -> Vec<u64> {
        self.frontier
            .iter()
            .map(|idx| self.graph[*idx].id)
            .collect()
    }

    /// Get the maximum depth in the graph
    fn max_depth(&self) -> usize {
        self.graph
            .node_weights()
            .map(|n| n.depth)
            .max()
            .unwrap_or(0)
    }

    /// Get total node count
    fn node_count(&self) -> usize {
        self.graph.node_count()
    }

    /// Prune nodes below a score threshold, keeping at least min_keep nodes
    fn prune(&mut self, threshold: f64, min_keep: usize) -> usize {
        // Collect nodes to potentially remove
        let mut scored_nodes: Vec<(NodeIndex, f64)> = self
            .frontier
            .iter()
            .filter_map(|&idx| {
                let node = &self.graph[idx];
                node.score.map(|s| (idx, s))
            })
            .collect();

        // Sort by score descending
        scored_nodes.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));

        // Determine which nodes to keep
        let keep_indices: std::collections::HashSet<NodeIndex> = scored_nodes
            .iter()
            .enumerate()
            .filter(|(i, (_, score))| *i < min_keep || *score >= threshold)
            .map(|(_, (idx, _))| *idx)
            .collect();

        // Remove nodes not in keep set
        let to_remove: Vec<NodeIndex> = self
            .frontier
            .iter()
            .filter(|idx| !keep_indices.contains(idx))
            .copied()
            .collect();

        let removed_count = to_remove.len();

        for idx in to_remove {
            // Remove from frontier
            self.frontier.retain(|&i| i != idx);

            // Remove from id_to_index
            let id = self.graph[idx].id;
            self.id_to_index.remove(&id);

            // Note: We don't actually remove from petgraph to preserve structure
            // Instead we mark as pruned
            self.graph[idx].valid = Some(false);
            self.graph[idx].tags.push("pruned".to_string());
        }

        removed_count
    }

    /// Check for cycles (should not exist in a DAG)
    #[allow(dead_code)]
    fn has_cycle(&self) -> bool {
        petgraph::algo::is_cyclic_directed(&self.graph)
    }

    /// Convert to serializable data structure
    fn to_data(&self) -> ReasoningGraphData {
        let nodes: Vec<ThoughtNode> = self.graph.node_weights().cloned().collect();

        let edges: Vec<(u64, u64)> = self
            .graph
            .edge_indices()
            .filter_map(|e| {
                let (a, b) = self.graph.edge_endpoints(e)?;
                Some((self.graph[a].id, self.graph[b].id))
            })
            .collect();

        let root_id = self.root.map(|idx| self.graph[idx].id).unwrap_or(0);

        let leaf_ids = self.frontier_ids();

        let max_depth = self.max_depth();

        ReasoningGraphData {
            nodes,
            edges,
            root_id,
            leaf_ids,
            max_depth,
        }
    }

    /// Perform DFS traversal and collect nodes
    #[allow(dead_code)]
    fn dfs_collect(&self) -> Vec<u64> {
        let mut result = Vec::new();
        if let Some(root) = self.root {
            let mut dfs = Dfs::new(&self.graph, root);
            while let Some(idx) = dfs.next(&self.graph) {
                result.push(self.graph[idx].id);
            }
        }
        result
    }
}

// ============================================================================
// ASYNC TRAIT
// ============================================================================

/// Trait for async ThinkTool execution
pub trait AsyncThinkToolModule: ThinkToolModule {
    /// Execute the module asynchronously
    fn execute_async<'a>(
        &'a self,
        context: &'a ThinkToolContext,
    ) -> Pin<Box<dyn Future<Output = Result<ThinkToolOutput>> + Send + 'a>>;
}

// ============================================================================
// GRAPH OF THOUGHT MODULE
// ============================================================================

/// Graph-of-Thought reasoning module for DAG-based problem solving.
///
/// Implements the GoT framework from ETH Zurich (Besta et al., 2023) for
/// non-linear reasoning with branching, aggregation, and refinement.
///
/// ## Key Features
///
/// - **Branching**: Generate multiple thought paths simultaneously
/// - **Aggregation**: Merge insights from multiple paths into synthesized conclusions
/// - **Refinement**: Iteratively improve thoughts through feedback loops
/// - **Backtracking**: Return to earlier states when reasoning paths fail
/// - **Pruning**: Automatically remove low-quality branches
///
/// ## Module Shortcut: `got`
pub struct GraphOfThought {
    /// Module configuration
    module_config: ThinkToolModuleConfig,

    /// GoT-specific configuration
    config: GoTConfig,
}

impl Default for GraphOfThought {
    fn default() -> Self {
        Self::new()
    }
}

impl GraphOfThought {
    /// Create a new Graph-of-Thought module with default configuration
    pub fn new() -> Self {
        Self::with_config(GoTConfig::default())
    }

    /// Create with custom configuration
    pub fn with_config(config: GoTConfig) -> Self {
        Self {
            module_config: ThinkToolModuleConfig {
                name: "GraphOfThought".to_string(),
                version: "1.0.0".to_string(),
                description:
                    "DAG-based reasoning with branching, aggregation, and refinement (Besta et al. 2023)"
                        .to_string(),
                confidence_weight: 0.25,
            },
            config,
        }
    }

    /// Get the GoT configuration
    pub fn got_config(&self) -> &GoTConfig {
        &self.config
    }

    /// Validate the input query
    fn validate_query(&self, query: &str) -> Result<()> {
        let length = query.len();

        if length < self.config.min_query_length {
            return Err(GraphOfThoughtError::QueryValidationFailed {
                reason: format!(
                    "Query too short: {} characters, minimum required is {}",
                    length, self.config.min_query_length
                ),
            }
            .into());
        }

        if length > self.config.max_query_length {
            return Err(GraphOfThoughtError::QueryValidationFailed {
                reason: format!(
                    "Query too long: {} characters, maximum allowed is {}",
                    length, self.config.max_query_length
                ),
            }
            .into());
        }

        Ok(())
    }

    /// Execute the Graph-of-Thought reasoning process
    fn run_reasoning(&self, query: &str) -> Result<GoTResult> {
        let start = std::time::Instant::now();

        let mut graph = ReasoningGraph::new();
        let mut operations_executed: Vec<ExecutedOperation> = Vec::new();
        let mut pruned_count = 0;
        let mut generate_count = 0;
        let mut aggregate_count = 0;
        let mut refine_count = 0;
        let mut backtrack_count = 0;

        // Step 1: Create root node from query
        let root_id = graph.add_root(format!("Initial analysis of: {}", query));

        // Step 2: Generate initial thought branches
        let op_start = std::time::Instant::now();
        let mut generated_ids =
            self.generate_thoughts(&mut graph, root_id, self.config.max_branches)?;
        operations_executed.push(ExecutedOperation {
            operation: GraphOp::Generate {
                k: self.config.max_branches,
            },
            success: true,
            affected_nodes: generated_ids.clone(),
            duration_ms: op_start.elapsed().as_millis() as u64,
            notes: format!("Generated {} initial branches", generated_ids.len()),
        });
        generate_count += 1;

        // Step 3: Score all thoughts
        let op_start = std::time::Instant::now();
        let scored_ids = self.score_thoughts(&mut graph)?;
        operations_executed.push(ExecutedOperation {
            operation: GraphOp::Score,
            success: true,
            affected_nodes: scored_ids.clone(),
            duration_ms: op_start.elapsed().as_millis() as u64,
            notes: format!("Scored {} thoughts", scored_ids.len()),
        });

        // Step 4: Iterative reasoning loop
        let mut iteration = 0;
        let max_iterations = self.config.max_depth.min(5);

        while iteration < max_iterations && graph.node_count() < self.config.max_nodes {
            iteration += 1;

            // Check for low-scoring frontier nodes - backtrack if needed
            let frontier_ids = graph.frontier_ids();
            let low_scorers: Vec<u64> = frontier_ids
                .iter()
                .filter(|&&id| {
                    graph
                        .get(id)
                        .map(|n| n.effective_score() < self.config.backtrack_threshold)
                        .unwrap_or(false)
                })
                .copied()
                .collect();

            if !low_scorers.is_empty() && backtrack_count < 3 {
                // Find best ancestor to backtrack to
                if let Some(best_ancestor) = self.find_best_backtrack_target(&graph, &low_scorers) {
                    let op_start = std::time::Instant::now();
                    self.backtrack(&mut graph, best_ancestor)?;
                    operations_executed.push(ExecutedOperation {
                        operation: GraphOp::Backtrack {
                            to_id: best_ancestor,
                        },
                        success: true,
                        affected_nodes: vec![best_ancestor],
                        duration_ms: op_start.elapsed().as_millis() as u64,
                        notes: format!("Backtracked to node {} due to low scores", best_ancestor),
                    });
                    backtrack_count += 1;
                    continue;
                }
            }

            // Prune low-scoring branches if auto-prune enabled
            if self.config.auto_prune {
                let op_start = std::time::Instant::now();
                let pruned = graph.prune(self.config.backtrack_threshold, self.config.keep_top_n);
                if pruned > 0 {
                    operations_executed.push(ExecutedOperation {
                        operation: GraphOp::KeepBestN {
                            n: self.config.keep_top_n,
                        },
                        success: true,
                        affected_nodes: vec![],
                        duration_ms: op_start.elapsed().as_millis() as u64,
                        notes: format!("Pruned {} low-scoring branches", pruned),
                    });
                    pruned_count += pruned;
                }
            }

            // Generate more thoughts from top performers
            let top_frontier: Vec<u64> = graph
                .frontier_ids()
                .into_iter()
                .filter(|&id| {
                    graph
                        .get(id)
                        .map(|n| n.is_viable(self.config.backtrack_threshold))
                        .unwrap_or(false)
                })
                .take(2)
                .collect();

            for parent_id in top_frontier {
                if graph.node_count() >= self.config.max_nodes {
                    break;
                }

                let op_start = std::time::Instant::now();
                let new_ids = self.generate_thoughts(&mut graph, parent_id, 2)?;
                generated_ids.extend(new_ids.clone());
                operations_executed.push(ExecutedOperation {
                    operation: GraphOp::Generate { k: 2 },
                    success: true,
                    affected_nodes: new_ids,
                    duration_ms: op_start.elapsed().as_millis() as u64,
                    notes: format!("Generated branches from node {}", parent_id),
                });
                generate_count += 1;
            }

            // Score new thoughts
            let op_start = std::time::Instant::now();
            let newly_scored = self.score_thoughts(&mut graph)?;
            if !newly_scored.is_empty() {
                operations_executed.push(ExecutedOperation {
                    operation: GraphOp::Score,
                    success: true,
                    affected_nodes: newly_scored.clone(),
                    duration_ms: op_start.elapsed().as_millis() as u64,
                    notes: format!("Scored {} new thoughts", newly_scored.len()),
                });
            }

            // Try aggregation if enabled and we have multiple good paths
            if self.config.enable_aggregation && iteration >= 2 {
                let good_frontier: Vec<u64> = graph
                    .frontier_ids()
                    .into_iter()
                    .filter(|&id| {
                        graph
                            .get(id)
                            .map(|n| n.effective_score() >= self.config.min_confidence * 0.8)
                            .unwrap_or(false)
                    })
                    .take(3)
                    .collect();

                if good_frontier.len() >= 2 {
                    let op_start = std::time::Instant::now();
                    if let Ok(agg_id) = self.aggregate_thoughts(&mut graph, &good_frontier) {
                        operations_executed.push(ExecutedOperation {
                            operation: GraphOp::Aggregate {
                                source_ids: good_frontier.clone(),
                            },
                            success: true,
                            affected_nodes: vec![agg_id],
                            duration_ms: op_start.elapsed().as_millis() as u64,
                            notes: format!("Aggregated {} thoughts", good_frontier.len()),
                        });
                        aggregate_count += 1;

                        // Score the aggregated thought
                        // First compute avg score to avoid borrow conflict
                        let avg_source_score: f64 = good_frontier
                            .iter()
                            .filter_map(|&id| graph.get(id).and_then(|n| n.score))
                            .sum::<f64>()
                            / good_frontier.len() as f64;

                        if let Some(node) = graph.get_mut(agg_id) {
                            // Aggregation typically improves score slightly
                            node.score = Some((avg_source_score * 1.1).min(1.0));
                            node.valid = Some(true);
                        }
                    }
                }
            }

            // Try refinement if enabled
            if self.config.enable_refinement && refine_count < self.config.max_refinement_rounds {
                let top_thought = graph
                    .frontier_ids()
                    .into_iter()
                    .filter_map(|id| graph.get(id).map(|n| (id, n.effective_score())))
                    .max_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal))
                    .map(|(id, _)| id);

                if let Some(thought_id) = top_thought {
                    let op_start = std::time::Instant::now();
                    if self.refine_thought(&mut graph, thought_id).is_ok() {
                        operations_executed.push(ExecutedOperation {
                            operation: GraphOp::Refine { max_iterations: 1 },
                            success: true,
                            affected_nodes: vec![thought_id],
                            duration_ms: op_start.elapsed().as_millis() as u64,
                            notes: format!("Refined thought {}", thought_id),
                        });
                        refine_count += 1;
                    }
                }
            }
        }

        // Step 5: Select final thoughts
        let final_thoughts = self.select_final_thoughts(&graph);

        // Calculate overall confidence
        let confidence = self.calculate_confidence(&final_thoughts, &graph);

        // Build result
        let duration_ms = start.elapsed().as_millis() as u64;

        Ok(GoTResult {
            query: query.to_string(),
            final_thoughts,
            reasoning_graph: graph.to_data(),
            operations_executed,
            total_nodes_explored: graph.node_count(),
            pruned_branches: pruned_count,
            confidence,
            metadata: GoTMetadata {
                version: self.module_config.version.clone(),
                duration_ms,
                config: self.config.clone(),
                generate_count,
                aggregate_count,
                refine_count,
                backtrack_count,
            },
        })
    }

    /// Generate k thought branches from a parent node
    fn generate_thoughts(
        &self,
        graph: &mut ReasoningGraph,
        parent_id: u64,
        k: usize,
    ) -> Result<Vec<u64>> {
        let parent = graph
            .get(parent_id)
            .ok_or_else(|| GraphOfThoughtError::InvalidOperation {
                operation: format!("Parent node {} not found", parent_id),
            })?;

        let parent_content = parent.reasoning_step.clone();
        let parent_depth = parent.depth;

        // Check depth limit
        if parent_depth >= self.config.max_depth {
            return Err(GraphOfThoughtError::MaxDepthExceeded {
                depth: parent_depth + 1,
                max_depth: self.config.max_depth,
            }
            .into());
        }

        let mut generated_ids = Vec::new();

        // Generate diverse thought branches
        let branch_types = [
            ("analytical", "Breaking down the problem into components"),
            ("creative", "Exploring unconventional approaches"),
            ("critical", "Examining potential flaws and counterarguments"),
            ("practical", "Considering implementation and feasibility"),
            ("comparative", "Drawing parallels with similar problems"),
            ("systematic", "Following a structured methodology"),
            ("intuitive", "Applying domain expertise and patterns"),
            ("contrarian", "Challenging assumptions and conventions"),
        ];

        for (i, (branch_type, description)) in branch_types.iter().take(k).enumerate() {
            let reasoning = format!(
                "Branch {}: {} approach\n\nBuilding on: {}\n\n{}",
                i + 1,
                branch_type,
                parent_content,
                description
            );

            let child_id = graph.add_child(parent_id, reasoning)?;

            // Add metadata
            if let Some(node) = graph.get_mut(child_id) {
                node.metadata.created_by = Some("Generate".to_string());
                node.tags.push(branch_type.to_string());
            }

            generated_ids.push(child_id);
        }

        Ok(generated_ids)
    }

    /// Score all unscored thoughts in the graph
    fn score_thoughts(&self, graph: &mut ReasoningGraph) -> Result<Vec<u64>> {
        let unscored: Vec<u64> = graph
            .all_nodes()
            .iter()
            .filter(|n| n.score.is_none())
            .map(|n| n.id)
            .collect();

        for id in &unscored {
            if let Some(node) = graph.get_mut(*id) {
                // Calculate score based on various factors
                let depth_factor = 1.0 - (node.depth as f64 * 0.05).min(0.3);
                let content_factor = (node.reasoning_step.len() as f64 / 500.0).min(1.0);
                let tag_bonus = if node.tags.is_empty() { 0.0 } else { 0.1 };

                let base_score = 0.5 + (depth_factor * 0.2) + (content_factor * 0.2) + tag_bonus;

                // Add some variance based on content analysis
                let has_analysis = node.reasoning_step.to_lowercase().contains("because")
                    || node.reasoning_step.to_lowercase().contains("therefore")
                    || node.reasoning_step.to_lowercase().contains("consider");

                let final_score = if has_analysis {
                    (base_score * 1.1).min(0.95)
                } else {
                    base_score * 0.9
                };

                node.score = Some(final_score.clamp(0.3, 0.95));
                node.valid = Some(final_score >= self.config.backtrack_threshold);
            }
        }

        Ok(unscored)
    }

    /// Aggregate multiple thoughts into a synthesized thought
    fn aggregate_thoughts(&self, graph: &mut ReasoningGraph, source_ids: &[u64]) -> Result<u64> {
        if source_ids.len() < 2 {
            return Err(GraphOfThoughtError::AggregationFailed {
                reason: "Need at least 2 thoughts to aggregate".to_string(),
            }
            .into());
        }

        // Build aggregation content
        let mut synthesis =
            String::from("Synthesized conclusion from multiple reasoning paths:\n\n");

        for (i, &id) in source_ids.iter().enumerate() {
            if let Some(node) = graph.get(id) {
                synthesis.push_str(&format!(
                    "Path {} (score: {:.2}): {}\n\n",
                    i + 1,
                    node.effective_score(),
                    node.reasoning_step.chars().take(200).collect::<String>()
                ));
            }
        }

        synthesis.push_str("Key insights from aggregation:\n");
        synthesis.push_str("- Multiple perspectives converge on common themes\n");
        synthesis.push_str("- Complementary approaches strengthen the analysis\n");
        synthesis.push_str("- Synthesis captures the best elements from each path\n");

        graph.aggregate(source_ids, synthesis)
    }

    /// Refine a thought through iterative improvement
    fn refine_thought(&self, graph: &mut ReasoningGraph, thought_id: u64) -> Result<()> {
        let node =
            graph
                .get_mut(thought_id)
                .ok_or_else(|| GraphOfThoughtError::InvalidOperation {
                    operation: format!("Thought {} not found for refinement", thought_id),
                })?;

        if node.metadata.refinement_count >= self.config.max_refinement_rounds {
            return Err(GraphOfThoughtError::RefinementExceeded {
                rounds: node.metadata.refinement_count,
                max_rounds: self.config.max_refinement_rounds,
            }
            .into());
        }

        // Enhance the reasoning
        let enhanced = format!(
            "{}\n\n[Refinement {}] Additional considerations:\n\
             - Strengthening the logical connections\n\
             - Addressing potential counterarguments\n\
             - Clarifying assumptions and constraints",
            node.reasoning_step,
            node.metadata.refinement_count + 1
        );

        node.reasoning_step = enhanced;
        node.metadata.refinement_count += 1;

        // Boost score slightly for refinement
        if let Some(score) = node.score {
            node.score = Some((score * 1.05).min(0.98));
        }

        Ok(())
    }

    /// Find the best node to backtrack to
    fn find_best_backtrack_target(
        &self,
        graph: &ReasoningGraph,
        low_scorers: &[u64],
    ) -> Option<u64> {
        // Find ancestors of low scorers that have good scores
        for &low_id in low_scorers {
            if let Some(node) = graph.get(low_id) {
                for &parent_id in &node.parents {
                    if let Some(parent) = graph.get(parent_id) {
                        if parent.effective_score() >= self.config.min_confidence * 0.7 {
                            return Some(parent_id);
                        }
                    }
                }
            }
        }
        None
    }

    /// Backtrack to a specific node
    fn backtrack(&self, graph: &mut ReasoningGraph, target_id: u64) -> Result<()> {
        if graph.get(target_id).is_none() {
            return Err(GraphOfThoughtError::BacktrackTargetNotFound { node_id: target_id }.into());
        }

        // Reset frontier to the target node
        if let Some(&idx) = graph.id_to_index.get(&target_id) {
            graph.frontier = vec![idx];
        }

        Ok(())
    }

    /// Select the best final thoughts from the graph
    fn select_final_thoughts(&self, graph: &ReasoningGraph) -> Vec<ThoughtNode> {
        let mut candidates: Vec<ThoughtNode> = graph
            .frontier_ids()
            .iter()
            .filter_map(|&id| graph.get(id).cloned())
            .filter(|n| n.is_viable(self.config.backtrack_threshold))
            .collect();

        // Sort by score descending
        candidates.sort_by(|a, b| {
            b.effective_score()
                .partial_cmp(&a.effective_score())
                .unwrap_or(std::cmp::Ordering::Equal)
        });

        // Take top N
        candidates.truncate(self.config.keep_top_n);

        candidates
    }

    /// Calculate overall confidence from final thoughts
    fn calculate_confidence(&self, final_thoughts: &[ThoughtNode], _graph: &ReasoningGraph) -> f64 {
        if final_thoughts.is_empty() {
            return 0.0;
        }

        let avg_score: f64 = final_thoughts
            .iter()
            .map(|n| n.effective_score())
            .sum::<f64>()
            / final_thoughts.len() as f64;

        // Factor in diversity of approaches
        let unique_tags: std::collections::HashSet<&str> = final_thoughts
            .iter()
            .flat_map(|n| n.tags.iter().map(|s| s.as_str()))
            .collect();

        let diversity_factor = (unique_tags.len() as f64 / 8.0).min(1.0);

        // Combine factors
        (avg_score * 0.7 + diversity_factor * 0.3).clamp(0.0, 1.0)
    }
}

impl ThinkToolModule for GraphOfThought {
    fn config(&self) -> &ThinkToolModuleConfig {
        &self.module_config
    }

    fn execute(&self, context: &ThinkToolContext) -> Result<ThinkToolOutput> {
        // Validate input
        self.validate_query(&context.query)?;

        // Run the reasoning process
        let result = self.run_reasoning(&context.query)?;

        // Convert to ThinkToolOutput
        let output = json!({
            "final_thoughts": result.final_thoughts.iter().map(|t| json!({
                "id": t.id,
                "reasoning_step": t.reasoning_step.chars().take(500).collect::<String>(),
                "score": t.score,
                "valid": t.valid,
                "depth": t.depth,
                "tags": t.tags
            })).collect::<Vec<_>>(),
            "graph_summary": {
                "total_nodes": result.reasoning_graph.nodes.len(),
                "edges": result.reasoning_graph.edges.len(),
                "max_depth": result.reasoning_graph.max_depth,
                "leaf_count": result.reasoning_graph.leaf_ids.len()
            },
            "operations": result.operations_executed.iter().map(|op| json!({
                "type": op.operation.description(),
                "success": op.success,
                "affected_nodes": op.affected_nodes.len(),
                "duration_ms": op.duration_ms,
                "notes": op.notes
            })).collect::<Vec<_>>(),
            "statistics": {
                "total_nodes_explored": result.total_nodes_explored,
                "pruned_branches": result.pruned_branches,
                "generate_operations": result.metadata.generate_count,
                "aggregate_operations": result.metadata.aggregate_count,
                "refine_operations": result.metadata.refine_count,
                "backtrack_operations": result.metadata.backtrack_count
            },
            "confidence": result.confidence,
            "metadata": {
                "version": result.metadata.version,
                "duration_ms": result.metadata.duration_ms
            }
        });

        Ok(ThinkToolOutput {
            module: self.module_config.name.clone(),
            confidence: result.confidence,
            output,
        })
    }
}

impl AsyncThinkToolModule for GraphOfThought {
    fn execute_async<'a>(
        &'a self,
        context: &'a ThinkToolContext,
    ) -> Pin<Box<dyn Future<Output = Result<ThinkToolOutput>> + Send + 'a>> {
        Box::pin(async move {
            // For now, delegate to sync execution
            // In a real implementation with LLM, this would use async calls
            self.execute(context)
        })
    }
}

// ============================================================================
// BUILDER PATTERN
// ============================================================================

/// Builder for Graph-of-Thought module with fluent configuration
#[derive(Default)]
pub struct GoTBuilder {
    config: GoTConfig,
}

impl GoTBuilder {
    /// Create a new builder with default configuration
    pub fn new() -> Self {
        Self::default()
    }

    /// Set maximum branches per generation
    pub fn max_branches(mut self, k: usize) -> Self {
        self.config.max_branches = k;
        self
    }

    /// Enable or disable aggregation
    pub fn enable_aggregation(mut self, enabled: bool) -> Self {
        self.config.enable_aggregation = enabled;
        self
    }

    /// Enable or disable refinement
    pub fn enable_refinement(mut self, enabled: bool) -> Self {
        self.config.enable_refinement = enabled;
        self
    }

    /// Set maximum refinement rounds
    pub fn max_refinement_rounds(mut self, rounds: usize) -> Self {
        self.config.max_refinement_rounds = rounds;
        self
    }

    /// Set backtrack threshold
    pub fn backtrack_threshold(mut self, threshold: f64) -> Self {
        self.config.backtrack_threshold = threshold.clamp(0.0, 1.0);
        self
    }

    /// Set minimum confidence
    pub fn min_confidence(mut self, confidence: f64) -> Self {
        self.config.min_confidence = confidence.clamp(0.0, 1.0);
        self
    }

    /// Set maximum depth
    pub fn max_depth(mut self, depth: usize) -> Self {
        self.config.max_depth = depth;
        self
    }

    /// Enable or disable auto pruning
    pub fn auto_prune(mut self, enabled: bool) -> Self {
        self.config.auto_prune = enabled;
        self
    }

    /// Set keep top N for pruning
    pub fn keep_top_n(mut self, n: usize) -> Self {
        self.config.keep_top_n = n;
        self
    }

    /// Set maximum nodes
    pub fn max_nodes(mut self, max: usize) -> Self {
        self.config.max_nodes = max;
        self
    }

    /// Enable or disable verbose mode
    pub fn verbose(mut self, enabled: bool) -> Self {
        self.config.verbose = enabled;
        self
    }

    /// Build the GraphOfThought module
    pub fn build(self) -> GraphOfThought {
        GraphOfThought::with_config(self.config)
    }
}

// ============================================================================
// TESTS
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_got_creation() {
        let got = GraphOfThought::new();
        assert_eq!(got.config().name, "GraphOfThought");
        assert_eq!(got.config().version, "1.0.0");
    }

    #[test]
    fn test_got_config_default() {
        let config = GoTConfig::default();
        assert_eq!(config.max_branches, 4);
        assert!(config.enable_aggregation);
        assert!(config.enable_refinement);
        assert_eq!(config.max_refinement_rounds, 3);
        assert!((config.backtrack_threshold - 0.3).abs() < 0.01);
        assert!((config.min_confidence - 0.75).abs() < 0.01);
    }

    #[test]
    fn test_got_config_presets() {
        let quick = GoTConfig::quick();
        assert_eq!(quick.max_branches, 2);
        assert!(!quick.enable_aggregation);

        let deep = GoTConfig::deep();
        assert_eq!(deep.max_branches, 6);
        assert!(deep.enable_aggregation);

        let paranoid = GoTConfig::paranoid();
        assert_eq!(paranoid.max_branches, 8);
        assert!((paranoid.min_confidence - 0.90).abs() < 0.01);
    }

    #[test]
    fn test_thought_node_creation() {
        let node = ThoughtNode::new(1, "Test reasoning step")
            .with_score(0.85)
            .with_valid(true)
            .with_depth(2)
            .with_tag("analytical");

        assert_eq!(node.id, 1);
        assert_eq!(node.reasoning_step, "Test reasoning step");
        assert_eq!(node.score, Some(0.85));
        assert_eq!(node.valid, Some(true));
        assert_eq!(node.depth, 2);
        assert!(node.tags.contains(&"analytical".to_string()));
    }

    #[test]
    fn test_thought_node_viability() {
        let node = ThoughtNode::new(1, "Test").with_score(0.8).with_valid(true);
        assert!(node.is_viable(0.5));
        assert!(node.is_viable(0.8));
        assert!(!node.is_viable(0.81));

        let invalid_node = ThoughtNode::new(2, "Test")
            .with_score(0.9)
            .with_valid(false);
        assert!(!invalid_node.is_viable(0.5));
    }

    #[test]
    fn test_graph_op_descriptions() {
        let gen_op = GraphOp::Generate { k: 4 };
        assert!(gen_op.description().contains("4"));

        let agg_op = GraphOp::Aggregate {
            source_ids: vec![1, 2, 3],
        };
        assert!(agg_op.description().contains("3"));

        let refine_op = GraphOp::Refine { max_iterations: 5 };
        assert!(refine_op.description().contains("5"));
    }

    #[test]
    fn test_reasoning_graph_basic() {
        let mut graph = ReasoningGraph::new();
        let root_id = graph.add_root("Root thought");
        assert_eq!(root_id, 1);
        assert_eq!(graph.node_count(), 1);

        let child_id = graph.add_child(root_id, "Child thought").unwrap();
        assert_eq!(child_id, 2);
        assert_eq!(graph.node_count(), 2);

        let root = graph.get(root_id).unwrap();
        assert_eq!(root.children, vec![child_id]);

        let child = graph.get(child_id).unwrap();
        assert_eq!(child.parents, vec![root_id]);
        assert_eq!(child.depth, 1);
    }

    #[test]
    fn test_reasoning_graph_aggregation() {
        let mut graph = ReasoningGraph::new();
        let root_id = graph.add_root("Root");
        let child1 = graph.add_child(root_id, "Child 1").unwrap();
        let child2 = graph.add_child(root_id, "Child 2").unwrap();

        let agg_id = graph.aggregate(&[child1, child2], "Aggregated").unwrap();

        let agg_node = graph.get(agg_id).unwrap();
        assert_eq!(agg_node.parents.len(), 2);
        assert!(agg_node.metadata.aggregated_from.contains(&child1));
        assert!(agg_node.metadata.aggregated_from.contains(&child2));
    }

    #[test]
    fn test_got_builder() {
        let got = GoTBuilder::new()
            .max_branches(6)
            .enable_aggregation(false)
            .min_confidence(0.85)
            .build();

        assert_eq!(got.got_config().max_branches, 6);
        assert!(!got.got_config().enable_aggregation);
        assert!((got.got_config().min_confidence - 0.85).abs() < 0.01);
    }

    #[test]
    fn test_query_validation() {
        let got = GraphOfThought::new();

        // Too short
        let short_result = got.validate_query("short");
        assert!(short_result.is_err());

        // Valid
        let valid_result =
            got.validate_query("What is the optimal strategy for solving complex problems?");
        assert!(valid_result.is_ok());
    }

    #[test]
    fn test_got_execution() {
        let got = GraphOfThought::with_config(GoTConfig {
            max_nodes: 20,
            max_depth: 3,
            max_branches: 2,
            ..GoTConfig::quick()
        });

        let context = ThinkToolContext::new("What are the key considerations for system design?");
        let result = got.execute(&context).unwrap();

        assert_eq!(result.module, "GraphOfThought");
        assert!(result.confidence > 0.0);

        // Check output structure
        assert!(result.output.get("final_thoughts").is_some());
        assert!(result.output.get("graph_summary").is_some());
        assert!(result.output.get("operations").is_some());
        assert!(result.output.get("statistics").is_some());
    }

    #[test]
    fn test_reasoning_graph_no_cycles() {
        let mut graph = ReasoningGraph::new();
        let root_id = graph.add_root("Root");
        let child1 = graph.add_child(root_id, "Child 1").unwrap();
        let _child2 = graph.add_child(child1, "Child 2").unwrap();

        assert!(!graph.has_cycle());
    }

    #[test]
    fn test_reasoning_graph_pruning() {
        let mut graph = ReasoningGraph::new();
        let root_id = graph.add_root("Root");

        // Add several children with different scores
        for i in 0..5 {
            let child_id = graph.add_child(root_id, format!("Child {}", i)).unwrap();
            if let Some(node) = graph.get_mut(child_id) {
                node.score = Some(0.2 + (i as f64 * 0.15));
            }
        }

        let initial_frontier = graph.frontier_ids().len();
        let pruned = graph.prune(0.5, 2);

        assert!(pruned > 0);
        assert!(graph.frontier_ids().len() < initial_frontier);
    }

    #[test]
    fn test_got_result_structure() {
        let got = GraphOfThought::with_config(GoTConfig::quick());
        let context =
            ThinkToolContext::new("Analyze the trade-offs between performance and maintainability");

        let result = got.run_reasoning(&context.query).unwrap();

        assert!(!result.final_thoughts.is_empty());
        assert!(!result.reasoning_graph.nodes.is_empty());
        assert!(result.total_nodes_explored > 0);
        assert!(result.confidence > 0.0);
    }

    #[tokio::test]
    async fn test_async_execution() {
        let got = GraphOfThought::with_config(GoTConfig::quick());
        let context =
            ThinkToolContext::new("What factors should be considered in technology selection?");

        let result = got.execute_async(&context).await.unwrap();
        assert_eq!(result.module, "GraphOfThought");
        assert!(result.confidence > 0.0);
    }

    #[test]
    fn test_dfs_traversal() {
        let mut graph = ReasoningGraph::new();
        let root_id = graph.add_root("Root");
        let child1 = graph.add_child(root_id, "Child 1").unwrap();
        let child2 = graph.add_child(root_id, "Child 2").unwrap();
        let grandchild = graph.add_child(child1, "Grandchild").unwrap();

        let traversal = graph.dfs_collect();
        assert_eq!(traversal.len(), 4);
        assert!(traversal.contains(&root_id));
        assert!(traversal.contains(&child1));
        assert!(traversal.contains(&child2));
        assert!(traversal.contains(&grandchild));
    }
}