beads_rust 0.1.42

//! Graph command implementation.
//!
//! Visualizes dependency graphs with focus on reverse dependencies (dependents).
//!
//! - `br graph <issue-id>`: Show all dependents of an issue (what depends on it)
//! - `br graph --all`: Show connected components for all nonterminal issues

use super::{auto_import_storage_ctx_if_stale, resolve_issue_id};
use crate::cli::GraphArgs;
use crate::config;
use crate::error::{BeadsError, Result};
use crate::model::{DependencyType, Issue, Priority, Status};
use crate::output::{OutputContext, OutputMode};
use crate::storage::{ListFilters, SqliteStorage};
use crate::util::id::{IdResolver, ResolverConfig};
use rich_rust::prelude::*;
use serde::Serialize;
use std::collections::{HashMap, HashSet, VecDeque};
use std::str::FromStr;
use tracing::debug;
use unicode_width::UnicodeWidthStr;

/// JSON output for a single node in the graph.
#[derive(Debug, Clone, Serialize)]
struct GraphNode {
    id: String,
    title: String,
    status: String,
    priority: i32,
    depth: usize,
}

/// JSON output for the graph command (single issue mode).
#[derive(Debug, Serialize)]
struct SingleGraphOutput {
    root: String,
    nodes: Vec<GraphNode>,
    edges: Vec<(String, String)>,
    count: usize,
}

/// JSON output for connected component.
#[derive(Debug, Serialize)]
struct ConnectedComponent {
    nodes: Vec<GraphNode>,
    edges: Vec<(String, String)>,
    roots: Vec<String>,
}

/// JSON output for --all mode.
#[derive(Debug, Serialize)]
struct AllGraphOutput {
    components: Vec<ConnectedComponent>,
    total_nodes: usize,
    total_components: usize,
}

