analyssa 0.4.1

//! Indexed graph wrapper for domain-typed nodes.
//!
//! This module provides [`IndexedGraph`], a convenience wrapper around [`DirectedGraph`]
//! that automatically handles the mapping between domain types (like `AssemblyIdentity`
//! or `TableId`) and internal `NodeId` indices.
//!
//! # Motivation
//!
//! When working with graph algorithms, domain code often needs to:
//! 1. Build a graph from domain-specific types
//! 2. Run algorithms that work with `NodeId`
//! 3. Map results back to domain types
//!
//! `IndexedGraph` encapsulates this pattern, providing a cleaner API.
//!
//! # Examples
//!
//! ```rust
//! use analyssa::graph::IndexedGraph;
//!
//! // Create a graph with string keys
//! let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();
//!
//! // Add nodes using domain types directly
//! graph.add_node("A");
//! graph.add_node("B");
//! graph.add_node("C");
//!
//! // Add edges using domain types
//! graph.add_edge("A", "B", ()).unwrap();
//! graph.add_edge("B", "C", ()).unwrap();
//! graph.add_edge("C", "A", ()).unwrap(); // Creates a cycle
//!
//! // Run algorithms - results are automatically mapped back
//! let cycle = graph.find_cycle_from(&"A").unwrap();
//! assert_eq!(cycle, vec!["A", "B", "C", "A"]);
//! ```

use std::{
    collections::{HashMap, HashSet},
    hash::Hash,
};

use crate::{
    Result,
    graph::{DirectedGraph, NodeId, algorithms},
};

/// A graph wrapper that provides automatic mapping between domain types and `NodeId`.
///
/// `IndexedGraph<K, E>` stores nodes indexed by keys of type `K` (which must be
/// `Hash + Eq + Clone`) and edges with data of type `E`. It maintains bidirectional
/// mappings for efficient lookups in both directions.
///
/// # Type Parameters
///
/// * `K` - The domain key type for nodes (e.g., `AssemblyIdentity`, `TableId`)
/// * `E` - The edge data type
///
/// # Thread Safety
///
/// `IndexedGraph<K, E>` is `Send` and `Sync` when both `K` and `E` are.
#[derive(Debug, Clone)]
pub struct IndexedGraph<K, E>
where
    K: Hash + Eq + Clone,
{
    /// The underlying directed graph (nodes store unit type, keys are separate)
    graph: DirectedGraph<'static, (), E>,
    /// Map from domain key to `NodeId`
    key_to_node: HashMap<K, NodeId>,
    /// Map from `NodeId` to domain key
    node_to_key: HashMap<NodeId, K>,
    /// Existing `(source, target)` edges, for O(1) duplicate detection in
    /// [`add_edge`](Self::add_edge) instead of scanning the source's successors.
    edge_set: HashSet<(NodeId, NodeId)>,
}

impl<K, E> Default for IndexedGraph<K, E>
where
    K: Hash + Eq + Clone,
{
    fn default() -> Self {
        Self::new()
    }
}

