scribe_graph/

statistics.rs

//! # Graph Statistics and Analysis for Dependency Graphs
//!
//! Comprehensive statistical analysis and metrics computation for code dependency graphs.
//! This module provides detailed insights into graph structure, connectivity patterns,
//! and characteristics that are essential for understanding codebase architecture.
//!
//! ## Key Features
//! - **Degree Distribution Analysis**: In-degree, out-degree, and total degree statistics
//! - **Connectivity Metrics**: Strongly connected components, graph density, clustering
//! - **Structural Patterns**: Hub detection, authority identification, bottleneck analysis
//! - **Import Relationship Insights**: Dependency depth, fan-in/fan-out analysis
//! - **Performance Characteristics**: Memory usage, computation complexity estimates
//! - **Comparative Analysis**: Before/after graph evolution tracking

use std::collections::{HashMap, VecDeque};
use serde::{Deserialize, Serialize};
use scribe_core::Result;

use crate::graph::{DependencyGraph, NodeId, GraphStatistics};

/// Comprehensive graph analysis results
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct GraphAnalysisResults {
    /// Basic graph statistics
    pub basic_stats: GraphStatistics,
    
    /// Degree distribution analysis
    pub degree_distribution: DegreeDistribution,
    
    /// Connectivity analysis
    pub connectivity: ConnectivityAnalysis,
    
    /// Structural patterns
    pub structural_patterns: StructuralPatterns,
    
    /// Import relationship insights
    pub import_insights: ImportInsights,
    
    /// Performance characteristics
    pub performance_profile: PerformanceProfile,
    
    /// Analysis metadata
    pub analysis_metadata: AnalysisMetadata,
}

/// Detailed degree distribution statistics
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
pub struct DegreeDistribution {
    /// In-degree statistics
    pub in_degree: DegreeStats,
    
    /// Out-degree statistics  
    pub out_degree: DegreeStats,
    
    /// Total degree statistics
    pub total_degree: DegreeStats,
    
    /// Degree distribution histogram (degree -> count)
    pub in_degree_histogram: HashMap<usize, usize>,
    pub out_degree_histogram: HashMap<usize, usize>,
    
    /// Power-law fitting parameters (if applicable)
    pub power_law_alpha: Option<f64>,
    pub power_law_goodness_of_fit: Option<f64>,
}

/// Statistical measures for degree sequences
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
pub struct DegreeStats {
    pub min: usize,
    pub max: usize,
    pub mean: f64,
    pub median: f64,
    pub std_dev: f64,
    pub percentile_25: f64,
    pub percentile_75: f64,
    pub percentile_90: f64,
    pub percentile_95: f64,
    pub percentile_99: f64,
}

/// Graph connectivity and component analysis
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
pub struct ConnectivityAnalysis {
    /// Number of weakly connected components
    pub weakly_connected_components: usize,
    
    /// Number of strongly connected components
    pub strongly_connected_components: usize,
    
    /// Size of largest strongly connected component
    pub largest_scc_size: usize,
    
    /// Graph density (actual edges / possible edges)
    pub graph_density: f64,
    
    /// Average clustering coefficient
    pub average_clustering: f64,
    
    /// Global clustering coefficient (transitivity)
    pub global_clustering: f64,
    
    /// Average path length (in largest component)
    pub average_path_length: Option<f64>,
    
    /// Graph diameter (longest shortest path)
    pub diameter: Option<usize>,
    
    /// Is the graph acyclic (DAG)
    pub is_acyclic: bool,
}

/// Structural patterns and notable nodes
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
pub struct StructuralPatterns {
    /// Hub nodes (high out-degree)
    pub hubs: Vec<NodeInfo>,
    
    /// Authority nodes (high in-degree) 
    pub authorities: Vec<NodeInfo>,
    
    /// Bottleneck nodes (high betweenness centrality estimate)
    pub bottlenecks: Vec<NodeInfo>,
    
    /// Bridge nodes (critical for connectivity)
    pub bridges: Vec<NodeInfo>,
    
    /// Isolated nodes (no connections)
    pub isolated_nodes: Vec<NodeId>,
    
    /// Dangling nodes (no outgoing edges)
    pub dangling_nodes: Vec<NodeId>,
    
    /// Leaf nodes (no incoming edges, but have outgoing)
    pub leaf_nodes: Vec<NodeId>,
}

/// Information about important nodes
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct NodeInfo {
    pub node_id: NodeId,
    pub score: f64,
    pub in_degree: usize,
    pub out_degree: usize,
    pub metadata: Option<String>, // Additional context
}

/// Import relationship specific insights
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
pub struct ImportInsights {
    /// Average import depth (distance from root nodes)
    pub average_import_depth: f64,
    
    /// Maximum import depth
    pub max_import_depth: usize,
    
    /// Import fan-out distribution (how many files each file imports)
    pub fan_out_distribution: DegreeStats,
    
    /// Import fan-in distribution (how many files import each file)
    pub fan_in_distribution: DegreeStats,
    
    /// Circular dependency detection
    pub circular_dependencies: Vec<CircularDependency>,
    
    /// Dependency layers (topological levels)
    pub dependency_layers: Vec<Vec<NodeId>>,
    
    /// Critical import paths (most important dependency chains)
    pub critical_paths: Vec<DependencyPath>,
}

/// Circular dependency information
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct CircularDependency {
    pub nodes: Vec<NodeId>,
    pub cycle_length: usize,
    pub strength: f64, // How many edges form the cycle
}