#[derive(Debug)]
struct SingleGraphTraversal {
    traversal_order: Vec<String>,
    issues_by_id: HashMap<String, Issue>,
    edges: Vec<(String, String)>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum HumanGraphRenderMode {
    Rich,
    Compact,
    Plain,
}

/// Execute the graph command.
///
/// # Errors
///
/// Returns an error if database operations fail or if inputs are invalid.
pub fn execute(args: &GraphArgs, cli: &config::CliOverrides, ctx: &OutputContext) -> Result<()> {
    let beads_dir = config::discover_beads_dir_with_cli(cli)?;
    let route_cli = routed_cli_for_graph(cli, args, &beads_dir)?;
    let storage_ctx = open_storage_for_graph(args, &route_cli, &beads_dir)?;
    execute_with_storage_ctx(args, &route_cli, ctx, &beads_dir, &storage_ctx)
}

fn routed_cli_for_graph(
    cli: &config::CliOverrides,
    args: &GraphArgs,
    local_beads_dir: &std::path::Path,
) -> Result<config::CliOverrides> {
    let mut route_cli = cli.clone();
    if let Some(issue_input) = args.issue.as_deref()
        && !args.all
        && config::routing::resolve_route(issue_input, local_beads_dir)?.is_external
    {
        route_cli.db = None;
    }
    Ok(route_cli)
}

fn open_storage_for_graph(
    args: &GraphArgs,
    cli: &config::CliOverrides,
    local_beads_dir: &std::path::Path,
) -> Result<config::OpenStorageResult> {
    if let Some(issue_input) = args.issue.as_deref()
        && !args.all
    {
        let route = config::routing::resolve_route(issue_input, local_beads_dir)?;
        let mut storage_ctx = config::open_storage_with_cli(&route.beads_dir, cli)?;
        auto_import_storage_ctx_if_stale(&mut storage_ctx, cli)?;
        return Ok(storage_ctx);
    }

    let mut storage_ctx = config::open_storage_with_cli(local_beads_dir, cli)?;
    auto_import_storage_ctx_if_stale(&mut storage_ctx, cli)?;
    Ok(storage_ctx)
}

/// Execute the graph command using storage that was already opened by the caller.
///
/// # Errors
///
/// Returns an error if database operations fail or if inputs are invalid.
pub fn execute_with_storage_ctx(
    args: &GraphArgs,
    cli: &config::CliOverrides,
    ctx: &OutputContext,
    local_beads_dir: &std::path::Path,
    storage_ctx: &config::OpenStorageResult,
) -> Result<()> {
    if let Some(issue_input) = args.issue.as_deref()
        && !args.all
    {
        let route = config::routing::resolve_route(issue_input, local_beads_dir)?;
        if route.is_external {
            let mut route_cli = cli.clone();
            route_cli.db = None;
            let mut routed_storage_ctx =
                config::open_storage_with_cli(&route.beads_dir, &route_cli)?;
            auto_import_storage_ctx_if_stale(&mut routed_storage_ctx, &route_cli)?;
            return execute_graph_with_storage_ctx(args, &route_cli, ctx, &routed_storage_ctx);
        }
    }

    execute_graph_with_storage_ctx(args, cli, ctx, storage_ctx)
}

fn execute_graph_with_storage_ctx(
    args: &GraphArgs,
    cli: &config::CliOverrides,
    ctx: &OutputContext,
    storage_ctx: &config::OpenStorageResult,
) -> Result<()> {
    let config_layer = storage_ctx.load_config(cli)?;
    let id_config = config::id_config_from_layer(&config_layer);
    let resolver = IdResolver::new(ResolverConfig::with_prefix(id_config.prefix));
    if args.all {
        graph_all(&storage_ctx.storage, args.compact, ctx)
    } else {
        let issue_id = args.issue.as_ref().ok_or_else(|| {
            BeadsError::validation("issue", "Issue ID required unless --all is specified")
        })?;

        let resolved_id = resolve_issue_id(&storage_ctx.storage, &resolver, issue_id)?;
        graph_single(&storage_ctx.storage, &resolved_id, args.compact, ctx)
    }
}

/// Show graph for a single issue (traverse dependents only).
fn graph_single(
    storage: &SqliteStorage,
    root_id: &str,
    compact: bool,
    ctx: &OutputContext,
) -> Result<()> {
    // Verify the root issue exists
    let root_issue = storage
        .get_issue(root_id)?
        .ok_or_else(|| BeadsError::IssueNotFound {
            id: root_id.to_string(),
        })?;

    if ctx.is_quiet() {
        return Ok(());
    }

    let traversal = collect_single_graph(storage, root_id, &root_issue)?;
    let root_nodes = [root_id.to_string()];
    let depths = calculate_depths_from_dependency_edges(
        &traversal.traversal_order,
        &traversal.edges,
        &root_nodes,
    );
    let mut nodes = build_graph_nodes(&traversal.traversal_order, &traversal.issues_by_id, &depths);
    sort_single_graph_nodes(&mut nodes, root_id);

    if ctx.is_json() || ctx.is_toon() {
        let output = SingleGraphOutput {
            root: root_id.to_string(),
            count: nodes.len(),
            nodes,
            edges: traversal.edges,
        };
        if ctx.is_toon() {
            ctx.toon(&output);
        } else {
            ctx.json_pretty(&output);
        }
        return Ok(());
    }

    // Text output
    if nodes.len() == 1 {
        if matches!(ctx.mode(), OutputMode::Rich) {
            render_no_dependents_rich(root_id, &root_issue, ctx);
        } else {
            println!("No dependents for {root_id}");
        }
        return Ok(());
    }

    match human_graph_render_mode(ctx.mode(), compact) {
        HumanGraphRenderMode::Rich => {
            render_single_graph_rich(&nodes, &traversal.edges, &root_issue, ctx);
        }
        HumanGraphRenderMode::Compact => {
            println!(
                "{}",
                format_compact_dependency_edges(root_id, &traversal.edges)
            );
        }
        HumanGraphRenderMode::Plain => {
            render_single_graph_plain(&nodes, &traversal.edges, &root_issue);
        }
    }

    Ok(())
}

/// Show graph for all nonterminal issues.
#[allow(clippy::too_many_lines)]
fn graph_all(storage: &SqliteStorage, compact: bool, ctx: &OutputContext) -> Result<()> {
    if ctx.is_quiet() {
        return Ok(());
    }

    // Get all nonterminal issues
    let filters = ListFilters {
        include_closed: false,
        include_deferred: true,
        include_templates: false,
        ..Default::default()
    };

    let issues = storage.list_issues(&filters)?;
    debug!(count = issues.len(), "Found issues for graph");

    if issues.is_empty() {
        if ctx.is_json() || ctx.is_toon() {
            let output = AllGraphOutput {
                components: vec![],
                total_nodes: 0,
                total_components: 0,
            };
            if ctx.is_toon() {
                ctx.toon(&output);
            } else {
                ctx.json_pretty(&output);
            }
        } else if matches!(ctx.mode(), OutputMode::Rich) {
            render_no_issues_rich(ctx);
        } else {
            println!("No active issues found");
        }
        return Ok(());
    }

    // Build issue lookup and adjacency lists
    let issue_set: HashSet<String> = issues.iter().map(|i| i.id.clone()).collect();
    let issue_map: HashMap<String, &crate::model::Issue> =
        issues.iter().map(|i| (i.id.clone(), i)).collect();

    // Build adjacency list (both directions for connected components)
    let mut adj: HashMap<String, Vec<String>> = HashMap::new();
    let mut blocking_edges: Vec<(String, String)> = Vec::new();

    // Optimize: fetch all dependencies once
    let all_dependencies = storage.get_all_dependency_records()?;

    for issue in &issues {
        adj.entry(issue.id.clone()).or_default();

        // Get dependencies from bulk map
        if let Some(deps) = all_dependencies.get(&issue.id) {
            for dependency in deps {
                if !dependency.dep_type.affects_ready_work() {
                    continue;
                }
                let dep_id = &dependency.depends_on_id;
                // Only include edges within our issue set
                if issue_set.contains(dep_id) {
                    adj.entry(issue.id.clone())
                        .or_default()
                        .push(dep_id.clone());
                    adj.entry(dep_id.clone())
                        .or_default()
                        .push(issue.id.clone());
                    blocking_edges.push((issue.id.clone(), dep_id.clone()));
                }
            }
        }
    }

    // Find connected components using BFS
    let mut visited: HashSet<String> = HashSet::new();
    let mut components: Vec<ConnectedComponent> = Vec::new();

    for issue in &issues {
        if visited.contains(&issue.id) {
            continue;
        }

        // BFS to find all nodes in this component
        let mut component_nodes: Vec<String> = Vec::new();
        let mut queue: VecDeque<String> = VecDeque::new();

        queue.push_back(issue.id.clone());
        visited.insert(issue.id.clone());

        while let Some(current) = queue.pop_front() {
            component_nodes.push(current.clone());

            if let Some(neighbors) = adj.get(&current) {
                for neighbor in neighbors {
                    if !visited.contains(neighbor) {
                        visited.insert(neighbor.clone());
                        queue.push_back(neighbor.clone());
                    }
                }
            }
        }

        // Calculate depths using longest path from roots
        // Roots are issues with no unsatisfied dependencies within the component
        let component_set: HashSet<&String> = component_nodes.iter().collect();
        let (mut depths, mut roots) =
            calculate_depths(&all_dependencies, &component_nodes, &component_set);

        // Build component output
        let mut nodes: Vec<GraphNode> = Vec::new();

        for node_id in &component_nodes {
            if let Some(issue) = issue_map.get(node_id) {
                let depth = depths.remove(node_id).unwrap_or(0);
                nodes.push(GraphNode {
                    id: node_id.clone(),
                    title: issue.title.clone(),
                    status: issue.status.as_str().to_string(),
                    priority: issue.priority.0,
                    depth,
                });
            }
        }

        // Sort by depth, priority, id
        nodes.sort_by(|a, b| {
            a.depth
                .cmp(&b.depth)
                .then(a.priority.cmp(&b.priority))
                .then(a.id.cmp(&b.id))
        });
        roots.sort();

        // Filter edges to this component
        let component_edges: Vec<(String, String)> = blocking_edges
            .iter()
            .filter(|(from, to)| component_set.contains(from) && component_set.contains(to))
            .cloned()
            .collect();

        components.push(ConnectedComponent {
            nodes,
            edges: component_edges,
            roots,
        });
    }

    // Sort components by size (largest first)
    components.sort_by_key(|b| std::cmp::Reverse(b.nodes.len()));

    let total_nodes: usize = components.iter().map(|c| c.nodes.len()).sum();

    if ctx.is_json() || ctx.is_toon() {
        let output = AllGraphOutput {
            total_nodes,
            total_components: components.len(),
            components,
        };
        if ctx.is_toon() {
            ctx.toon(&output);
        } else {
            ctx.json_pretty(&output);
        }
        return Ok(());
    }

    // Text output
    match human_graph_render_mode(ctx.mode(), compact) {
        HumanGraphRenderMode::Rich => render_all_graph_rich(&components, total_nodes, ctx),
        HumanGraphRenderMode::Compact | HumanGraphRenderMode::Plain => {
            let render_compact = matches!(
                human_graph_render_mode(ctx.mode(), compact),
                HumanGraphRenderMode::Compact
            );

            println!(
                "Dependency graph: {} issues in {} component(s)",
                total_nodes,
                components.len()
            );
            println!();

            for (i, component) in components.iter().enumerate() {
                if render_compact {
                    // Compact: one line per component
                    let ids: Vec<&str> = component.nodes.iter().map(|n| n.id.as_str()).collect();
                    println!("Component {}: {}", i + 1, ids.join(", "));
                } else {
                    let roots = if component.roots.is_empty() {
                        "none".to_string()
                    } else {
                        component.roots.join(", ")
                    };
                    let parent_map = build_parent_map(&component.edges);
                    // Detailed view
                    println!(
                        "Component {} ({} issues, roots: {}, by depth):",
                        i + 1,
                        component.nodes.len(),
                        roots
                    );

                    for node in &component.nodes {
                        let indent = "  ".repeat(node.depth + 1);
                        let root_marker = if component.roots.contains(&node.id) {
                            " (root)"
                        } else {
                            ""
                        };
                        let parents =
                            format_parent_list(parent_map.get(&node.id).map(Vec::as_slice));
                        println!(
                            "{}{}: {} [P{}] [{}]{}{}",
                            indent,
                            node.id,
                            node.title,
                            node.priority,
                            node.status,
                            root_marker,
                            parents
                        );
                    }
                    println!();
                }
            }
        }
    }

    Ok(())
}

// Calculate depths for nodes using longest path from roots.
///
/// Returns both the computed depths and the component roots. Roots are issues
/// with no dependencies within the component. Depth is the longest path from
/// any root to the node.
fn calculate_depths(
    all_dependencies: &HashMap<String, Vec<crate::model::Dependency>>,
    nodes: &[String],
    component_set: &HashSet<&String>,
) -> (HashMap<String, usize>, Vec<String>) {
    let dependency_edges = dependency_edges_for_component(all_dependencies, nodes, component_set);
    let dependency_map = build_dependency_map(nodes, &dependency_edges);
    let roots: Vec<String> = nodes
        .iter()
        .filter(|node_id| dependency_map.get(*node_id).is_none_or(Vec::is_empty))
        .cloned()
        .collect();
    let depths = calculate_depths_from_dependency_edges(nodes, &dependency_edges, &roots);
    (depths, roots)
}

fn dependency_edges_for_component(
    all_dependencies: &HashMap<String, Vec<crate::model::Dependency>>,
    nodes: &[String],
    component_set: &HashSet<&String>,
) -> Vec<(String, String)> {
    let mut dependency_edges = Vec::new();

    for node_id in nodes {
        if let Some(deps) = all_dependencies.get(node_id) {
            for dependency in deps {
                if !dependency.dep_type.affects_ready_work() {
                    continue;
                }

                if component_set.contains(&dependency.depends_on_id) {
                    dependency_edges.push((node_id.clone(), dependency.depends_on_id.clone()));
                }
            }
        }
    }

    dependency_edges
}

fn collect_single_graph(
    storage: &SqliteStorage,
    root_id: &str,
    root_issue: &Issue,
) -> Result<SingleGraphTraversal> {
    // For single graph (dependents), we want to show all paths from the root.
    // However, to prevent infinite loops in case of cycles, we track the current path.
    // We also want traversal_order to reflect first-visit DFS order so rendered subtrees stay
    // contiguous in the human-readable graph output.
    let mut traversal_order: Vec<String> = Vec::new();
    let mut issues_by_id: HashMap<String, Issue> = HashMap::new();
    let mut edges: Vec<(String, String)> = Vec::new();
    let mut seen_edges: HashSet<(String, String)> = HashSet::new();
    let mut ordered_nodes: HashSet<String> = HashSet::new();
    let mut expanded_nodes: HashSet<String> = HashSet::new();
    let mut queued_nodes: HashSet<String> = HashSet::new();

    // Optimization: Prefetch active issue metadata to avoid N+1 queries during traversal
    let metadata_cache = storage.get_active_issues_metadata()?;

    // Stack stores (current_id, path_to_this_node)
    let mut stack: Vec<(String, Vec<String>)> = vec![(root_id.to_string(), vec![])];
    queued_nodes.insert(root_id.to_string());

    issues_by_id.insert(root_id.to_string(), root_issue.clone());

    while let Some((current_id, path)) = stack.pop() {
        queued_nodes.remove(&current_id);

        if ordered_nodes.insert(current_id.clone()) {
            traversal_order.push(current_id.clone());
        }

        if !expanded_nodes.insert(current_id.clone()) {
            continue;
        }

        let mut dependents = storage.get_dependents_with_metadata(&current_id)?;
        dependents.retain(|dep| {
            dep.dep_type
                .parse::<DependencyType>()
                .unwrap_or(DependencyType::Blocks)
                .affects_ready_work()
        });
        // Sort for deterministic traversal: priority then ID
        dependents.sort_by(|a, b| a.priority.0.cmp(&b.priority.0).then(a.id.cmp(&b.id)));

        for dep in dependents.into_iter().rev() {
            let edge = (dep.id.clone(), current_id.clone());
            if seen_edges.insert(edge.clone()) {
                edges.push(edge);
            }

            if !issues_by_id.contains_key(&dep.id) {
                // Use cache if available, otherwise preserve the dependency metadata
                // placeholder instead of turning a missing issue back into a hard error.
                let issue = if let Some(meta) = metadata_cache.get(&dep.id) {
                    Issue {
                        id: dep.id.clone(),
                        title: meta.0.clone(),
                        priority: Priority(meta.1),
                        status: Status::from_str(&meta.2).unwrap_or(Status::Open),
                        ..Issue::default()
                    }
                } else {
                    Issue {
                        id: dep.id.clone(),
                        title: dep.title.clone(),
                        priority: dep.priority,
                        status: dep.status.clone(),
                        ..Issue::default()
                    }
                };

                issues_by_id.insert(dep.id.clone(), issue);
            }

            // Cycle prevention: only descend if the child isn't already in the path to here
            if !path.contains(&dep.id)
                && dep.id != current_id
                && !expanded_nodes.contains(&dep.id)
                && queued_nodes.insert(dep.id.clone())
            {
                let mut new_path = path.clone();
                new_path.push(current_id.clone());
                stack.push((dep.id.clone(), new_path));
            }
        }
    }

    Ok(SingleGraphTraversal {
        traversal_order,
        issues_by_id,
        edges,
    })
}

fn build_graph_nodes(
    traversal_order: &[String],
    issues_by_id: &HashMap<String, Issue>,
    depths: &HashMap<String, usize>,
) -> Vec<GraphNode> {
    traversal_order
        .iter()
        .map(|node_id| {
            let issue = issues_by_id
                .get(node_id)
                .expect("reachable graph node should exist");
            GraphNode {
                id: node_id.clone(),
                title: issue.title.clone(),
                status: issue.status.as_str().to_string(),
                priority: issue.priority.0,
                depth: depths.get(node_id).copied().unwrap_or(0),
            }
        })
        .collect()
}

fn sort_single_graph_nodes(nodes: &mut [GraphNode], root_id: &str) {
    if let Some(root_index) = nodes.iter().position(|node| node.id == root_id) {
        nodes[..=root_index].rotate_right(1);
    }
}

fn calculate_depths_from_dependency_edges(
    nodes: &[String],
    dependency_edges: &[(String, String)],
    root_nodes: &[String],
) -> HashMap<String, usize> {
    let dependency_map = build_dependency_map(nodes, dependency_edges);
    let node_to_component = strongly_connected_components(nodes, &dependency_map);
    let component_count = node_to_component
        .values()
        .copied()
        .max()
        .map_or(0, |max_component| max_component + 1);

    if component_count == 0 {
        return HashMap::new();
    }

    let mut component_children: HashMap<usize, HashSet<usize>> = HashMap::new();
    let mut component_indegree = vec![0usize; component_count];

    for (dependent, dependency) in dependency_edges {
        let dependent_component = *node_to_component
            .get(dependent)
            .expect("dependent node should have a component");
        let dependency_component = *node_to_component
            .get(dependency)
            .expect("dependency node should have a component");

        if dependency_component == dependent_component {
            continue;
        }

        let inserted = component_children
            .entry(dependency_component)
            .or_default()
            .insert(dependent_component);
        if inserted {
            component_indegree[dependent_component] += 1;
        }
    }

    let mut component_depths = vec![0usize; component_count];
    let mut reachable_components: HashSet<usize> = root_nodes
        .iter()
        .filter_map(|node_id| node_to_component.get(node_id).copied())
        .collect();

    let mut queue: VecDeque<usize> = component_indegree
        .iter()
        .enumerate()
        .filter_map(|(component_id, indegree)| (*indegree == 0).then_some(component_id))
        .collect();

    while let Some(component_id) = queue.pop_front() {
        if let Some(children) = component_children.get(&component_id) {
            for child_component in children {
                if reachable_components.contains(&component_id) {
                    reachable_components.insert(*child_component);
                    component_depths[*child_component] =
                        component_depths[*child_component].max(component_depths[component_id] + 1);
                }

                component_indegree[*child_component] -= 1;
                if component_indegree[*child_component] == 0 {
                    queue.push_back(*child_component);
                }
            }
        }
    }

    nodes
        .iter()
        .map(|node_id| {
            let component_id = node_to_component
                .get(node_id)
                .expect("graph node should have a component");
            (node_id.clone(), component_depths[*component_id])
        })
        .collect()
}

fn build_dependency_map(
    nodes: &[String],
    dependency_edges: &[(String, String)],
) -> HashMap<String, Vec<String>> {
    let mut dependency_map: HashMap<String, Vec<String>> = nodes
        .iter()
        .cloned()
        .map(|node_id| (node_id, Vec::new()))
        .collect();

    for (dependent, dependency) in dependency_edges {
        dependency_map
            .entry(dependent.clone())
            .or_default()
            .push(dependency.clone());
    }

    for dependencies in dependency_map.values_mut() {
        dependencies.sort();
        dependencies.dedup();
    }

    dependency_map
}

fn strongly_connected_components(
    nodes: &[String],
    dependency_map: &HashMap<String, Vec<String>>,
) -> HashMap<String, usize> {
    let reverse_map = build_reverse_map(nodes, dependency_map);
    let mut visited: HashSet<String> = HashSet::new();
    let mut finish_order = Vec::new();

    for node_id in nodes {
        if visited.contains(node_id) {
            continue;
        }
        dfs_finish_order(node_id, dependency_map, &mut visited, &mut finish_order);
    }

    let mut component_map = HashMap::new();
    let mut next_component = 0usize;

    while let Some(node_id) = finish_order.pop() {
        if component_map.contains_key(&node_id) {
            continue;
        }

        let mut stack = vec![node_id.clone()];
        while let Some(current_id) = stack.pop() {
            if component_map.contains_key(&current_id) {
                continue;
            }

            component_map.insert(current_id.clone(), next_component);
            if let Some(parents) = reverse_map.get(&current_id) {
                for parent_id in parents.iter().rev() {
                    if !component_map.contains_key(parent_id) {
                        stack.push(parent_id.clone());
                    }
                }
            }
        }

        next_component += 1;
    }

    component_map
}

fn build_reverse_map(
    nodes: &[String],
    dependency_map: &HashMap<String, Vec<String>>,
) -> HashMap<String, Vec<String>> {
    let mut reverse_map: HashMap<String, Vec<String>> = nodes
        .iter()
        .cloned()
        .map(|node_id| (node_id, Vec::new()))
        .collect();

    for (node_id, dependencies) in dependency_map {
        for dependency_id in dependencies {
            reverse_map
                .entry(dependency_id.clone())
                .or_default()
                .push(node_id.clone());
        }
    }

    for dependents in reverse_map.values_mut() {
        dependents.sort();
        dependents.dedup();
    }

    reverse_map
}

fn dfs_finish_order(
    start: &str,
    dependency_map: &HashMap<String, Vec<String>>,
    visited: &mut HashSet<String>,
    finish_order: &mut Vec<String>,
) {
    let mut stack = vec![(start.to_string(), false)];

    while let Some((node_id, expanded)) = stack.pop() {
        if expanded {
            finish_order.push(node_id);
            continue;
        }

        if !visited.insert(node_id.clone()) {
            continue;
        }

        stack.push((node_id.clone(), true));
        if let Some(dependencies) = dependency_map.get(&node_id) {
            for dependency_id in dependencies.iter().rev() {
                if !visited.contains(dependency_id) {
                    stack.push((dependency_id.clone(), false));
                }
            }
        }
    }
}

fn build_parent_map(edges: &[(String, String)]) -> HashMap<String, Vec<String>> {
    let mut parent_map: HashMap<String, Vec<String>> = HashMap::new();

    for (dependent, dependency) in edges {
        parent_map
            .entry(dependent.clone())
            .or_default()
            .push(dependency.clone());
    }

    for parents in parent_map.values_mut() {
        parents.sort();
        parents.dedup();
    }

    parent_map
}

fn format_parent_list(parents: Option<&[String]>) -> String {
    match parents {
        Some(parents) if !parents.is_empty() => format!(" depends on: {}", parents.join(", ")),
        _ => String::new(),
    }
}

fn format_compact_dependency_edges(root_id: &str, edges: &[(String, String)]) -> String {
    if edges.is_empty() {
        return root_id.to_string();
    }

    let mut grouped_dependents: HashMap<String, Vec<String>> = HashMap::new();
    for (dependent, dependency) in edges {
        grouped_dependents
            .entry(dependency.clone())
            .or_default()
            .push(dependent.clone());
    }

    let mut dependencies: Vec<String> = grouped_dependents.keys().cloned().collect();
    dependencies.sort_by(|left, right| {
        if left == root_id {
            std::cmp::Ordering::Less
        } else if right == root_id {
            std::cmp::Ordering::Greater
        } else {
            left.cmp(right)
        }
    });
    let includes_root = dependencies
        .iter()
        .any(|dependency_id| dependency_id == root_id);

    let parts: Vec<String> = dependencies
        .iter()
        .map(|dependency_id| {
            let dependents = grouped_dependents
                .get(dependency_id)
                .expect("grouped dependents should exist");
            let mut sorted_dependents = dependents.clone();
            sorted_dependents.sort();
            sorted_dependents.dedup();
            format!("{dependency_id} <- {}", sorted_dependents.join(", "))
        })
        .collect();

    if includes_root {
        parts.join("; ")
    } else {
        format!("{root_id}; {}", parts.join("; "))
    }
}

const fn human_graph_render_mode(mode: OutputMode, compact: bool) -> HumanGraphRenderMode {
    if compact {
        HumanGraphRenderMode::Compact
    } else if matches!(mode, OutputMode::Rich) {
        HumanGraphRenderMode::Rich
    } else {
        HumanGraphRenderMode::Plain
    }
}

fn render_single_graph_plain(nodes: &[GraphNode], edges: &[(String, String)], root_issue: &Issue) {
    let parent_map = build_parent_map(edges);
    println!(
        "Dependents of {} by depth ({} total):",
        root_issue.id,
        nodes.len() - 1
    );
    println!();
    println!(
        "  {}: {} [P{}] [{}] (root)",
        root_issue.id,
        root_issue.title,
        root_issue.priority.0,
        root_issue.status.as_str()
    );

    for node in nodes.iter().skip(1) {
        let indent = "  ".repeat(node.depth + 1);
        let parents = format_parent_list(parent_map.get(&node.id).map(Vec::as_slice));
        println!(
            "{}← {}: {} [P{}] [{}]{}",
            indent, node.id, node.title, node.priority, node.status, parents
        );
    }
}

// ─────────────────────────────────────────────────────────────
// Rich Output Rendering
// ─────────────────────────────────────────────────────────────

/// Render single graph with rich formatting.
fn render_single_graph_rich(
    nodes: &[GraphNode],
    edges: &[(String, String)],
    root_issue: &Issue,
    ctx: &OutputContext,
) {
    let console = Console::default();
    let theme = ctx.theme();
    let width = ctx.width();
    let parent_map = build_parent_map(edges);

    let mut content = Text::new("");

    // Header with root info
    content.append_styled("Root: ", theme.dimmed.clone());
    content.append_styled(&root_issue.id, theme.issue_id.clone());
    content.append(" ");
    content.append_styled(&root_issue.title, theme.emphasis.clone());
    content.append("\n\n");

    // Dependent count
    let dep_count = nodes.len() - 1;
    content.append_styled(
        &format!(
            "{} dependent{}\n\n",
            dep_count,
            if dep_count == 1 { "" } else { "s" }
        ),
        theme.dimmed.clone(),
    );
    content.append_styled(
        "Layered view; shared dependents list all blockers in this graph.\n\n",
        theme.dimmed.clone(),
    );

    // Render tree
    for node in nodes {
        let indent = "  ".repeat(node.depth);

        // Depth indicator
        if node.id == root_issue.id {
            content.append_styled("● ", theme.success.clone());
        } else {
            content.append(&indent);
            content.append_styled("← ", theme.dimmed.clone());
        }

        // ID
        content.append_styled(&node.id, theme.issue_id.clone());
        content.append(" ");

        // Title
        content.append(&node.title);
        content.append(" ");

        // Priority badge
        let priority_style = priority_style(node.priority, theme);
        content.append_styled(&format!("[P{}]", node.priority), priority_style);
        content.append(" ");

        // Status badge
        let status_style = status_style(&node.status, theme);
        content.append_styled(&format!("[{}]", node.status), status_style);

        if node.id == root_issue.id {
            content.append_styled(" (root)", theme.dimmed.clone());
        } else if let Some(parents) = parent_map.get(&node.id) {
            content.append_styled(
                &format!(" depends on: {}", parents.join(", ")),
                theme.dimmed.clone(),
            );
        }
        content.append("\n");
    }

    let panel = Panel::from_rich_text(&content, width)
        .title(Text::styled("Dependency Graph", theme.panel_title.clone()))
        .box_style(theme.box_style);

    console.print_renderable(&panel);
}

/// Render no dependents message with rich formatting.
fn render_no_dependents_rich(root_id: &str, root_issue: &Issue, ctx: &OutputContext) {
    let console = Console::default();
    let theme = ctx.theme();
    let width = ctx.width();

    let mut content = Text::new("");

    content.append_styled("● ", theme.success.clone());
    content.append_styled(root_id, theme.issue_id.clone());
    content.append(" ");
    content.append(&root_issue.title);
    content.append("\n\n");
    content.append_styled("No dependents found", theme.dimmed.clone());
    content.append("\n");

    let panel = Panel::from_rich_text(&content, width)
        .title(Text::styled("Dependency Graph", theme.panel_title.clone()))
        .box_style(theme.box_style);

    console.print_renderable(&panel);
}

/// Render all graph (connected components) with rich formatting.
fn render_all_graph_rich(
    components: &[ConnectedComponent],
    total_nodes: usize,
    ctx: &OutputContext,
) {
    let console = Console::default();
    let theme = ctx.theme();
    let width = ctx.width();

    let mut content = Text::new("");

    // Summary header
    content.append_styled(
        &format!(
            "{} issue{} in {} component{}\n",
            total_nodes,
            if total_nodes == 1 { "" } else { "s" },
            components.len(),
            if components.len() == 1 { "" } else { "s" }
        ),
        theme.section.clone(),
    );
    content.append_styled(
        "Layered view; shared dependents list all blockers within each component.\n",
        theme.dimmed.clone(),
    );

    // Render each component
    for (i, component) in components.iter().enumerate() {
        content.append("\n");
        let parent_map = build_parent_map(&component.edges);

        // Component header
        content.append_styled(&format!("Component {}", i + 1), theme.emphasis.clone());
        let roots = if component.roots.is_empty() {
            "none".to_string()
        } else {
            component.roots.join(", ")
        };
        content.append_styled(
            &format!(
                " ({} issue{}, roots: {})\n",
                component.nodes.len(),
                if component.nodes.len() == 1 { "" } else { "s" },
                roots
            ),
            theme.dimmed.clone(),
        );

        // Render nodes in component
        for node in &component.nodes {
            let indent = "  ".repeat(node.depth + 1);
            content.append(&indent);

            // ID
            content.append_styled(&node.id, theme.issue_id.clone());
            content.append(" ");

            // Title (truncate if too long for all-graph view to avoid messy panels)
            // Use visual width for the check to be consistent with truncate_title
            let title = if UnicodeWidthStr::width(node.title.as_str()) > 40 {
                crate::format::truncate_title(&node.title, 40)
            } else {
                node.title.clone()
            };
            content.append(&title);
            content.append(" ");

            // Priority badge
            let priority_style = priority_style(node.priority, theme);
            content.append_styled(&format!("[P{}]", node.priority), priority_style);
            content.append(" ");

            // Status badge
            let status_style = status_style(&node.status, theme);
            content.append_styled(&format!("[{}]", node.status), status_style);

            if component.roots.contains(&node.id) {
                content.append_styled(" (root)", theme.dimmed.clone());
            } else if let Some(parents) = parent_map.get(&node.id) {
                content.append_styled(
                    &format!(" depends on: {}", parents.join(", ")),
                    theme.dimmed.clone(),
                );
            }
            content.append("\n");
        }
    }

    let panel = Panel::from_rich_text(&content, width)
        .title(Text::styled("Dependency Graph", theme.panel_title.clone()))
        .box_style(theme.box_style);

    console.print_renderable(&panel);
}

/// Render no issues message with rich formatting.
fn render_no_issues_rich(ctx: &OutputContext) {
    let console = Console::default();
    let theme = ctx.theme();
    let width = ctx.width();

    let mut content = Text::new("");
    content.append_styled(
        "No open/in_progress/blocked issues found",
        theme.dimmed.clone(),
    );
    content.append("\n");

    let panel = Panel::from_rich_text(&content, width)
        .title(Text::styled("Dependency Graph", theme.panel_title.clone()))
        .box_style(theme.box_style);

    console.print_renderable(&panel);
}

/// Get style for priority level.
fn priority_style(priority: i32, theme: &crate::output::Theme) -> Style {
    match priority {
        0 => theme.priority_critical.clone(),
        1 => theme.priority_high.clone(),
        2 => theme.priority_medium.clone(),
        3 => theme.priority_low.clone(),
        _ => theme.priority_backlog.clone(),
    }
}

/// Get style for status.
fn status_style(status: &str, theme: &crate::output::Theme) -> Style {
    match status {
        "open" => theme.status_open.clone(),
        "in_progress" => theme.status_in_progress.clone(),
        "blocked" => theme.status_blocked.clone(),
        "closed" => theme.status_closed.clone(),
        "deferred" => theme.status_deferred.clone(),
        _ => theme.dimmed.clone(),
    }
}

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

