agileplus-domain 0.3.0

use crate::intent_graph::*;
use crate::query::topological_sort;
use std::collections::{HashMap, HashSet};

/// Result of diffing two graphs.
#[derive(Debug, Clone, PartialEq)]
pub struct GraphDiff {
    pub added_nodes: Vec<Node>,
    pub removed_nodes: Vec<Node>,
    pub modified_nodes: Vec<(Node, Node)>,
    pub added_edges: Vec<Edge>,
    pub removed_edges: Vec<Edge>,
}

/// Merge two graphs into a new graph. Nodes and edges are deduplicated by ID.
pub fn merge_graphs(a: &IntentGraph, b: &IntentGraph) -> IntentGraph {
    let mut result = a.clone();
    let mut seen_nodes: HashSet<NodeId> = result.nodes.iter().map(|n| n.id.clone()).collect();
    let mut seen_edges: HashSet<String> = result.edges.iter().map(|e| e.id.clone()).collect();

    for node in &b.nodes {
        if !seen_nodes.contains(&node.id) {
            seen_nodes.insert(node.id.clone());
            result.add_node(node.clone());
        }
    }
    for edge in &b.edges {
        if !seen_edges.contains(&edge.id) {
            seen_edges.insert(edge.id.clone());
            result.add_edge(edge.clone());
        }
    }
    result.update_counts();
    result
}

/// Extract an induced subgraph from the given set of node IDs.
pub fn subgraph(graph: &IntentGraph, node_ids: &[NodeId]) -> IntentGraph {
    let id_set: HashSet<NodeId> = node_ids.iter().cloned().collect();
    let mut nodes: Vec<Node> = Vec::new();
    let mut edges: Vec<Edge> = Vec::new();

    for node in &graph.nodes {
        if id_set.contains(&node.id) {
            nodes.push(node.clone());
        }
    }
    for edge in &graph.edges {
        if id_set.contains(&edge.source) && id_set.contains(&edge.target) {
            edges.push(edge.clone());
        }
    }

    let mut result = IntentGraph::new(graph.metadata.clone());
    result.nodes = nodes;
    result.edges = edges;
    result.update_counts();
    result
}

/// Compute the difference between two graphs.
pub fn graph_diff(old: &IntentGraph, new: &IntentGraph) -> GraphDiff {
    let old_nodes: HashMap<NodeId, &Node> = old.nodes.iter().map(|n| (n.id.clone(), n)).collect();
    let new_nodes: HashMap<NodeId, &Node> = new.nodes.iter().map(|n| (n.id.clone(), n)).collect();
    let old_edges: HashMap<String, &Edge> = old.edges.iter().map(|e| (e.id.clone(), e)).collect();
    let new_edges: HashMap<String, &Edge> = new.edges.iter().map(|e| (e.id.clone(), e)).collect();

    let mut added_nodes = Vec::new();
    let mut removed_nodes = Vec::new();
    let mut modified_nodes = Vec::new();

    for (id, node) in &new_nodes {
        if let Some(old_node) = old_nodes.get(id) {
            if *old_node != *node {
                modified_nodes.push(((*old_node).clone(), (*node).clone()));
            }
        } else {
            added_nodes.push((*node).clone());
        }
    }
    for (id, node) in &old_nodes {
        if !new_nodes.contains_key(id) {
            removed_nodes.push((*node).clone());
        }
    }

    let mut added_edges = Vec::new();
    let mut removed_edges = Vec::new();
    for (id, edge) in &new_edges {
        if !old_edges.contains_key(id) {
            added_edges.push((*edge).clone());
        }
    }
    for (id, edge) in &old_edges {
        if !new_edges.contains_key(id) {
            removed_edges.push((*edge).clone());
        }
    }

    GraphDiff {
        added_nodes,
        removed_nodes,
        modified_nodes,
        added_edges,
        removed_edges,
    }
}

/// Compute the longest path from any root to the given node.
/// Returns the depth (number of edges) along the longest path.
pub fn compute_depth(graph: &IntentGraph, node_id: &NodeId) -> usize {
    let mut memo: HashMap<NodeId, usize> = HashMap::new();
    let mut visiting: HashSet<NodeId> = HashSet::new();
    compute_depth_recursive(graph, node_id, &mut memo, &mut visiting)
}

fn compute_depth_recursive(
    graph: &IntentGraph,
    node_id: &NodeId,
    memo: &mut HashMap<NodeId, usize>,
    visiting: &mut HashSet<NodeId>,
) -> usize {
    if let Some(&d) = memo.get(node_id) {
        return d;
    }
    if !visiting.insert(node_id.clone()) {
        return 0;
    }
    let incoming = graph.edges_to(node_id);
    let depth = if incoming.is_empty() {
        0
    } else {
        incoming
            .iter()
            .map(|e| compute_depth_recursive(graph, &e.source, memo, visiting) + 1)
            .max()
            .unwrap_or(0)
    };
    memo.insert(node_id.clone(), depth);
    visiting.remove(node_id);
    depth
}

/// Compute the critical path in the DAG: the longest path from any root to any leaf.
/// Returns the ordered list of nodes along that path.
pub fn compute_critical_path(graph: &IntentGraph) -> Vec<&Node> {
    let sorted = match topological_sort(graph) {
        Ok(s) => s,
        Err(_) => return Vec::new(),
    };

    let mut dist: HashMap<NodeId, usize> = HashMap::new();
    let mut prev: HashMap<NodeId, Option<NodeId>> = HashMap::new();

    for node in &sorted {
        dist.insert(node.id.clone(), 0);
        prev.insert(node.id.clone(), None);
    }

    for node in &sorted {
        let node_dist = *dist.get(&node.id).unwrap_or(&0);
        for edge in graph.edges_from(&node.id) {
            let target = &edge.target;
            let new_dist = node_dist + 1;
            if new_dist > *dist.get(target).unwrap_or(&0) {
                dist.insert(target.clone(), new_dist);
                prev.insert(target.clone(), Some(node.id.clone()));
            }
        }
    }

    let max_node_id = dist.iter().max_by_key(|(_, &d)| d).map(|(id, _)| id.clone());
    if let Some(mut current_id) = max_node_id {
        let mut path: Vec<&Node> = Vec::new();
        while let Some(node) = graph.node_by_id(&current_id) {
            path.push(node);
            match prev.get(&current_id).and_then(|p| p.as_ref()) {
                Some(next_id) => current_id = next_id.clone(),
                None => break,
            }
        }
        path.reverse();
        return path;
    }
    Vec::new()
}