/// Important dependency path
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct DependencyPath {
    pub path: Vec<NodeId>,
    pub length: usize,
    pub importance_score: f64,
}

/// Performance characteristics of the graph
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
pub struct PerformanceProfile {
    /// Estimated memory usage for PageRank computation
    pub pagerank_memory_estimate_mb: f64,
    
    /// Estimated PageRank computation time
    pub pagerank_time_estimate_ms: u64,
    
    /// Graph traversal complexity
    pub traversal_complexity: TraversalComplexity,
    
    /// Storage efficiency metrics
    pub storage_efficiency: StorageEfficiency,
}

/// Complexity analysis for graph algorithms
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
pub struct TraversalComplexity {
    /// BFS/DFS time complexity class
    pub time_complexity_class: String,
    
    /// Space complexity class
    pub space_complexity_class: String,
    
    /// Expected iterations for convergence algorithms
    pub expected_iterations: usize,
}

/// Storage and memory efficiency metrics
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
pub struct StorageEfficiency {
    /// Adjacency list memory usage (bytes)
    pub adjacency_list_size_bytes: usize,
    
    /// Average edges per node
    pub edges_per_node: f64,
    
    /// Memory overhead ratio
    pub memory_overhead_ratio: f64,
    
    /// Sparsity coefficient
    pub sparsity: f64,
}

/// Analysis execution metadata
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct AnalysisMetadata {
    /// When the analysis was performed
    pub timestamp: chrono::DateTime<chrono::Utc>,
    
    /// Analysis duration in milliseconds
    pub analysis_duration_ms: u64,
    
    /// Whether parallel computation was used
    pub used_parallel: bool,
    
    /// Analysis configuration used
    pub config: StatisticsConfig,
    
    /// Version of the statistics module
    pub version: String,
}

impl Default for AnalysisMetadata {
    fn default() -> Self {
        Self {
            timestamp: chrono::Utc::now(),
            analysis_duration_ms: 0,
            used_parallel: false,
            config: StatisticsConfig::default(),
            version: "1.0.0".to_string(),
        }
    }
}

/// Configuration for statistics computation
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct StatisticsConfig {
    /// Whether to compute expensive metrics (clustering, path length)
    pub compute_expensive_metrics: bool,
    
    /// Whether to use parallel computation where possible
    pub use_parallel: bool,
    
    /// Maximum number of nodes to analyze for expensive operations
    pub max_nodes_for_expensive_ops: usize,
    
    /// Number of top nodes to include in structural patterns
    pub top_nodes_count: usize,
    
    /// Minimum score threshold for pattern detection
    pub pattern_threshold: f64,
}

impl Default for StatisticsConfig {
    fn default() -> Self {
        Self {
            compute_expensive_metrics: true,
            use_parallel: true,
            max_nodes_for_expensive_ops: 10000,
            top_nodes_count: 10,
            pattern_threshold: 0.1,
        }
    }
}

/// Main graph statistics analyzer
#[derive(Debug)]
pub struct GraphStatisticsAnalyzer {
    config: StatisticsConfig,
}

impl GraphStatisticsAnalyzer {
    /// Create a new analyzer with default configuration
    pub fn new() -> Self {
        Self {
            config: StatisticsConfig::default(),
        }
    }
    
    /// Create with custom configuration
    pub fn with_config(config: StatisticsConfig) -> Self {
        Self { config }
    }
    
    /// Create analyzer optimized for large graphs
    pub fn for_large_graphs() -> Self {
        Self {
            config: StatisticsConfig {
                compute_expensive_metrics: false,
                max_nodes_for_expensive_ops: 5000,
                top_nodes_count: 5,
                ..StatisticsConfig::default()
            },
        }
    }
    
    /// Perform comprehensive analysis of the dependency graph
    pub fn analyze(&self, graph: &DependencyGraph) -> Result<GraphAnalysisResults> {
        let start_time = std::time::Instant::now();
        
        // Basic statistics
        let basic_stats = self.compute_basic_statistics(graph);
        
        // Degree distribution analysis
        let degree_distribution = self.analyze_degree_distribution(graph)?;
        
        // Connectivity analysis
        let connectivity = self.analyze_connectivity(graph)?;
        
        // Structural patterns
        let structural_patterns = self.identify_structural_patterns(graph)?;
        
        // Import-specific insights
        let import_insights = self.analyze_import_patterns(graph)?;
        
        // Performance characteristics
        let performance_profile = self.estimate_performance_characteristics(graph);
        
        // Analysis metadata
        let analysis_metadata = AnalysisMetadata {
            timestamp: chrono::Utc::now(),
            analysis_duration_ms: start_time.elapsed().as_millis() as u64,
            used_parallel: self.config.use_parallel,
            config: self.config.clone(),
            version: env!("CARGO_PKG_VERSION").to_string(),
        };
        
        Ok(GraphAnalysisResults {
            basic_stats,
            degree_distribution,
            connectivity,
            structural_patterns,
            import_insights,
            performance_profile,
            analysis_metadata,
        })
    }
    