    #[test]
    fn test_graph_node_serialization() {
        let node = GraphNode {
            id: "bd-001".to_string(),
            title: "Test Issue".to_string(),
            status: "open".to_string(),
            priority: 2,
            depth: 0,
        };

        let json = serde_json::to_string(&node).unwrap();
        assert!(json.contains("\"id\":\"bd-001\""));
        assert!(json.contains("\"depth\":0"));
    }

    #[test]
    fn test_single_graph_output_serialization() {
        let output = SingleGraphOutput {
            root: "bd-001".to_string(),
            count: 3,
            nodes: vec![
                GraphNode {
                    id: "bd-001".to_string(),
                    title: "Root".to_string(),
                    status: "open".to_string(),
                    priority: 2,
                    depth: 0,
                },
                GraphNode {
                    id: "bd-002".to_string(),
                    title: "Child 1".to_string(),
                    status: "blocked".to_string(),
                    priority: 1,
                    depth: 1,
                },
            ],
            edges: vec![("bd-002".to_string(), "bd-001".to_string())],
        };

        let json = serde_json::to_string(&output).unwrap();
        assert!(json.contains("\"root\":\"bd-001\""));
        assert!(json.contains("\"count\":3"));
    }

    #[test]
    fn test_connected_component_serialization() {
        let component = ConnectedComponent {
            nodes: vec![GraphNode {
                id: "bd-001".to_string(),
                title: "Test".to_string(),
                status: "open".to_string(),
                priority: 2,
                depth: 0,
            }],
            edges: vec![],
            roots: vec!["bd-001".to_string()],
        };

        let json = serde_json::to_string(&component).unwrap();
        assert!(json.contains("\"roots\":[\"bd-001\"]"));
    }

