echo_orchestration 0.1.4

//! DAG dependency analysis (cycle detection, topological sort, dependency chain query, Mermaid visualization)

use super::manager::TaskManager;
use std::collections::HashMap;

impl TaskManager {
    /// Detect cyclic dependencies, return all cycle paths
    pub fn detect_circular_dependencies(&self) -> Vec<Vec<String>> {
        let mut cycles = Vec::new();
        let mut visited: HashMap<String, super::manager::VisitState> = HashMap::new();
        let mut path: Vec<String> = Vec::new();

        let task_ids: Vec<String> = self.tasks.iter().map(|r| r.key().clone()).collect();
        for task_id in task_ids {
            if visited.get(&task_id) != Some(&super::manager::VisitState::Visited) {
                self.dfs_detect_cycle(&task_id, &mut visited, &mut path, &mut cycles);
            }
        }

        cycles
    }

    /// Get topological sort (returns error if cyclic dependencies exist)
    pub fn get_topological_order(&self) -> Result<Vec<String>, String> {
        let cycles = self.detect_circular_dependencies();
        if !cycles.is_empty() {
            let cycle_strs: Vec<String> = cycles
                .iter()
                .map(|cycle| format!("[{}]", cycle.join(" -> ")))
                .collect();
            return Err(format!(
                "Cyclic dependency exists, cannot perform topological sort: {}",
                cycle_strs.join(", ")
            ));
        }

        // Kahn's algorithm for topological sort
        let mut in_degree: HashMap<String, usize> = HashMap::new();
        let mut adj_list: HashMap<String, Vec<String>> = HashMap::new();

        let task_ids: Vec<String> = self.tasks.iter().map(|r| r.key().clone()).collect();
        for task_id in &task_ids {
            in_degree.insert(task_id.clone(), 0);
            adj_list.insert(task_id.clone(), Vec::new());
        }

        for entry in self.tasks.iter() {
            let task_id = entry.key();
            let task = entry.value();
            for dep_id in &task.dependencies {
                if let Some(adj) = adj_list.get_mut(dep_id) {
                    adj.push(task_id.clone());
                }
                if let Some(degree) = in_degree.get_mut(task_id) {
                    *degree += 1;
                }
            }
        }

        let mut queue: Vec<String> = in_degree
            .iter()
            .filter(|&(_, &deg)| deg == 0)
            .map(|(id, _)| id.clone())
            .collect();
        queue.sort_by(|a, b| {
            self.tasks
                .get(a)
                .and_then(|t| self.tasks.get(b).map(|u| u.priority.cmp(&t.priority)))
                .unwrap_or(std::cmp::Ordering::Equal)
        });

        let mut result = Vec::new();

        while let Some(task_id) = queue.pop() {
            result.push(task_id.clone());

            if let Some(adj) = adj_list.get(&task_id) {
                for neighbor in adj {
                    if let Some(degree) = in_degree.get_mut(neighbor) {
                        *degree -= 1;
                        if *degree == 0 {
                            queue.push(neighbor.clone());
                        }
                    }
                }
            }
        }

        Ok(result)
    }

    /// Generate a visualization of the dependency graph (Mermaid format)
    pub fn visualize_dependencies(&self) -> String {
        let mut mermaid = String::from("graph TD\n");

        for entry in self.tasks.iter() {
            let task_id = entry.key();
            let task = entry.value();
            for dep_id in &task.dependencies {
                mermaid.push_str(&format!(
                    "  {}[{}] --> {}[{}]\n",
                    dep_id, dep_id, task_id, task_id
                ));
            }
        }

        mermaid
    }

    /// Get dependency chain (from the specified task to the root node)
    pub fn get_dependency_chain(&self, task_id: &str) -> Vec<Vec<String>> {
        let mut chains = Vec::new();
        let mut current_chain = Vec::new();
        self.get_dependency_chain_recursive(task_id, &mut current_chain, &mut chains);
        chains
    }
}