    /// Compute basic graph statistics
    fn compute_basic_statistics(&self, graph: &DependencyGraph) -> GraphStatistics {
        let total_nodes = graph.node_count();
        let total_edges = graph.edge_count();
        
        if total_nodes == 0 {
            return GraphStatistics::empty();
        }
        
        // Compute degree statistics
        let degrees: Vec<_> = graph.nodes()
            .map(|node| (graph.in_degree(node), graph.out_degree(node)))
            .collect();
        
        let in_degrees: Vec<_> = degrees.iter().map(|(in_deg, _)| *in_deg).collect();
        let out_degrees: Vec<_> = degrees.iter().map(|(_, out_deg)| *out_deg).collect();
        
        let in_degree_avg = in_degrees.iter().sum::<usize>() as f64 / total_nodes as f64;
        let in_degree_max = *in_degrees.iter().max().unwrap_or(&0);
        let out_degree_avg = out_degrees.iter().sum::<usize>() as f64 / total_nodes as f64;
        let out_degree_max = *out_degrees.iter().max().unwrap_or(&0);
        
        // Count special node types
        let isolated_nodes = degrees.iter().filter(|(in_deg, out_deg)| *in_deg == 0 && *out_deg == 0).count();
        let dangling_nodes = degrees.iter().filter(|(_, out_deg)| *out_deg == 0).count();
        
        // Graph density
        let max_possible_edges = total_nodes * (total_nodes - 1);
        let graph_density = if max_possible_edges > 0 {
            total_edges as f64 / max_possible_edges as f64
        } else {
            0.0
        };
        
        GraphStatistics {
            total_nodes,
            total_edges,
            in_degree_avg,
            in_degree_max,
            out_degree_avg,
            out_degree_max,
            strongly_connected_components: graph.estimate_scc_count(),
            graph_density,
            isolated_nodes,
            dangling_nodes,
        }
    }
    
    /// Analyze degree distributions in detail
    fn analyze_degree_distribution(&self, graph: &DependencyGraph) -> Result<DegreeDistribution> {
        let degrees: Vec<_> = graph.nodes()
            .map(|node| (graph.in_degree(node), graph.out_degree(node)))
            .collect();
        
        let in_degrees: Vec<_> = degrees.iter().map(|(in_deg, _)| *in_deg).collect();
        let out_degrees: Vec<_> = degrees.iter().map(|(_, out_deg)| *out_deg).collect();
        let total_degrees: Vec<_> = degrees.iter().map(|(in_deg, out_deg)| in_deg + out_deg).collect();
        
        Ok(DegreeDistribution {
            in_degree: self.compute_degree_stats(&in_degrees),
            out_degree: self.compute_degree_stats(&out_degrees),
            total_degree: self.compute_degree_stats(&total_degrees),
            in_degree_histogram: self.compute_histogram(&in_degrees),
            out_degree_histogram: self.compute_histogram(&out_degrees),
            power_law_alpha: self.estimate_power_law_alpha(&in_degrees),
            power_law_goodness_of_fit: None, // TODO: Implement KS test
        })
    }
    
    /// Compute detailed statistics for a degree sequence
    fn compute_degree_stats(&self, degrees: &[usize]) -> DegreeStats {
        if degrees.is_empty() {
            return DegreeStats {
                min: 0,
                max: 0,
                mean: 0.0,
                median: 0.0,
                std_dev: 0.0,
                percentile_25: 0.0,
                percentile_75: 0.0,
                percentile_90: 0.0,
                percentile_95: 0.0,
                percentile_99: 0.0,
            };
        }
        
        let mut sorted_degrees = degrees.to_vec();
        sorted_degrees.sort();
        
        let min = sorted_degrees[0];
        let max = sorted_degrees[sorted_degrees.len() - 1];
        let mean = degrees.iter().sum::<usize>() as f64 / degrees.len() as f64;
        
        // Percentiles
        let median = self.percentile(&sorted_degrees, 50.0);
        let percentile_25 = self.percentile(&sorted_degrees, 25.0);
        let percentile_75 = self.percentile(&sorted_degrees, 75.0);
        let percentile_90 = self.percentile(&sorted_degrees, 90.0);
        let percentile_95 = self.percentile(&sorted_degrees, 95.0);
        let percentile_99 = self.percentile(&sorted_degrees, 99.0);
        
        // Standard deviation
        let variance = degrees.iter()
            .map(|&deg| (deg as f64 - mean).powi(2))
            .sum::<f64>() / degrees.len() as f64;
        let std_dev = variance.sqrt();
        
        DegreeStats {
            min,
            max,
            mean,
            median,
            std_dev,
            percentile_25,
            percentile_75,
            percentile_90,
            percentile_95,
            percentile_99,
        }
    }
    
    /// Calculate percentile from sorted array
    fn percentile(&self, sorted_values: &[usize], percentile: f64) -> f64 {
        if sorted_values.is_empty() {
            return 0.0;
        }
        
        let index = (percentile / 100.0) * (sorted_values.len() - 1) as f64;
        let lower = index.floor() as usize;
        let upper = index.ceil() as usize;
        
        if lower == upper {
            sorted_values[lower] as f64
        } else {
            let weight = index - lower as f64;
            (1.0 - weight) * sorted_values[lower] as f64 + weight * sorted_values[upper] as f64
        }
    }
    
    /// Compute degree histogram
    fn compute_histogram(&self, degrees: &[usize]) -> HashMap<usize, usize> {
        let mut histogram = HashMap::new();
        for &degree in degrees {
            *histogram.entry(degree).or_insert(0) += 1;
        }
        histogram
    }
    