    // ============================================================
    // Additional tests for comprehensive graph module coverage
    // ============================================================

    #[test]
    fn test_all_graph_output_serialization() {
        let output = AllGraphOutput {
            components: vec![ConnectedComponent {
                nodes: vec![
                    GraphNode {
                        id: "bd-001".to_string(),
                        title: "Root Issue".to_string(),
                        status: "open".to_string(),
                        priority: 1,
                        depth: 0,
                    },
                    GraphNode {
                        id: "bd-002".to_string(),
                        title: "Child Issue".to_string(),
                        status: "blocked".to_string(),
                        priority: 2,
                        depth: 1,
                    },
                ],
                edges: vec![("bd-002".to_string(), "bd-001".to_string())],
                roots: vec!["bd-001".to_string()],
            }],
            total_nodes: 2,
            total_components: 1,
        };

        let json = serde_json::to_string(&output).unwrap();
        assert!(json.contains("\"total_nodes\":2"));
        assert!(json.contains("\"total_components\":1"));
        assert!(json.contains("\"components\""));
    }

    #[test]
    fn test_all_graph_output_empty() {
        let output = AllGraphOutput {
            components: vec![],
            total_nodes: 0,
            total_components: 0,
        };

        let json = serde_json::to_string(&output).unwrap();
        assert!(json.contains("\"total_nodes\":0"));
        assert!(json.contains("\"total_components\":0"));
        assert!(json.contains("\"components\":[]"));
    }