impl<K, E> IndexedGraph<K, E>
where
    K: Hash + Eq + Clone,
{
    /// Creates a new empty indexed graph.
    #[must_use]
    pub fn new() -> Self {
        Self {
            graph: DirectedGraph::new(),
            key_to_node: HashMap::new(),
            node_to_key: HashMap::new(),
            edge_set: HashSet::new(),
        }
    }

    /// Creates a new indexed graph with pre-allocated capacity.
    #[must_use]
    pub fn with_capacity(node_capacity: usize, edge_capacity: usize) -> Self {
        Self {
            graph: DirectedGraph::with_capacity(node_capacity, edge_capacity),
            key_to_node: HashMap::with_capacity(node_capacity),
            node_to_key: HashMap::with_capacity(node_capacity),
            edge_set: HashSet::with_capacity(edge_capacity),
        }
    }

    /// Adds a node with the given key, or returns the existing `NodeId` if already present.
    ///
    /// This method is idempotent - calling it multiple times with the same key
    /// will always return the same `NodeId`.
    ///
    /// # Arguments
    ///
    /// * `key` - The domain key for this node
    ///
    /// # Returns
    ///
    /// The `NodeId` associated with this key.
    pub fn add_node(&mut self, key: K) -> NodeId {
        if let Some(&node_id) = self.key_to_node.get(&key) {
            return node_id;
        }

        let node_id = self.graph.add_node(());
        self.key_to_node.insert(key.clone(), node_id);
        self.node_to_key.insert(node_id, key);
        node_id
    }

    /// Adds a directed edge between two nodes identified by their keys.
    ///
    /// If either node doesn't exist, it will be created automatically.
    ///
    /// # Arguments
    ///
    /// * `from` - The source node key
    /// * `to` - The target node key
    /// * `data` - The edge data
    ///
    /// # Returns
    ///
    /// * `Ok(true)` if a new edge was added
    /// * `Ok(false)` if the edge already existed
    /// * `Err(_)` if the edge could not be added
    ///
    /// # Errors
    ///
    /// Returns an error if the underlying graph operation fails.
    pub fn add_edge(&mut self, from: K, to: K, data: E) -> Result<bool>
    where
        E: Clone,
    {
        let from_node = self.add_node(from);
        let to_node = self.add_node(to);

        // O(1) duplicate check via the edge set.
        if !self.edge_set.insert((from_node, to_node)) {
            return Ok(false);
        }

        self.graph.add_edge(from_node, to_node, data)?;
        Ok(true)
    }

    /// Returns the `NodeId` for a given key, if it exists.
    #[must_use]
    pub fn get_node_id(&self, key: &K) -> Option<NodeId> {
        self.key_to_node.get(key).copied()
    }

    /// Returns the key for a given `NodeId`, if it exists.
    #[must_use]
    pub fn get_key(&self, node_id: NodeId) -> Option<&K> {
        self.node_to_key.get(&node_id)
    }

    /// Returns the number of nodes in the graph.
    #[must_use]
    pub fn node_count(&self) -> usize {
        self.graph.node_count()
    }

    /// Returns the number of edges in the graph.
    #[must_use]
    pub fn edge_count(&self) -> usize {
        self.graph.edge_count()
    }

    /// Returns `true` if the graph contains no nodes.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.graph.is_empty()
    }

    /// Returns a reference to the underlying `DirectedGraph`.
    ///
    /// This is useful when you need to pass the graph to algorithms that
    /// work with `DirectedGraph` directly.
    #[must_use]
    pub fn inner(&self) -> &DirectedGraph<'static, (), E> {
        &self.graph
    }

    /// Returns an iterator over all keys in the graph.
    pub fn keys(&self) -> impl Iterator<Item = &K> {
        self.key_to_node.keys()
    }

    /// Maps a vector of `NodeId`s back to domain keys.
    ///
    /// Nodes that don't have a corresponding key are skipped.
    #[must_use]
    pub fn map_nodes_to_keys(&self, nodes: &[NodeId]) -> Vec<K> {
        nodes
            .iter()
            .filter_map(|node_id| self.node_to_key.get(node_id).cloned())
            .collect()
    }

    /// Maps a vector of SCCs (each being a `Vec<NodeId>`) back to domain keys.
    #[must_use]
    pub fn map_sccs_to_keys(&self, sccs: &[Vec<NodeId>]) -> Vec<Vec<K>> {
        sccs.iter().map(|scc| self.map_nodes_to_keys(scc)).collect()
    }
}