    /// Estimate power-law exponent alpha using linear regression on log-log plot
    fn estimate_power_law_alpha(&self, degrees: &[usize]) -> Option<f64> {
        // Filter out zeros (can't take log)
        let non_zero_degrees: Vec<_> = degrees.iter().filter(|&&d| d > 0).collect();
        
        if non_zero_degrees.len() < 10 {
            return None; // Not enough data for reliable estimation
        }
        
        // Create log-log data points
        let mut log_points = Vec::new();
        let histogram = self.compute_histogram(&non_zero_degrees.into_iter().copied().collect::<Vec<_>>());
        
        for (&degree, &count) in &histogram {
            if count > 0 {
                log_points.push((degree as f64, count as f64));
            }
        }
        
        if log_points.len() < 5 {
            return None;
        }
        
        // Linear regression: log(count) = -alpha * log(degree) + C
        let n = log_points.len() as f64;
        let sum_log_x: f64 = log_points.iter().map(|(x, _)| x.ln()).sum();
        let sum_log_y: f64 = log_points.iter().map(|(_, y)| y.ln()).sum();
        let sum_log_x_log_y: f64 = log_points.iter().map(|(x, y)| x.ln() * y.ln()).sum();
        let sum_log_x_squared: f64 = log_points.iter().map(|(x, _)| x.ln().powi(2)).sum();
        
        let denominator = n * sum_log_x_squared - sum_log_x.powi(2);
        if denominator.abs() < 1e-10 {
            return None;
        }
        
        let alpha = -(n * sum_log_x_log_y - sum_log_x * sum_log_y) / denominator;
        
        // Only return positive alpha (valid for power-law)
        if alpha > 0.0 { Some(alpha) } else { None }
    }
    
    /// Analyze graph connectivity properties
    fn analyze_connectivity(&self, graph: &DependencyGraph) -> Result<ConnectivityAnalysis> {
        let strongly_connected_components = graph.estimate_scc_count();
        let largest_scc_size = self.estimate_largest_scc_size(graph);
        
        // For now, assume weakly connected components = strongly connected components
        // A more sophisticated implementation would use Union-Find
        let weakly_connected_components = strongly_connected_components;
        
        let graph_density = if graph.node_count() > 1 {
            let max_edges = graph.node_count() * (graph.node_count() - 1);
            graph.edge_count() as f64 / max_edges as f64
        } else {
            0.0
        };
        
        // Expensive computations only for smaller graphs
        let (average_clustering, global_clustering, average_path_length, diameter) = 
            if self.config.compute_expensive_metrics && graph.node_count() <= self.config.max_nodes_for_expensive_ops {
                (
                    Some(self.estimate_average_clustering(graph)),
                    Some(self.estimate_global_clustering(graph)),
                    self.estimate_average_path_length(graph),
                    self.estimate_diameter(graph),
                )
            } else {
                (None, None, None, None)
            };
        
        let is_acyclic = self.estimate_is_acyclic(graph);
        
        Ok(ConnectivityAnalysis {
            weakly_connected_components,
            strongly_connected_components,
            largest_scc_size,
            graph_density,
            average_clustering: average_clustering.unwrap_or(0.0),
            global_clustering: global_clustering.unwrap_or(0.0),
            average_path_length,
            diameter,
            is_acyclic,
        })
    }
    
    /// Estimate size of largest strongly connected component
    fn estimate_largest_scc_size(&self, graph: &DependencyGraph) -> usize {
        // Simplified estimation: find node with highest product of in/out degrees
        graph.nodes()
            .map(|node| std::cmp::min(graph.in_degree(node) + 1, graph.out_degree(node) + 1))
            .max()
            .unwrap_or(0)
    }
    
    /// Estimate average clustering coefficient
    fn estimate_average_clustering(&self, graph: &DependencyGraph) -> f64 {
        let clustering_coefficients: Vec<f64> = graph.nodes()
            .map(|node| self.local_clustering_coefficient(graph, node))
            .collect();
        
        if clustering_coefficients.is_empty() {
            0.0
        } else {
            clustering_coefficients.iter().sum::<f64>() / clustering_coefficients.len() as f64
        }
    }
    
    /// Compute local clustering coefficient for a node
    fn local_clustering_coefficient(&self, graph: &DependencyGraph, node: &NodeId) -> f64 {
        let neighbors = graph.all_neighbors(node);
        let k = neighbors.len();
        
        if k < 2 {
            return 0.0;
        }
        
        // Count edges between neighbors
        let mut edges_between_neighbors = 0;
        let neighbor_vec: Vec<_> = neighbors.iter().collect();
        
        for i in 0..neighbor_vec.len() {
            for j in (i + 1)..neighbor_vec.len() {
                if graph.contains_edge(neighbor_vec[i], neighbor_vec[j]) ||
                   graph.contains_edge(neighbor_vec[j], neighbor_vec[i]) {
                    edges_between_neighbors += 1;
                }
            }
        }
        
        let max_possible_edges = k * (k - 1) / 2;
        edges_between_neighbors as f64 / max_possible_edges as f64
    }
    
    /// Estimate global clustering coefficient (transitivity)
    fn estimate_global_clustering(&self, graph: &DependencyGraph) -> f64 {
        let mut triangles = 0;
        let mut triplets = 0;
        
        for node in graph.nodes() {
            let neighbors = graph.all_neighbors(node);
            if neighbors.len() < 2 {
                continue;
            }
            
            let neighbor_vec: Vec<_> = neighbors.iter().collect();
            
            for i in 0..neighbor_vec.len() {
                for j in (i + 1)..neighbor_vec.len() {
                    triplets += 1;
                    if graph.contains_edge(neighbor_vec[i], neighbor_vec[j]) ||
                       graph.contains_edge(neighbor_vec[j], neighbor_vec[i]) {
                        triangles += 1;
                    }
                }
            }
        }
        
        if triplets > 0 {
            3.0 * triangles as f64 / triplets as f64
        } else {
            0.0
        }
    }
    