    #[test]
    fn test_graph_node_all_fields_present() {
        let node = GraphNode {
            id: "beads_rust-abc123".to_string(),
            title: "Complex title with special chars: <>&".to_string(),
            status: "in_progress".to_string(),
            priority: 0,
            depth: 5,
        };

        let json = serde_json::to_string(&node).unwrap();

        // Parse back to verify all fields
        let parsed: serde_json::Value = serde_json::from_str(&json).unwrap();
        assert_eq!(parsed["id"], "beads_rust-abc123");
        assert_eq!(parsed["title"], "Complex title with special chars: <>&");
        assert_eq!(parsed["status"], "in_progress");
        assert_eq!(parsed["priority"], 0);
        assert_eq!(parsed["depth"], 5);
    }

    #[test]
    fn test_graph_node_deserialize() {
        let json = r#"{
            "id": "bd-test",
            "title": "Test Issue",
            "status": "open",
            "priority": 2,
            "depth": 0
        }"#;

        // GraphNode doesn't derive Deserialize, but we can verify the JSON is valid
        let parsed: serde_json::Value = serde_json::from_str(json).unwrap();
        assert_eq!(parsed["id"], "bd-test");
        assert_eq!(parsed["priority"], 2);
    }

    #[test]
    fn test_connected_component_with_multiple_roots() {
        let component = ConnectedComponent {
            nodes: vec![
                GraphNode {
                    id: "bd-001".to_string(),
                    title: "Root 1".to_string(),
                    status: "open".to_string(),
                    priority: 1,
                    depth: 0,
                },
                GraphNode {
                    id: "bd-002".to_string(),
                    title: "Root 2".to_string(),
                    status: "open".to_string(),
                    priority: 2,
                    depth: 0,
                },
                GraphNode {
                    id: "bd-003".to_string(),
                    title: "Shared Child".to_string(),
                    status: "blocked".to_string(),
                    priority: 3,
                    depth: 1,
                },
            ],
            edges: vec![
                ("bd-003".to_string(), "bd-001".to_string()),
                ("bd-003".to_string(), "bd-002".to_string()),
            ],
            roots: vec!["bd-001".to_string(), "bd-002".to_string()],
        };

        let json = serde_json::to_string(&component).unwrap();
        let parsed: serde_json::Value = serde_json::from_str(&json).unwrap();

        // Check roots array has both
        let roots = parsed["roots"].as_array().unwrap();
        assert_eq!(roots.len(), 2);

        // Check edges array has both edges
        let edges = parsed["edges"].as_array().unwrap();
        assert_eq!(edges.len(), 2);
    }

    #[test]
    fn test_connected_component_empty() {
        let component = ConnectedComponent {
            nodes: vec![],
            edges: vec![],
            roots: vec![],
        };

        let json = serde_json::to_string(&component).unwrap();
        assert!(json.contains("\"nodes\":[]"));
        assert!(json.contains("\"edges\":[]"));
        assert!(json.contains("\"roots\":[]"));
    }

    #[test]
    fn test_single_graph_output_with_complex_edges() {
        let output = SingleGraphOutput {
            root: "bd-root".to_string(),
            count: 4,
            nodes: vec![
                GraphNode {
                    id: "bd-root".to_string(),
                    title: "Root".to_string(),
                    status: "open".to_string(),
                    priority: 0,
                    depth: 0,
                },
                GraphNode {
                    id: "bd-a".to_string(),
                    title: "A".to_string(),
                    status: "blocked".to_string(),
                    priority: 1,
                    depth: 1,
                },
                GraphNode {
                    id: "bd-b".to_string(),
                    title: "B".to_string(),
                    status: "blocked".to_string(),
                    priority: 1,
                    depth: 1,
                },
                GraphNode {
                    id: "bd-c".to_string(),
                    title: "C".to_string(),
                    status: "blocked".to_string(),
                    priority: 2,
                    depth: 2,
                },
            ],
            edges: vec![
                ("bd-a".to_string(), "bd-root".to_string()),
                ("bd-b".to_string(), "bd-root".to_string()),
                ("bd-c".to_string(), "bd-a".to_string()),
                ("bd-c".to_string(), "bd-b".to_string()),
            ],
        };

        let json = serde_json::to_string(&output).unwrap();
        let parsed: serde_json::Value = serde_json::from_str(&json).unwrap();

        assert_eq!(parsed["count"], 4);
        assert_eq!(parsed["nodes"].as_array().unwrap().len(), 4);
        assert_eq!(parsed["edges"].as_array().unwrap().len(), 4);
    }

    #[test]
    fn test_graph_node_priority_boundaries() {
        // Test P0 (critical)
        let p0_node = GraphNode {
            id: "bd-p0".to_string(),
            title: "Critical".to_string(),
            status: "open".to_string(),
            priority: 0,
            depth: 0,
        };
        let json = serde_json::to_string(&p0_node).unwrap();
        assert!(json.contains("\"priority\":0"));

        // Test P4 (backlog)
        let p4_node = GraphNode {
            id: "bd-p4".to_string(),
            title: "Backlog".to_string(),
            status: "open".to_string(),
            priority: 4,
            depth: 0,
        };
        let json = serde_json::to_string(&p4_node).unwrap();
        assert!(json.contains("\"priority\":4"));
    }

    #[test]
    fn test_all_graph_output_multiple_components() {
        let output = AllGraphOutput {
            components: vec![
                ConnectedComponent {
                    nodes: vec![GraphNode {
                        id: "comp1-a".to_string(),
                        title: "Comp1 Issue".to_string(),
                        status: "open".to_string(),
                        priority: 1,
                        depth: 0,
                    }],
                    edges: vec![],
                    roots: vec!["comp1-a".to_string()],
                },
                ConnectedComponent {
                    nodes: vec![
                        GraphNode {
                            id: "comp2-a".to_string(),
                            title: "Comp2 Root".to_string(),
                            status: "open".to_string(),
                            priority: 2,
                            depth: 0,
                        },
                        GraphNode {
                            id: "comp2-b".to_string(),
                            title: "Comp2 Child".to_string(),
                            status: "blocked".to_string(),
                            priority: 2,
                            depth: 1,
                        },
                    ],
                    edges: vec![("comp2-b".to_string(), "comp2-a".to_string())],
                    roots: vec!["comp2-a".to_string()],
                },
            ],
            total_nodes: 3,
            total_components: 2,
        };

        let json = serde_json::to_string_pretty(&output).unwrap();
        let parsed: serde_json::Value = serde_json::from_str(&json).unwrap();

        assert_eq!(parsed["total_components"], 2);
        assert_eq!(parsed["total_nodes"], 3);
        assert_eq!(parsed["components"].as_array().unwrap().len(), 2);
    }

    #[test]
    fn test_graph_node_all_status_values() {
        let statuses = [
            "open",
            "in_progress",
            "blocked",
            "closed",
            "deferred",
            "tombstone",
        ];

        for status in statuses {
            let node = GraphNode {
                id: format!("bd-{status}"),
                title: format!("Issue with {status} status"),
                status: status.to_string(),
                priority: 2,
                depth: 0,
            };

            let json = serde_json::to_string(&node).unwrap();
            assert!(json.contains(&format!("\"status\":\"{status}\"")));
        }
    }

    #[test]
    fn test_calculate_depths_cycle_has_no_roots() {
        let mut storage = SqliteStorage::open_memory().unwrap();
        let t1 = chrono::Utc::now();

        let a = Issue {
            id: "bd-a".to_string(),
            title: "A".to_string(),
            status: Status::Open,
            priority: crate::model::Priority::MEDIUM,
            issue_type: crate::model::IssueType::Task,
            created_at: t1,
            updated_at: t1,
            ..Default::default()
        };
        let b = Issue {
            id: "bd-b".to_string(),
            title: "B".to_string(),
            status: Status::Open,
            priority: crate::model::Priority::MEDIUM,
            issue_type: crate::model::IssueType::Task,
            created_at: t1,
            updated_at: t1,
            ..Default::default()
        };

        storage.create_issue(&a, "test").unwrap();
        storage.create_issue(&b, "test").unwrap();
        let created_at = t1.to_rfc3339();
        storage
            .execute_test_sql(&format!(
                "INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-a', 'bd-b', 'waits-for', '{created_at}', 'test');
                 INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-b', 'bd-a', 'waits-for', '{created_at}', 'test');"
            ))
            .unwrap();

        let all_dependencies = storage.get_all_dependency_records().unwrap();
        let nodes = vec!["bd-a".to_string(), "bd-b".to_string()];
        let component_set: HashSet<&String> = nodes.iter().collect();

        let (depths, roots) = calculate_depths(&all_dependencies, &nodes, &component_set);
        assert!(roots.is_empty());
        assert_eq!(depths.get("bd-a"), Some(&0));
        assert_eq!(depths.get("bd-b"), Some(&0));
    }

    #[test]
    fn test_graph_all_cycle_robustness() {
        let mut storage = SqliteStorage::open_memory().unwrap();
        let t1 = chrono::Utc::now();

        let root = Issue {
            id: "root".to_string(),
            title: "Root".to_string(),
            status: Status::Open,
            priority: crate::model::Priority::MEDIUM,
            issue_type: crate::model::IssueType::Task,
            created_at: t1,
            updated_at: t1,
            ..Default::default()
        };
        let i1 = Issue {
            id: "bd-1".to_string(),
            title: "A".to_string(),
            status: Status::Open,
            priority: crate::model::Priority::MEDIUM,
            issue_type: crate::model::IssueType::Task,
            created_at: t1,
            updated_at: t1,
            ..Default::default()
        };
        let i2 = Issue {
            id: "bd-2".to_string(),
            title: "B".to_string(),
            status: Status::Open,
            priority: crate::model::Priority::MEDIUM,
            issue_type: crate::model::IssueType::Task,
            created_at: t1,
            updated_at: t1,
            ..Default::default()
        };

        storage.create_issue(&root, "test").unwrap();
        storage.create_issue(&i1, "test").unwrap();
        storage.create_issue(&i2, "test").unwrap();

        let created_at = t1.to_rfc3339();
        storage
            .execute_test_sql(&format!(
                "INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-1', 'root', 'waits-for', '{created_at}', 'test');
                 INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-2', 'bd-1', 'waits-for', '{created_at}', 'test');
                 INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-1', 'bd-2', 'waits-for', '{created_at}', 'test');"
            ))
            .unwrap();

        let ctx = OutputContext::from_flags(true, false, true); // JSON mode

        // This should not hang even with root feeding into cycle
        // If it hangs, the test runner will timeout
        let result = graph_all(&storage, false, &ctx);
        assert!(result.is_ok());
    }

    #[test]
    fn test_collect_single_graph_preserves_missing_dependent_placeholder() {
        let mut storage = SqliteStorage::open_memory().unwrap();
        let t1 = chrono::Utc::now();

        let root = Issue {
            id: "bd-root".to_string(),
            title: "Root".to_string(),
            status: Status::Open,
            priority: crate::model::Priority::MEDIUM,
            issue_type: crate::model::IssueType::Task,
            created_at: t1,
            updated_at: t1,
            ..Default::default()
        };

        storage.create_issue(&root, "test").unwrap();

        let created_at = t1.to_rfc3339();
        storage
            .execute_test_sql(&format!(
                "PRAGMA foreign_keys = OFF;
                 INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-missing', 'bd-root', 'blocks', '{created_at}', 'test');
                 PRAGMA foreign_keys = ON;"
            ))
            .unwrap();

        let traversal = collect_single_graph(&storage, "bd-root", &root)
            .expect("graph traversal should preserve missing dependent placeholders");

        let missing = traversal
            .issues_by_id
            .get("bd-missing")
            .expect("missing dependent should be represented in graph output");
        assert_eq!(missing.title, "[missing issue: bd-missing]");
        assert_eq!(missing.status, Status::Tombstone);
        assert!(
            traversal
                .edges
                .contains(&(String::from("bd-missing"), String::from("bd-root"))),
            "graph should retain the dangling edge"
        );
    }

    #[test]
    fn test_collect_single_graph_uses_first_visit_dfs_order() {
        let mut storage = SqliteStorage::open_memory().unwrap();
        let t1 = chrono::Utc::now();

        for (id, title) in [
            ("bd-root", "Root"),
            ("bd-a", "A"),
            ("bd-b", "B"),
            ("bd-c", "C"),
        ] {
            let issue = Issue {
                id: id.to_string(),
                title: title.to_string(),
                status: Status::Open,
                priority: crate::model::Priority::MEDIUM,
                issue_type: crate::model::IssueType::Task,
                created_at: t1,
                updated_at: t1,
                ..Default::default()
            };
            storage.create_issue(&issue, "test").unwrap();
        }

        let created_at = t1.to_rfc3339();
        storage
            .execute_test_sql(&format!(
                "INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-a', 'bd-root', 'blocks', '{created_at}', 'test');
                 INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-b', 'bd-root', 'blocks', '{created_at}', 'test');
                 INSERT INTO dependencies (issue_id, depends_on_id, type, created_at, created_by)
                 VALUES ('bd-c', 'bd-a', 'blocks', '{created_at}', 'test');"
            ))
            .unwrap();

        let root = storage
            .get_issue("bd-root")
            .unwrap()
            .expect("root issue should exist");
        let traversal =
            collect_single_graph(&storage, "bd-root", &root).expect("graph traversal should work");

        assert_eq!(
            traversal.traversal_order,
            vec![
                "bd-root".to_string(),
                "bd-a".to_string(),
                "bd-c".to_string(),
                "bd-b".to_string()
            ]
        );
    }

    #[test]
    fn test_calculate_depths_from_dependency_edges_uses_longest_path() {
        let nodes = vec![
            "root".to_string(),
            "bd-a".to_string(),
            "bd-b".to_string(),
            "bd-c".to_string(),
            "bd-d".to_string(),
        ];
        let dependency_edges = vec![
            ("bd-a".to_string(), "root".to_string()),
            ("bd-b".to_string(), "root".to_string()),
            ("bd-c".to_string(), "bd-b".to_string()),
            ("bd-d".to_string(), "bd-a".to_string()),
            ("bd-d".to_string(), "bd-c".to_string()),
        ];
        let root_nodes = ["root".to_string()];

        let depths = calculate_depths_from_dependency_edges(&nodes, &dependency_edges, &root_nodes);

        assert_eq!(depths.get("root"), Some(&0));
        assert_eq!(depths.get("bd-a"), Some(&1));
        assert_eq!(depths.get("bd-b"), Some(&1));
        assert_eq!(depths.get("bd-c"), Some(&2));
        assert_eq!(depths.get("bd-d"), Some(&3));
    }

    #[test]
    fn test_calculate_depths_from_dependency_edges_collapses_reachable_cycle() {
        let nodes = vec!["root".to_string(), "bd-a".to_string(), "bd-b".to_string()];
        let dependency_edges = vec![
            ("bd-a".to_string(), "root".to_string()),
            ("bd-b".to_string(), "bd-a".to_string()),
            ("bd-a".to_string(), "bd-b".to_string()),
        ];
        let root_nodes = ["root".to_string()];

        let depths = calculate_depths_from_dependency_edges(&nodes, &dependency_edges, &root_nodes);

        assert_eq!(depths.get("root"), Some(&0));
        assert_eq!(depths.get("bd-a"), Some(&1));
        assert_eq!(depths.get("bd-b"), Some(&1));
    }

    #[test]
    fn test_format_compact_dependency_edges_preserves_branching() {
        let edges = vec![
            ("bd-a".to_string(), "root".to_string()),
            ("bd-b".to_string(), "root".to_string()),
            ("bd-c".to_string(), "bd-a".to_string()),
            ("bd-c".to_string(), "bd-b".to_string()),
        ];

        let compact = format_compact_dependency_edges("root", &edges);
        assert_eq!(compact, "root <- bd-a, bd-b; bd-a <- bd-c; bd-b <- bd-c");
    }

    #[test]
    fn test_human_graph_render_mode_prefers_compact_over_rich() {
        assert_eq!(
            human_graph_render_mode(OutputMode::Rich, true),
            HumanGraphRenderMode::Compact
        );
        assert_eq!(
            human_graph_render_mode(OutputMode::Rich, false),
            HumanGraphRenderMode::Rich
        );
        assert_eq!(
            human_graph_render_mode(OutputMode::Plain, true),
            HumanGraphRenderMode::Compact
        );
        assert_eq!(
            human_graph_render_mode(OutputMode::Plain, false),
            HumanGraphRenderMode::Plain
        );
    }

    #[test]
    fn test_sort_single_graph_nodes_keeps_root_first_without_reordering_subtrees() {
        let mut nodes = vec![
            GraphNode {
                id: "branch-a".to_string(),
                title: "branch-a".to_string(),
                status: "open".to_string(),
                priority: 1,
                depth: 1,
            },
            GraphNode {
                id: "middle".to_string(),
                title: "middle".to_string(),
                status: "open".to_string(),
                priority: 0,
                depth: 2,
            },
            GraphNode {
                id: "leaf".to_string(),
                title: "leaf".to_string(),
                status: "open".to_string(),
                priority: 3,
                depth: 3,
            },
            GraphNode {
                id: "branch-b".to_string(),
                title: "branch-b".to_string(),
                status: "open".to_string(),
                priority: 2,
                depth: 1,
            },
            GraphNode {
                id: "root".to_string(),
                title: "root".to_string(),
                status: "open".to_string(),
                priority: 4,
                depth: 0,
            },
        ];

        sort_single_graph_nodes(&mut nodes, "root");

        let ordered_ids: Vec<&str> = nodes.iter().map(|node| node.id.as_str()).collect();
        assert_eq!(
            ordered_ids,
            vec!["root", "branch-a", "middle", "leaf", "branch-b"]
        );
    }
}