// Algorithm convenience methods
impl<K, E> IndexedGraph<K, E>
where
    K: Hash + Eq + Clone,
{
    /// Finds a cycle in the graph starting from the given key.
    ///
    /// Returns the cycle as a vector of domain keys if found, `None` otherwise.
    #[must_use]
    pub fn find_cycle_from(&self, start: &K) -> Option<Vec<K>> {
        let start_node = self.key_to_node.get(start)?;
        let cycle_nodes = algorithms::find_cycle(&self.graph, *start_node)?;
        Some(self.map_nodes_to_keys(&cycle_nodes))
    }

    /// Checks if the graph contains any cycle reachable from the given key.
    #[must_use]
    pub fn has_cycle_from(&self, start: &K) -> bool {
        self.key_to_node
            .get(start)
            .is_some_and(|&start_node| algorithms::has_cycle(&self.graph, start_node))
    }

    /// Finds any cycle in the graph.
    ///
    /// Returns the cycle in the lowest-numbered strongly connected component
    /// that has one, so the answer is **deterministic**: iterating
    /// `key_to_node.values()` and returning the first hit made the result depend
    /// on `HashMap` order, which varies run to run — and a downstream
    /// content-addressed pipeline needs byte-identical output.
    ///
    /// # Complexity
    ///
    /// O(V + E), one Tarjan pass. Restarting `find_cycle` from every node was
    /// O(V·(V+E)) because each restart re-walked the graph with fresh state.
    #[must_use]
    pub fn find_any_cycle(&self) -> Option<Vec<K>> {
        // Components arrive in a deterministic order and a cycle exists exactly
        // where a component has more than one node, or a single node with an
        // edge to itself.
        for component in algorithms::strongly_connected_components(&self.graph) {
            if component.len() > 1 {
                return Some(self.map_nodes_to_keys(&component));
            }
            if let Some(&only) = component.first()
                && self.graph.successors(only).any(|succ| succ == only)
            {
                return Some(self.map_nodes_to_keys(&component));
            }
        }
        None
    }

    /// Computes strongly connected components.
    ///
    /// Returns SCCs as vectors of domain keys, in reverse topological order.
    #[must_use]
    pub fn strongly_connected_components(&self) -> Vec<Vec<K>> {
        let sccs = algorithms::strongly_connected_components(&self.graph);
        self.map_sccs_to_keys(&sccs)
    }

    /// Computes a topological ordering of the graph.
    ///
    /// Returns `Some(order)` if the graph is acyclic, `None` if it contains cycles.
    #[must_use]
    pub fn topological_sort(&self) -> Option<Vec<K>> {
        let order = algorithms::topological_sort(&self.graph)?;
        Some(self.map_nodes_to_keys(&order))
    }
}

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

    /// `find_any_cycle` iterated a `HashMap`'s values, so which cycle it
    /// reported varied between runs of the same binary. The downstream
    /// similarity pipeline is content-addressed and requires byte-identical
    /// output, so a nondeterministic answer is a correctness problem there, not
    /// just an aesthetic one.
    #[test]
    fn find_any_cycle_is_deterministic() {
        let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();
        // Two disjoint cycles, so there is a real choice to make.
        for (from, to) in [("a", "b"), ("b", "a"), ("x", "y"), ("y", "x")] {
            let _ = graph.add_edge(from, to, ());
        }

        let first = graph.find_any_cycle().expect("the graph has cycles");
        for _ in 0..16 {
            let again = graph.find_any_cycle().expect("still cyclic");
            assert_eq!(again, first, "the reported cycle must not vary");
        }

        // And a self-loop counts as a cycle.
        let mut selfish: IndexedGraph<&str, ()> = IndexedGraph::new();
        let _ = selfish.add_edge("n", "n", ());
        assert_eq!(selfish.find_any_cycle(), Some(vec!["n"]));

        // An acyclic graph reports none.
        let mut dag: IndexedGraph<&str, ()> = IndexedGraph::new();
        let _ = dag.add_edge("a", "b", ());
        let _ = dag.add_edge("b", "c", ());
        assert_eq!(dag.find_any_cycle(), None);
    }

    #[test]
    fn test_indexed_graph_basic() {
        let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();

        let a = graph.add_node("A");
        let b = graph.add_node("B");

        assert_eq!(graph.node_count(), 2);
        assert_eq!(graph.get_node_id(&"A"), Some(a));
        assert_eq!(graph.get_node_id(&"B"), Some(b));
        assert_eq!(graph.get_key(a), Some(&"A"));
        assert_eq!(graph.get_key(b), Some(&"B"));
    }

    #[test]
    fn test_indexed_graph_idempotent_add() {
        let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();

        let a1 = graph.add_node("A");
        let a2 = graph.add_node("A"); // Same key

        assert_eq!(a1, a2);
        assert_eq!(graph.node_count(), 1);
    }

    #[test]
    fn test_indexed_graph_add_edge() {
        let mut graph: IndexedGraph<&str, i32> = IndexedGraph::new();

        // Nodes created automatically
        assert!(graph.add_edge("A", "B", 10).unwrap());
        assert!(graph.add_edge("B", "C", 20).unwrap());

        assert_eq!(graph.node_count(), 3);
        assert_eq!(graph.edge_count(), 2);

        // Duplicate edge not added
        assert!(!graph.add_edge("A", "B", 10).unwrap());
        assert_eq!(graph.edge_count(), 2);
    }

    #[test]
    fn test_indexed_graph_find_cycle() {
        let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();

        let _ = graph.add_edge("A", "B", ()).unwrap();
        let _ = graph.add_edge("B", "C", ()).unwrap();
        graph.add_edge("C", "A", ()).unwrap(); // Creates cycle

        let cycle = graph.find_cycle_from(&"A");
        assert!(cycle.is_some());

        let cycle = cycle.unwrap();
        assert!(cycle.contains(&"A"));
        assert!(cycle.contains(&"B"));
        assert!(cycle.contains(&"C"));
    }

    #[test]
    fn test_indexed_graph_no_cycle() {
        let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();

        let _ = graph.add_edge("A", "B", ()).unwrap();
        let _ = graph.add_edge("B", "C", ()).unwrap();
        // No back edge

        assert!(graph.find_cycle_from(&"A").is_none());
        assert!(!graph.has_cycle_from(&"A"));
    }

    #[test]
    fn test_indexed_graph_topological_sort() {
        let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();

        // A -> B -> D
        // A -> C -> D
        let _ = graph.add_edge("A", "B", ()).unwrap();
        let _ = graph.add_edge("A", "C", ()).unwrap();
        let _ = graph.add_edge("B", "D", ()).unwrap();
        let _ = graph.add_edge("C", "D", ()).unwrap();

        let order = graph.topological_sort();
        assert!(order.is_some());

        let order = order.unwrap();
        assert_eq!(order.len(), 4);

        // A must come before B, C; B and C must come before D
        let pos = |k: &str| order.iter().position(|&x| x == k).unwrap();
        assert!(pos("A") < pos("B"));
        assert!(pos("A") < pos("C"));
        assert!(pos("B") < pos("D"));
        assert!(pos("C") < pos("D"));
    }

    #[test]
    fn test_indexed_graph_topological_sort_with_cycle() {
        let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();

        let _ = graph.add_edge("A", "B", ()).unwrap();
        graph.add_edge("B", "A", ()).unwrap(); // Cycle

        assert!(graph.topological_sort().is_none());
    }

    #[test]
    fn test_indexed_graph_scc() {
        let mut graph: IndexedGraph<&str, ()> = IndexedGraph::new();

        // Two SCCs: {A, B} and {C}
        let _ = graph.add_edge("A", "B", ()).unwrap();
        graph.add_edge("B", "A", ()).unwrap(); // A <-> B cycle
        let _ = graph.add_edge("B", "C", ()).unwrap();

        let sccs = graph.strongly_connected_components();
        assert_eq!(sccs.len(), 2);

        // One SCC has 2 elements, one has 1
        let mut sizes: Vec<usize> = sccs.iter().map(|scc| scc.len()).collect();
        sizes.sort();
        assert_eq!(sizes, vec![1, 2]);
    }

    #[test]
    fn test_indexed_graph_with_integers() {
        let mut graph: IndexedGraph<i32, &str> = IndexedGraph::new();

        let _ = graph.add_edge(1, 2, "one-two").unwrap();
        let _ = graph.add_edge(2, 3, "two-three").unwrap();

        assert_eq!(graph.node_count(), 3);
        assert!(graph.topological_sort().is_some());
    }
}