    /// Estimate average path length using sampling
    fn estimate_average_path_length(&self, graph: &DependencyGraph) -> Option<f64> {
        let nodes: Vec<_> = graph.nodes().collect();
        if nodes.len() < 2 {
            return None;
        }
        
        let sample_size = std::cmp::min(100, nodes.len());
        let mut total_path_length = 0.0;
        let mut valid_paths = 0;
        
        for i in 0..sample_size {
            let start_node = &nodes[i % nodes.len()];
            let distances = self.bfs_distances(graph, start_node);
            
            for distance in distances.values() {
                if *distance > 0 && *distance < usize::MAX {
                    total_path_length += *distance as f64;
                    valid_paths += 1;
                }
            }
        }
        
        if valid_paths > 0 {
            Some(total_path_length / valid_paths as f64)
        } else {
            None
        }
    }
    
    /// Estimate graph diameter
    fn estimate_diameter(&self, graph: &DependencyGraph) -> Option<usize> {
        let nodes: Vec<_> = graph.nodes().collect();
        if nodes.is_empty() {
            return None;
        }
        
        let mut max_distance = 0;
        let sample_size = std::cmp::min(20, nodes.len());
        
        for i in 0..sample_size {
            let start_node = &nodes[i % nodes.len()];
            let distances = self.bfs_distances(graph, start_node);
            
            for &distance in distances.values() {
                if distance != usize::MAX && distance > max_distance {
                    max_distance = distance;
                }
            }
        }
        
        if max_distance > 0 { Some(max_distance) } else { None }
    }
    
    /// BFS to compute distances from a source node
    fn bfs_distances(&self, graph: &DependencyGraph, source: &NodeId) -> HashMap<NodeId, usize> {
        let mut distances = HashMap::new();
        let mut queue = VecDeque::new();
        
        distances.insert(source.clone(), 0);
        queue.push_back(source.clone());
        
        while let Some(current) = queue.pop_front() {
            let current_distance = distances[&current];
            
            // Visit both outgoing and incoming neighbors (undirected traversal)
            if let Some(outgoing) = graph.outgoing_neighbors(&current) {
                for neighbor in outgoing {
                    if !distances.contains_key(neighbor) {
                        distances.insert(neighbor.clone(), current_distance + 1);
                        queue.push_back(neighbor.clone());
                    }
                }
            }
            
            if let Some(incoming) = graph.incoming_neighbors(&current) {
                for neighbor in incoming {
                    if !distances.contains_key(neighbor) {
                        distances.insert(neighbor.clone(), current_distance + 1);
                        queue.push_back(neighbor.clone());
                    }
                }
            }
        }
        
        distances
    }
    
    /// Check if graph is likely acyclic (DAG)
    fn estimate_is_acyclic(&self, graph: &DependencyGraph) -> bool {
        // Simple heuristic: if there are very few nodes with both in and out edges, likely acyclic
        let nodes_with_both = graph.nodes()
            .filter(|&node| graph.in_degree(node) > 0 && graph.out_degree(node) > 0)
            .count();
        
        let total_nodes = graph.node_count();
        if total_nodes == 0 {
            return true;
        }
        
        let bidirectional_ratio = nodes_with_both as f64 / total_nodes as f64;
        bidirectional_ratio < 0.3 // Heuristic threshold
    }
    
    /// Identify structural patterns in the graph
    fn identify_structural_patterns(&self, graph: &DependencyGraph) -> Result<StructuralPatterns> {
        // Find hubs (high out-degree)
        let mut hub_candidates: Vec<_> = graph.nodes()
            .map(|node| NodeInfo {
                node_id: node.clone(),
                score: graph.out_degree(node) as f64,
                in_degree: graph.in_degree(node),
                out_degree: graph.out_degree(node),
                metadata: None,
            })
            .collect();
        hub_candidates.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap_or(std::cmp::Ordering::Equal));
        let hubs = hub_candidates.into_iter().take(self.config.top_nodes_count).collect();
        
        // Find authorities (high in-degree)
        let mut authority_candidates: Vec<_> = graph.nodes()
            .map(|node| NodeInfo {
                node_id: node.clone(),
                score: graph.in_degree(node) as f64,
                in_degree: graph.in_degree(node),
                out_degree: graph.out_degree(node),
                metadata: None,
            })
            .collect();
        authority_candidates.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap_or(std::cmp::Ordering::Equal));
        let authorities = authority_candidates.into_iter().take(self.config.top_nodes_count).collect();
        
        // Identify special node types
        let isolated_nodes: Vec<_> = graph.nodes()
            .filter(|&node| graph.degree(node) == 0)
            .cloned()
            .collect();
        
        let dangling_nodes = graph.dangling_nodes().into_iter().cloned().collect();
        
        let leaf_nodes: Vec<_> = graph.nodes()
            .filter(|&node| graph.in_degree(node) == 0 && graph.out_degree(node) > 0)
            .cloned()
            .collect();
        
        // TODO: Implement betweenness centrality for bottlenecks and bridges
        let bottlenecks = Vec::new();
        let bridges = Vec::new();
        
        Ok(StructuralPatterns {
            hubs,
            authorities,
            bottlenecks,
            bridges,
            isolated_nodes,
            dangling_nodes,
            leaf_nodes,
        })
    }
    
    /// Analyze import-specific patterns
    fn analyze_import_patterns(&self, graph: &DependencyGraph) -> Result<ImportInsights> {
        let fan_out_stats = {
            let out_degrees: Vec<_> = graph.nodes().map(|node| graph.out_degree(node)).collect();
            self.compute_degree_stats(&out_degrees)
        };
        
        let fan_in_stats = {
            let in_degrees: Vec<_> = graph.nodes().map(|node| graph.in_degree(node)).collect();
            self.compute_degree_stats(&in_degrees)
        };
        
        // TODO: Implement sophisticated cycle detection and dependency layering
        let circular_dependencies = Vec::new();
        let dependency_layers = Vec::new();
        let critical_paths = Vec::new();
        
        // Simple depth estimation
        let max_import_depth = if let Some(diameter) = self.estimate_diameter(graph) {
            diameter
        } else {
            0
        };
        
        let average_import_depth = if let Some(avg_path) = self.estimate_average_path_length(graph) {
            avg_path
        } else {
            0.0
        };
        
        Ok(ImportInsights {
            average_import_depth,
            max_import_depth,
            fan_out_distribution: fan_out_stats,
            fan_in_distribution: fan_in_stats,
            circular_dependencies,
            dependency_layers,
            critical_paths,
        })
    }
    
    /// Estimate performance characteristics for various graph algorithms
    fn estimate_performance_characteristics(&self, graph: &DependencyGraph) -> PerformanceProfile {
        let n = graph.node_count();
        let m = graph.edge_count();
        
        // PageRank memory estimate (2 score vectors + graph overhead)
        let pagerank_memory_mb = if n > 0 {
            let score_vector_size = n * std::mem::size_of::<f64>();
            let graph_overhead = m * (std::mem::size_of::<String>() + std::mem::size_of::<usize>());
            ((score_vector_size * 2 + graph_overhead) as f64) / (1024.0 * 1024.0)
        } else {
            0.0
        };
        
        // Rough PageRank time estimate (based on empirical observations)
        let pagerank_time_estimate_ms = if n > 0 {
            // Base time + iterations * (nodes + edges)
            let base_time = 1;
            let per_iteration_time = (n + m) / 10000; // Rough estimate
            let estimated_iterations = if n < 1000 { 10 } else { 20 };
            base_time + estimated_iterations * per_iteration_time.max(1)
        } else {
            0
        } as u64;
        
        let traversal_complexity = TraversalComplexity {
            time_complexity_class: format!("O(V + E) = O({} + {})", n, m),
            space_complexity_class: format!("O(V) = O({})", n),
            expected_iterations: if n < 1000 { 10 } else { 20 },
        };
        
        let edges_per_node = if n > 0 { m as f64 / n as f64 } else { 0.0 };
        let max_possible_edges = if n > 1 { n * (n - 1) } else { 1 };
        let sparsity = 1.0 - (m as f64 / max_possible_edges as f64);
        
        let storage_efficiency = StorageEfficiency {
            adjacency_list_size_bytes: m * (std::mem::size_of::<String>() + std::mem::size_of::<usize>()),
            edges_per_node,
            memory_overhead_ratio: 1.5, // Rough estimate for hash map overhead
            sparsity,
        };
        
        PerformanceProfile {
            pagerank_memory_estimate_mb: pagerank_memory_mb,
            pagerank_time_estimate_ms,
            traversal_complexity,
            storage_efficiency,
        }
    }
}

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

/// Utility functions for graph analysis results
impl GraphAnalysisResults {
    /// Generate a comprehensive summary report
    pub fn summary_report(&self) -> String {
        format!(
            "Graph Analysis Summary Report\n\
             ============================\n\
             \n\
             Basic Statistics:\n\
             - Nodes: {} | Edges: {} | Density: {:.4}\n\
             - Average in-degree: {:.2} | Average out-degree: {:.2}\n\
             - Strongly connected components: {}\n\
             \n\
             Degree Distribution:\n\
             - In-degree range: [{}, {}] (mean: {:.2}, std: {:.2})\n\
             - Out-degree range: [{}, {}] (mean: {:.2}, std: {:.2})\n\
             - Power-law alpha: {}\n\
             \n\
             Connectivity:\n\
             - Average clustering: {:.4}\n\
             - Average path length: {}\n\
             - Diameter: {} | Is acyclic: {}\n\
             \n\
             Structural Patterns:\n\
             - Top hubs: {} | Top authorities: {}\n\
             - Isolated nodes: {} | Dangling nodes: {} | Leaf nodes: {}\n\
             \n\
             Import Insights:\n\
             - Average import depth: {:.2} | Max depth: {}\n\
             - Circular dependencies: {}\n\
             \n\
             Performance Profile:\n\
             - PageRank memory estimate: {:.1} MB\n\
             - PageRank time estimate: {} ms\n\
             - Graph sparsity: {:.4}\n\
             \n\
             Analysis completed in {} ms (parallel: {})",
            self.basic_stats.total_nodes,
            self.basic_stats.total_edges,
            self.basic_stats.graph_density,
            self.basic_stats.in_degree_avg,
            self.basic_stats.out_degree_avg,
            self.basic_stats.strongly_connected_components,
            
            self.degree_distribution.in_degree.min,
            self.degree_distribution.in_degree.max,
            self.degree_distribution.in_degree.mean,
            self.degree_distribution.in_degree.std_dev,
            self.degree_distribution.out_degree.min,
            self.degree_distribution.out_degree.max,
            self.degree_distribution.out_degree.mean,
            self.degree_distribution.out_degree.std_dev,
            self.degree_distribution.power_law_alpha.map_or("N/A".to_string(), |a| format!("{:.3}", a)),
            
            self.connectivity.average_clustering,
            self.connectivity.average_path_length.map_or("N/A".to_string(), |l| format!("{:.2}", l)),
            self.connectivity.diameter.map_or("N/A".to_string(), |d| d.to_string()),
            self.connectivity.is_acyclic,
            
            self.structural_patterns.hubs.len(),
            self.structural_patterns.authorities.len(),
            self.structural_patterns.isolated_nodes.len(),
            self.structural_patterns.dangling_nodes.len(),
            self.structural_patterns.leaf_nodes.len(),
            
            self.import_insights.average_import_depth,
            self.import_insights.max_import_depth,
            self.import_insights.circular_dependencies.len(),
            
            self.performance_profile.pagerank_memory_estimate_mb,
            self.performance_profile.pagerank_time_estimate_ms,
            self.performance_profile.storage_efficiency.sparsity,
            
            self.analysis_metadata.analysis_duration_ms,
            self.analysis_metadata.used_parallel,
        )
    }
    
    /// Get a list of the most important nodes by various metrics
    pub fn important_nodes_summary(&self) -> Vec<(String, Vec<String>)> {
        vec![
            (
                "Top Hubs (High Out-degree)".to_string(),
                self.structural_patterns.hubs.iter()
                    .map(|node| format!("{} (out: {})", node.node_id, node.out_degree))
                    .collect(),
            ),
            (
                "Top Authorities (High In-degree)".to_string(),
                self.structural_patterns.authorities.iter()
                    .map(|node| format!("{} (in: {})", node.node_id, node.in_degree))
                    .collect(),
            ),
        ]
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::graph::DependencyGraph;
    
    fn create_test_graph() -> DependencyGraph {
        let mut graph = DependencyGraph::new();
        
        // Create a more complex graph for testing
        graph.add_edge("main.py".to_string(), "utils.py".to_string()).unwrap();
        graph.add_edge("main.py".to_string(), "config.py".to_string()).unwrap();
        graph.add_edge("utils.py".to_string(), "config.py".to_string()).unwrap();
        graph.add_edge("test.py".to_string(), "main.py".to_string()).unwrap();
        graph.add_edge("test.py".to_string(), "utils.py".to_string()).unwrap();
        graph.add_node("isolated.py".to_string()).unwrap();
        
        graph
    }
    
    #[test]
    fn test_statistics_analyzer_creation() {
        let analyzer = GraphStatisticsAnalyzer::new();
        assert!(analyzer.config.compute_expensive_metrics);
        
        let large_graph_analyzer = GraphStatisticsAnalyzer::for_large_graphs();
        assert!(!large_graph_analyzer.config.compute_expensive_metrics);
    }
    
    #[test]
    fn test_basic_statistics() {
        let graph = create_test_graph();
        let analyzer = GraphStatisticsAnalyzer::new();
        
        let stats = analyzer.compute_basic_statistics(&graph);
        
        println!("Actual node count: {}, Expected: 6", stats.total_nodes);
        assert_eq!(stats.total_nodes, 5); // Fixed: should be 5 nodes (main.py, utils.py, config.py, test.py, isolated.py)
        assert_eq!(stats.total_edges, 5);
        assert!(stats.graph_density > 0.0);
        assert!(stats.graph_density < 1.0);
        assert_eq!(stats.isolated_nodes, 1); // isolated.py
    }
    
    #[test]
    fn test_degree_statistics() {
        let analyzer = GraphStatisticsAnalyzer::new();
        let degrees = vec![0, 1, 1, 2, 3, 5, 8];
        
        let stats = analyzer.compute_degree_stats(&degrees);
        
        assert_eq!(stats.min, 0);
        assert_eq!(stats.max, 8);
        assert!((stats.mean - 2.857).abs() < 0.01); // 20/7
        assert_eq!(stats.median, 2.0);
        assert!(stats.std_dev > 0.0);
    }
    
    #[test]
    fn test_percentile_calculation() {
        let analyzer = GraphStatisticsAnalyzer::new();
        let sorted_values = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        
        assert_eq!(analyzer.percentile(&sorted_values, 0.0), 1.0);
        assert_eq!(analyzer.percentile(&sorted_values, 50.0), 5.5);
        assert_eq!(analyzer.percentile(&sorted_values, 100.0), 10.0);
        assert!((analyzer.percentile(&sorted_values, 25.0) - 3.25).abs() < 0.01);
    }
    
    #[test]
    fn test_histogram_computation() {
        let analyzer = GraphStatisticsAnalyzer::new();
        let degrees = vec![1, 1, 2, 2, 2, 3];
        
        let histogram = analyzer.compute_histogram(&degrees);
        
        assert_eq!(histogram[&1], 2);
        assert_eq!(histogram[&2], 3);
        assert_eq!(histogram[&3], 1);
    }
    
    #[test]
    fn test_power_law_estimation() {
        let analyzer = GraphStatisticsAnalyzer::new();
        
        // Power-law-like distribution
        let degrees = vec![1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20];
        let alpha = analyzer.estimate_power_law_alpha(&degrees);
        
        assert!(alpha.is_some());
        let alpha_val = alpha.unwrap();
        assert!(alpha_val > 0.0);
        assert!(alpha_val < 5.0); // Reasonable range
        
        println!("Estimated power-law alpha: {:.3}", alpha_val);
    }
    
    #[test]
    fn test_clustering_coefficient() {
        let mut graph = DependencyGraph::new();
        
        // Create a triangle: A -> B, B -> C, C -> A
        graph.add_edge("A".to_string(), "B".to_string()).unwrap();
        graph.add_edge("B".to_string(), "C".to_string()).unwrap();
        graph.add_edge("C".to_string(), "A".to_string()).unwrap();
        
        let analyzer = GraphStatisticsAnalyzer::new();
        let clustering = analyzer.local_clustering_coefficient(&graph, &"A".to_string());
        
        // Should be high since A's neighbors (B and C) are connected
        assert!(clustering >= 0.0);
        assert!(clustering <= 1.0);
        println!("Clustering coefficient for A: {:.3}", clustering);
    }
    
    #[test]
    fn test_bfs_distances() {
        let graph = create_test_graph();
        let analyzer = GraphStatisticsAnalyzer::new();
        
        let distances = analyzer.bfs_distances(&graph, &"main.py".to_string());
        
        assert_eq!(distances["main.py"], 0);
        assert!(distances.contains_key("utils.py"));
        assert!(distances.contains_key("config.py"));
        assert!(distances["utils.py"] <= distances["config.py"]);
    }
    
    #[test]
    fn test_structural_patterns() {
        let graph = create_test_graph();
        let analyzer = GraphStatisticsAnalyzer::new();
        
        let patterns = analyzer.identify_structural_patterns(&graph).unwrap();
        
        // main.py should be a hub (high out-degree)
        let main_py_hub = patterns.hubs.iter().find(|node| node.node_id == "main.py");
        assert!(main_py_hub.is_some());
        
        // config.py should be an authority (high in-degree)
        let config_py_auth = patterns.authorities.iter().find(|node| node.node_id == "config.py");
        assert!(config_py_auth.is_some());
        
        // isolated.py should be in isolated nodes
        assert!(patterns.isolated_nodes.contains(&"isolated.py".to_string()));
    }
    
    #[test]
    fn test_full_analysis() {
        let graph = create_test_graph();
        let analyzer = GraphStatisticsAnalyzer::new();
        
        let analysis = analyzer.analyze(&graph).unwrap();
        
        // Basic checks
        assert_eq!(analysis.basic_stats.total_nodes, 5); // Fixed: should be 5 nodes
        assert_eq!(analysis.basic_stats.total_edges, 5);
        
        // Degree distribution
        assert!(analysis.degree_distribution.in_degree.mean >= 0.0);
        assert!(analysis.degree_distribution.out_degree.mean >= 0.0);
        
        // Connectivity
        assert!(analysis.connectivity.graph_density >= 0.0);
        assert!(analysis.connectivity.graph_density <= 1.0);
        
        // Performance profile
        assert!(analysis.performance_profile.pagerank_memory_estimate_mb >= 0.0);
        assert!(analysis.performance_profile.pagerank_time_estimate_ms >= 0);
        
        // Analysis metadata (duration may be 0 on fast systems)
        assert!(analysis.analysis_metadata.analysis_duration_ms >= 0);
        assert_eq!(analysis.analysis_metadata.version, env!("CARGO_PKG_VERSION"));
    }
    
    #[test]
    fn test_summary_report() {
        let graph = create_test_graph();
        let analyzer = GraphStatisticsAnalyzer::new();
        let analysis = analyzer.analyze(&graph).unwrap();
        
        let summary = analysis.summary_report();
        
        assert!(summary.contains("Graph Analysis Summary Report"));
        assert!(summary.contains("Basic Statistics"));
        assert!(summary.contains("Degree Distribution"));
        assert!(summary.contains("Connectivity"));
        assert!(summary.contains("Structural Patterns"));
        assert!(summary.contains("Import Insights"));
        assert!(summary.contains("Performance Profile"));
        
        println!("Summary Report:\n{}", summary);
    }
    
    #[test]
    fn test_important_nodes_summary() {
        let graph = create_test_graph();
        let analyzer = GraphStatisticsAnalyzer::new();
        let analysis = analyzer.analyze(&graph).unwrap();
        
        let important_nodes = analysis.important_nodes_summary();
        
        assert!(!important_nodes.is_empty());
        assert_eq!(important_nodes.len(), 2); // Hubs and Authorities
        
        for (category, nodes) in &important_nodes {
            println!("{}: {:?}", category, nodes);
        }
    }
    
    #[test]
    fn test_empty_graph_analysis() {
        let graph = DependencyGraph::new();
        let analyzer = GraphStatisticsAnalyzer::new();
        
        let analysis = analyzer.analyze(&graph).unwrap();
        
        assert_eq!(analysis.basic_stats.total_nodes, 0);
        assert_eq!(analysis.basic_stats.total_edges, 0);
        assert_eq!(analysis.degree_distribution.in_degree.mean, 0.0);
        assert!(analysis.structural_patterns.hubs.is_empty());
        assert!(analysis.structural_patterns.authorities.is_empty());
    }
}