konoma 0.28.2

// Vendored from the `dagre` crate v0.1.1 (https://github.com/kookyleo/dagre-rs).
// Copyright (c) kookyleo <kookyleo@gmail.com>. Licensed under the Apache License,
// Version 2.0 -- full text in `src/preview/mermaid/layout/LICENSE-APACHE`.
// Modified by the konoma authors; every change is listed in
// `src/preview/mermaid/layout/PROVENANCE.md`.

//! Tests ported from graphlib.js graph-test.ts (170+ tests) and alg/ tests (57+ tests)

use super::alg;
use super::*;

// ============================================================
// Graph - Initial State
// ============================================================

#[test]
fn has_no_nodes_by_default() {
    let g: Graph<i32, i32> = Graph::new();
    assert_eq!(g.node_count(), 0);
}

#[test]
fn has_no_edges_by_default() {
    let g: Graph<i32, i32> = Graph::new();
    assert_eq!(g.edge_count(), 0);
}

#[test]
fn defaults_to_directed() {
    let g: Graph<i32, i32> = Graph::new();
    assert!(g.is_directed());
}

#[test]
fn defaults_to_non_multigraph() {
    let g: Graph<i32, i32> = Graph::new();
    assert!(!g.is_multigraph());
}

#[test]
fn defaults_to_non_compound() {
    let g: Graph<i32, i32> = Graph::new();
    assert!(!g.is_compound());
}

#[test]
fn can_create_undirected_graph() {
    let g: Graph<i32, i32> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    assert!(!g.is_directed());
}

#[test]
fn can_create_multigraph() {
    let g: Graph<i32, i32> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    assert!(g.is_multigraph());
}

#[test]
fn can_create_compound_graph() {
    let g: Graph<i32, i32> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    assert!(g.is_compound());
}

// ============================================================
// Graph - Nodes
// ============================================================

#[test]
fn set_node_creates_node() {
    let mut g: Graph<&str, ()> = Graph::new();
    g.set_node("a", None);
    assert!(g.has_node("a"));
    assert_eq!(g.node_count(), 1);
}

#[test]
fn set_node_with_label() {
    let mut g: Graph<i32, ()> = Graph::new();
    g.set_node("a", Some(42));
    assert_eq!(g.node("a"), Some(&42));
}

#[test]
fn set_node_overwrites_label() {
    let mut g: Graph<i32, ()> = Graph::new();
    g.set_node("a", Some(1));
    g.set_node("a", Some(2));
    assert_eq!(g.node("a"), Some(&2));
    assert_eq!(g.node_count(), 1);
}

#[test]
fn set_node_does_not_overwrite_with_none() {
    let mut g: Graph<i32, ()> = Graph::new();
    g.set_node("a", Some(42));
    g.set_node("a", None);
    assert_eq!(g.node("a"), Some(&42));
}

#[test]
fn set_node_with_default_label() {
    let mut g: Graph<String, ()> = Graph::new();
    g.set_default_node_label(|v| format!("label-{}", v));
    g.set_node("a", None);
    assert_eq!(g.node("a"), Some(&"label-a".to_string()));
}

#[test]
fn node_returns_none_for_nonexistent() {
    let g: Graph<i32, ()> = Graph::new();
    assert_eq!(g.node("a"), None);
}

#[test]
fn remove_node_removes_node() {
    let mut g: Graph<i32, ()> = Graph::new();
    g.set_node("a", Some(1));
    g.remove_node("a");
    assert!(!g.has_node("a"));
    assert_eq!(g.node_count(), 0);
}

#[test]
fn remove_node_returns_label() {
    let mut g: Graph<i32, ()> = Graph::new();
    g.set_node("a", Some(42));
    assert_eq!(g.remove_node("a"), Some(42));
}

#[test]
fn remove_node_removes_incident_edges() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    g.remove_node("b");
    assert_eq!(g.edge_count(), 0);
}

#[test]
fn remove_nonexistent_node_returns_none() {
    let mut g: Graph<i32, ()> = Graph::new();
    assert_eq!(g.remove_node("a"), None);
}

#[test]
fn nodes_returns_all_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    g.set_node("b", None);
    let mut nodes = g.nodes();
    nodes.sort();
    assert_eq!(nodes, vec!["a", "b"]);
}

// ============================================================
// Graph - Sources and Sinks
// ============================================================

#[test]
fn sources_returns_nodes_with_no_in_edges() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let mut sources = g.sources();
    sources.sort();
    assert_eq!(sources, vec!["a"]);
}

#[test]
fn sinks_returns_nodes_with_no_out_edges() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let mut sinks = g.sinks();
    sinks.sort();
    assert_eq!(sinks, vec!["c"]);
}

// ============================================================
// Graph - Edges
// ============================================================

#[test]
fn set_edge_creates_edge() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    assert!(g.has_edge("a", "b", None));
    assert_eq!(g.edge_count(), 1);
}

#[test]
fn set_edge_creates_nodes_if_needed() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    assert!(g.has_node("a"));
    assert!(g.has_node("b"));
}

#[test]
fn set_edge_with_label() {
    let mut g: Graph<(), i32> = Graph::new();
    g.set_edge("a", "b", Some(42), None);
    assert_eq!(g.edge("a", "b", None), Some(&42));
}

#[test]
fn set_edge_overwrites_label() {
    let mut g: Graph<(), i32> = Graph::new();
    g.set_edge("a", "b", Some(1), None);
    g.set_edge("a", "b", Some(2), None);
    assert_eq!(g.edge("a", "b", None), Some(&2));
    assert_eq!(g.edge_count(), 1);
}

#[test]
fn set_edge_does_not_overwrite_with_none() {
    let mut g: Graph<(), i32> = Graph::new();
    g.set_edge("a", "b", Some(42), None);
    g.set_edge("a", "b", None, None);
    assert_eq!(g.edge("a", "b", None), Some(&42));
}

#[test]
fn set_edge_with_default_label() {
    let mut g: Graph<(), String> = Graph::new();
    g.set_default_edge_label(|_| "default".to_string());
    g.set_edge("a", "b", None, None);
    assert_eq!(g.edge("a", "b", None), Some(&"default".to_string()));
}

#[test]
fn edge_returns_none_for_nonexistent() {
    let g: Graph<(), i32> = Graph::new();
    assert_eq!(g.edge("a", "b", None), None);
}

#[test]
fn remove_edge_removes_edge() {
    let mut g: Graph<(), i32> = Graph::new();
    g.set_edge("a", "b", Some(42), None);
    g.remove_edge("a", "b", None);
    assert!(!g.has_edge("a", "b", None));
    assert_eq!(g.edge_count(), 0);
}

#[test]
fn remove_edge_returns_label() {
    let mut g: Graph<(), i32> = Graph::new();
    g.set_edge("a", "b", Some(42), None);
    assert_eq!(g.remove_edge("a", "b", None), Some(42));
}

#[test]
fn remove_edge_keeps_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.remove_edge("a", "b", None);
    assert!(g.has_node("a"));
    assert!(g.has_node("b"));
}

#[test]
fn edges_returns_all_edges() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    assert_eq!(g.edge_count(), 2);
    assert_eq!(g.edges().len(), 2);
}

// ============================================================
// Graph - Directed edges
// ============================================================

#[test]
fn directed_edge_has_direction() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    assert!(g.has_edge("a", "b", None));
    assert!(!g.has_edge("b", "a", None));
}

#[test]
fn in_edges_returns_incoming() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "b", None, None);
    let in_e = g.in_edges("b", None).unwrap();
    assert_eq!(in_e.len(), 2);
}

#[test]
fn in_edges_filtered_by_source() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "b", None, None);
    let in_e = g.in_edges("b", Some("a")).unwrap();
    assert_eq!(in_e.len(), 1);
    assert_eq!(in_e[0].v, "a");
}

#[test]
fn out_edges_returns_outgoing() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "c", None, None);
    let out_e = g.out_edges("a", None).unwrap();
    assert_eq!(out_e.len(), 2);
}

#[test]
fn out_edges_filtered_by_target() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "c", None, None);
    let out_e = g.out_edges("a", Some("b")).unwrap();
    assert_eq!(out_e.len(), 1);
    assert_eq!(out_e[0].w, "b");
}

#[test]
fn node_edges_returns_all_incident() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "b", None, None);
    let edges = g.node_edges("b", None).unwrap();
    assert_eq!(edges.len(), 2);
}

#[test]
fn predecessors_returns_incoming_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "b", None, None);
    let mut preds = g.predecessors("b").unwrap();
    preds.sort();
    assert_eq!(preds, vec!["a", "c"]);
}

#[test]
fn successors_returns_outgoing_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "c", None, None);
    let mut succs = g.successors("a").unwrap();
    succs.sort();
    assert_eq!(succs, vec!["b", "c"]);
}

#[test]
fn neighbors_returns_all_adjacent() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "a", None, None);
    let mut neighbors = g.neighbors("a").unwrap();
    neighbors.sort();
    assert_eq!(neighbors, vec!["b", "c"]);
}

// ============================================================
// Graph - Undirected
// ============================================================

#[test]
fn undirected_edge_both_directions() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    assert!(g.has_edge("a", "b", None));
    assert!(g.has_edge("b", "a", None));
}

#[test]
fn undirected_predecessors_and_successors_are_same() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    let preds = g.predecessors("b").unwrap();
    let succs = g.successors("b").unwrap();
    assert_eq!(preds, succs);
}

// ============================================================
// Graph - Multigraph
// ============================================================

#[test]
fn multigraph_allows_named_edges() {
    let mut g: Graph<(), i32> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", Some(1), Some("x"));
    g.set_edge("a", "b", Some(2), Some("y"));
    assert_eq!(g.edge("a", "b", Some("x")), Some(&1));
    assert_eq!(g.edge("a", "b", Some("y")), Some(&2));
    assert_eq!(g.edge_count(), 2);
}

#[test]
fn multigraph_remove_named_edge() {
    let mut g: Graph<(), i32> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", Some(1), Some("x"));
    g.set_edge("a", "b", Some(2), Some("y"));
    g.remove_edge("a", "b", Some("x"));
    assert!(!g.has_edge("a", "b", Some("x")));
    assert!(g.has_edge("a", "b", Some("y")));
    assert_eq!(g.edge_count(), 1);
}

// ============================================================
// Graph - Compound
// ============================================================

#[test]
fn compound_set_parent() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_parent("b", Some("a"));
    assert_eq!(g.parent("b"), Some("a"));
}

#[test]
fn compound_children_of_parent() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_node("c", None);
    g.set_parent("b", Some("a"));
    g.set_parent("c", Some("a"));
    let mut children = g.children(Some("a"));
    children.sort();
    assert_eq!(children, vec!["b", "c"]);
}

#[test]
fn compound_top_level_nodes() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_parent("b", Some("a"));
    let mut top = g.children(None);
    top.sort();
    assert_eq!(top, vec!["a"]);
}

#[test]
fn compound_parent_defaults_to_none() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    assert_eq!(g.parent("a"), None);
}

#[test]
fn compound_reset_parent_to_root() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_parent("b", Some("a"));
    g.set_parent("b", None);
    assert_eq!(g.parent("b"), None);
    assert!(g.children(Some("a")).is_empty());
}

#[test]
fn compound_remove_node_reparents_children() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_node("c", None);
    g.set_parent("b", Some("a"));
    g.set_parent("c", Some("b"));
    g.remove_node("b");
    // c should be reparented to a
    assert_eq!(g.parent("c"), Some("a"));
}

#[test]
fn compound_set_parent_creates_nodes() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("b", Some("a"));
    assert!(g.has_node("a"));
    assert!(g.has_node("b"));
    assert_eq!(g.parent("b"), Some("a"));
}

// ============================================================
// Graph - set_path
// ============================================================

#[test]
fn set_path_creates_chain() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    assert!(g.has_edge("a", "b", None));
    assert!(g.has_edge("b", "c", None));
    assert!(!g.has_edge("a", "c", None));
}

// ============================================================
// Graph - is_leaf
// ============================================================

#[test]
fn is_leaf_for_sink_node() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    assert!(g.is_leaf("b"));
    assert!(!g.is_leaf("a"));
}

#[test]
fn is_leaf_for_isolated_node() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    assert!(g.is_leaf("a"));
}

// ============================================================
// Graph - filter_nodes
// ============================================================

#[test]
fn filter_nodes_copies_matching_nodes() {
    let mut g: Graph<i32, ()> = Graph::new();
    g.set_node("a", Some(1));
    g.set_node("b", Some(2));
    let g2 = g.filter_nodes(|v| v == "a");
    assert!(g2.has_node("a"));
    assert!(!g2.has_node("b"));
    assert_eq!(g2.node("a"), Some(&1));
}

#[test]
fn filter_nodes_copies_edges_for_matching_nodes() {
    let mut g: Graph<(), i32> = Graph::new();
    g.set_edge("a", "b", Some(1), None);
    g.set_edge("b", "c", Some(2), None);
    let g2 = g.filter_nodes(|v| v != "c");
    assert!(g2.has_edge("a", "b", None));
    assert!(!g2.has_edge("b", "c", None));
}

#[test]
fn filter_nodes_preserves_compound_parents() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_node("c", None);
    g.set_parent("b", Some("a"));
    g.set_parent("c", Some("b"));
    // Filter out "b", "c" should reparent to "a"
    let g2 = g.filter_nodes(|v| v != "b");
    assert_eq!(g2.parent("c"), Some("a"));
}

// ============================================================
// Graph - node_mut
// ============================================================

#[test]
fn node_mut_allows_modification() {
    let mut g: Graph<i32, ()> = Graph::new();
    g.set_node("a", Some(1));
    *g.node_mut("a").unwrap() = 42;
    assert_eq!(g.node("a"), Some(&42));
}

// ============================================================
// Algorithm - Topological Sort
// ============================================================

#[test]
fn topsort_empty_graph() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(alg::topsort(&g).unwrap(), Vec::<String>::new());
}

#[test]
fn topsort_simple_chain() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    assert_eq!(alg::topsort(&g).unwrap(), vec!["a", "b", "c"]);
}

#[test]
fn topsort_diamond() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "d"], None);
    g.set_path(&["a", "c", "d"], None);
    let result = alg::topsort(&g).unwrap();
    // a must come before b, c; d must come last
    let pos = |v: &str| result.iter().position(|x| x == v).unwrap();
    assert!(pos("a") < pos("b"));
    assert!(pos("a") < pos("c"));
    assert!(pos("b") < pos("d"));
    assert!(pos("c") < pos("d"));
}

#[test]
fn topsort_detects_cycle() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c", "a"], None);
    assert!(alg::topsort(&g).is_err());
}

#[test]
fn topsort_detects_self_loop() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "a", None, None);
    assert!(alg::topsort(&g).is_err());
}

// ============================================================
// Algorithm - is_acyclic
// ============================================================

#[test]
fn is_acyclic_true_for_dag() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    assert!(alg::is_acyclic(&g));
}

#[test]
fn is_acyclic_false_for_cyclic() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c", "a"], None);
    assert!(!alg::is_acyclic(&g));
}

#[test]
fn is_acyclic_false_for_self_loop() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "a", None, None);
    assert!(!alg::is_acyclic(&g));
}

// ============================================================
// Algorithm - Tarjan (SCC)
// ============================================================

#[test]
fn tarjan_empty_graph() {
    let g: Graph<(), ()> = Graph::new();
    assert!(alg::tarjan(&g).is_empty());
}

#[test]
fn tarjan_single_node() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    let sccs = alg::tarjan(&g);
    assert_eq!(sccs.len(), 1);
    assert_eq!(sccs[0], vec!["a"]);
}

#[test]
fn tarjan_cycle() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c", "a"], None);
    let sccs = alg::tarjan(&g);
    let big_scc: Vec<&Vec<String>> = sccs.iter().filter(|s| s.len() > 1).collect();
    assert_eq!(big_scc.len(), 1);
    let mut scc = big_scc[0].clone();
    scc.sort();
    assert_eq!(scc, vec!["a", "b", "c"]);
}

#[test]
fn tarjan_two_cycles() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "a"], None);
    g.set_path(&["c", "d", "c"], None);
    let sccs = alg::tarjan(&g);
    let mut big_sccs: Vec<Vec<String>> = sccs
        .into_iter()
        .filter(|s| s.len() > 1)
        .map(|mut s| {
            s.sort();
            s
        })
        .collect();
    big_sccs.sort();
    assert_eq!(big_sccs.len(), 2);
    assert_eq!(big_sccs[0], vec!["a", "b"]);
    assert_eq!(big_sccs[1], vec!["c", "d"]);
}

// ============================================================
// Algorithm - find_cycles
// ============================================================

#[test]
fn find_cycles_empty() {
    let g: Graph<(), ()> = Graph::new();
    assert!(alg::find_cycles(&g).is_empty());
}

#[test]
fn find_cycles_acyclic() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    assert!(alg::find_cycles(&g).is_empty());
}

#[test]
fn find_cycles_self_loop() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    g.set_edge("a", "a", None, None);
    let cycles = alg::find_cycles(&g);
    assert_eq!(cycles.len(), 1);
}

// ============================================================
// Algorithm - Components
// ============================================================

#[test]
fn components_empty() {
    let g: Graph<(), ()> = Graph::new();
    assert!(alg::components(&g).is_empty());
}

#[test]
fn components_unconnected_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    g.set_node("b", None);
    let comps = alg::components(&g);
    assert_eq!(comps.len(), 2);
}

#[test]
fn components_connected() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let comps = alg::components(&g);
    assert_eq!(comps.len(), 1);
    assert_eq!(comps[0].len(), 3);
}

#[test]
fn components_two_components() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "d", None, None);
    let comps = alg::components(&g);
    assert_eq!(comps.len(), 2);
}

// ============================================================
// Algorithm - DFS / Preorder / Postorder
// ============================================================

#[test]
fn preorder_singleton() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    assert_eq!(alg::preorder(&g, &["a"]), vec!["a"]);
}

#[test]
fn preorder_tree() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "c", None, None);
    let result = alg::preorder(&g, &["a"]);
    assert_eq!(result[0], "a");
    assert_eq!(result.len(), 3);
}

#[test]
fn postorder_singleton() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    assert_eq!(alg::postorder(&g, &["a"]), vec!["a"]);
}

#[test]
fn postorder_tree() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "c", None, None);
    let result = alg::postorder(&g, &["a"]);
    // a should be last in postorder
    assert_eq!(result.last().unwrap(), "a");
    assert_eq!(result.len(), 3);
}

#[test]
fn dfs_visits_each_node_once() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "d"], None);
    g.set_path(&["a", "c", "d"], None);
    let result = alg::preorder(&g, &["a"]);
    assert_eq!(result.len(), 4);
    let unique: std::collections::HashSet<_> = result.iter().collect();
    assert_eq!(unique.len(), 4);
}

// ============================================================
// Graph - Additional setNode / node tests
// ============================================================

#[test]
fn set_node_is_idempotent() {
    let mut g: Graph<&str, ()> = Graph::new();
    g.set_node("a", Some("foo"));
    g.set_node("a", Some("foo"));
    assert_eq!(g.node("a"), Some(&"foo"));
    assert_eq!(g.node_count(), 1);
}

#[test]
fn nodes_empty_graph() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.nodes(), Vec::<String>::new());
}

#[test]
fn remove_node_is_idempotent() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    g.remove_node("a");
    let result = g.remove_node("a");
    assert_eq!(result, None);
    assert!(!g.has_node("a"));
    assert_eq!(g.node_count(), 0);
}

// ============================================================
// Graph - Additional sources / sinks tests
// ============================================================

#[test]
fn sources_includes_isolated_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    g.set_node("d", None);
    let mut sources = g.sources();
    sources.sort();
    assert_eq!(sources, vec!["a", "d"]);
}

#[test]
fn sinks_includes_isolated_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    g.set_node("d", None);
    let mut sinks = g.sinks();
    sinks.sort();
    assert_eq!(sinks, vec!["c", "d"]);
}

// ============================================================
// Graph - Additional filterNodes tests
// ============================================================

#[test]
fn filter_nodes_returns_identical_graph_for_all_pass() {
    let mut g: Graph<i32, i32> = Graph::new();
    g.set_node("a", Some(123));
    g.set_path(&["a", "b", "c"], None);
    g.set_edge("a", "c", Some(456), None);
    let g2 = g.filter_nodes(|_| true);
    let mut nodes = g2.nodes();
    nodes.sort();
    assert_eq!(nodes, vec!["a", "b", "c"]);
    assert!(g2.has_edge("a", "b", None));
    assert!(g2.has_edge("b", "c", None));
    assert!(g2.has_edge("a", "c", None));
    assert_eq!(g2.node("a"), Some(&123));
    assert_eq!(g2.edge("a", "c", None), Some(&456));
}

#[test]
fn filter_nodes_returns_empty_graph_for_none_pass() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    let g2 = g.filter_nodes(|_| false);
    assert_eq!(g2.nodes().len(), 0);
    assert_eq!(g2.edges().len(), 0);
}

#[test]
fn filter_nodes_removes_edges_to_removed_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    let g2 = g.filter_nodes(|v| v == "a");
    let mut nodes = g2.nodes();
    nodes.sort();
    assert_eq!(nodes, vec!["a"]);
    assert_eq!(g2.edges().len(), 0);
}

#[test]
fn filter_nodes_preserves_directed_option() {
    let g: Graph<(), ()> = Graph::new();
    assert!(g.filter_nodes(|_| true).is_directed());

    let g: Graph<(), ()> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    assert!(!g.filter_nodes(|_| true).is_directed());
}

#[test]
fn filter_nodes_preserves_multigraph_option() {
    let g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    assert!(g.filter_nodes(|_| true).is_multigraph());

    let g: Graph<(), ()> = Graph::new();
    assert!(!g.filter_nodes(|_| true).is_multigraph());
}

#[test]
fn filter_nodes_preserves_compound_option() {
    let g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    assert!(g.filter_nodes(|_| true).is_compound());

    let g: Graph<(), ()> = Graph::new();
    assert!(!g.filter_nodes(|_| true).is_compound());
}

#[test]
fn filter_nodes_includes_subgraphs() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("a", Some("parent"));
    let g2 = g.filter_nodes(|_| true);
    assert_eq!(g2.parent("a"), Some("parent"));
}

#[test]
fn filter_nodes_includes_multi_level_subgraphs() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("a", Some("parent"));
    g.set_parent("parent", Some("root"));
    let g2 = g.filter_nodes(|_| true);
    assert_eq!(g2.parent("a"), Some("parent"));
    assert_eq!(g2.parent("parent"), Some("root"));
}

#[test]
fn filter_nodes_promotes_child_when_parent_filtered_out() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("a", Some("parent"));
    g.set_parent("parent", Some("root"));
    let g2 = g.filter_nodes(|v| v != "parent");
    assert_eq!(g2.parent("a"), Some("root"));
}

// ============================================================
// Graph - Additional setParent tests
// ============================================================

#[test]
#[should_panic]
fn set_parent_throws_on_non_compound() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_parent("a", Some("b"));
}

#[test]
fn set_parent_moves_node_to_new_parent() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("a", Some("parent"));
    g.set_parent("a", Some("parent2"));
    assert_eq!(g.parent("a"), Some("parent2"));
    assert!(g.children(Some("parent")).is_empty());
    assert_eq!(g.children(Some("parent2")), vec!["a"]);
}

#[test]
fn set_parent_idempotent_remove() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("a", Some("parent"));
    g.set_parent("a", None);
    g.set_parent("a", None);
    assert_eq!(g.parent("a"), None);
    let mut top = g.children(None);
    top.sort();
    assert_eq!(top, vec!["a", "parent"]);
}

// ============================================================
// Graph - Additional parent tests
// ============================================================

#[test]
fn parent_returns_none_for_non_compound() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.parent("a"), None);
}

#[test]
fn parent_returns_none_for_unknown_node() {
    let g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    assert_eq!(g.parent("a"), None);
}

#[test]
fn parent_returns_current_assignment() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("parent", None);
    g.set_parent("a", Some("parent"));
    assert_eq!(g.parent("a"), Some("parent"));
}

// ============================================================
// Graph - Additional children tests
// ============================================================

#[test]
fn children_defaults_to_empty_for_new_compound_node() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    assert!(g.children(Some("a")).is_empty());
}

#[test]
fn children_returns_empty_for_non_compound_leaf() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    assert!(g.children(Some("a")).is_empty());
}

#[test]
fn children_returns_all_nodes_for_non_compound_root() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    g.set_node("b", None);
    let mut children = g.children(None);
    children.sort();
    assert_eq!(children, vec!["a", "b"]);
}

#[test]
fn children_of_parent_compound() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("a", Some("parent"));
    g.set_parent("b", Some("parent"));
    let mut children = g.children(Some("parent"));
    children.sort();
    assert_eq!(children, vec!["a", "b"]);
}

#[test]
fn children_without_parent_returns_top_level() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_node("c", None);
    g.set_node("parent", None);
    g.set_parent("a", Some("parent"));
    let mut top = g.children(None);
    top.sort();
    assert_eq!(top, vec!["b", "c", "parent"]);
}

// ============================================================
// Graph - removeNode removes compound relationships
// ============================================================

#[test]
fn remove_node_removes_compound_relationships() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("c", Some("b"));
    g.set_parent("b", Some("a"));
    g.remove_node("b");
    assert_eq!(g.parent("b"), None);
    assert!(g.children(Some("b")).is_empty());
    // "a" should no longer list "b" as child
    let a_children = g.children(Some("a"));
    assert!(!a_children.contains(&"b".to_string()));
    // "c" gets reparented to "a"
    assert_eq!(g.parent("c"), Some("a"));
}

// ============================================================
// Graph - Additional predecessors / successors / neighbors tests
// ============================================================

#[test]
fn predecessors_returns_none_for_unknown_node() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.predecessors("a"), None);
}

#[test]
fn predecessors_includes_self_loops() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    g.set_edge("a", "a", None, None);
    let mut preds = g.predecessors("a").unwrap();
    preds.sort();
    assert_eq!(preds, vec!["a"]);
}

#[test]
fn successors_returns_none_for_unknown_node() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.successors("a"), None);
}

#[test]
fn successors_includes_self_loops() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    g.set_edge("a", "a", None, None);
    let mut succs = g.successors("a").unwrap();
    succs.sort();
    assert_eq!(succs, vec!["a", "b"]);
}

#[test]
fn successors_returns_empty_for_leaf() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let succs = g.successors("c").unwrap();
    assert!(succs.is_empty());
}

#[test]
fn neighbors_returns_none_for_unknown_node() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.neighbors("a"), None);
}

#[test]
fn neighbors_includes_self_loop() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    g.set_edge("a", "a", None, None);
    let mut neighbors = g.neighbors("a").unwrap();
    neighbors.sort();
    assert_eq!(neighbors, vec!["a", "b"]);
}

// ============================================================
// Graph - Additional isLeaf tests
// ============================================================

#[test]
fn is_leaf_false_for_connected_undirected() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_edge("a", "b", None, None);
    assert!(!g.is_leaf("b"));
}

#[test]
fn is_leaf_true_for_unconnected_undirected() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_node("a", None);
    assert!(g.is_leaf("a"));
}

#[test]
fn is_leaf_true_for_unconnected_directed() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    assert!(g.is_leaf("a"));
}

#[test]
fn is_leaf_false_for_predecessor_directed() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_edge("a", "b", None, None);
    assert!(!g.is_leaf("a"));
}

#[test]
fn is_leaf_true_for_successor_directed() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    g.set_node("b", None);
    g.set_edge("a", "b", None, None);
    assert!(g.is_leaf("b"));
}

// ============================================================
// Graph - Additional edges tests
// ============================================================

#[test]
fn edges_empty_graph() {
    let g: Graph<(), ()> = Graph::new();
    assert!(g.edges().is_empty());
}

// ============================================================
// Graph - Additional setPath tests
// ============================================================

#[test]
fn set_path_with_label() {
    let mut g: Graph<(), i32> = Graph::new();
    g.set_path(&["a", "b", "c"], Some(42));
    assert_eq!(g.edge("a", "b", None), Some(&42));
    assert_eq!(g.edge("b", "c", None), Some(&42));
}

// ============================================================
// Graph - Additional setEdge tests
// ============================================================

#[test]
fn set_edge_creates_multi_edge_only_in_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, Some("name"));
    assert!(!g.has_edge("a", "b", None));
    assert!(g.has_edge("a", "b", Some("name")));
}

#[test]
#[should_panic]
fn set_edge_panics_for_named_edge_on_non_multigraph() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, Some("name"));
}

#[test]
fn set_edge_directed_treats_opposite_as_distinct() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    assert!(g.has_edge("a", "b", None));
    assert!(!g.has_edge("b", "a", None));
}

#[test]
fn set_edge_undirected_handles_both_directions() {
    let mut g: Graph<(), i32> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("a", "b", Some(42), None);
    assert_eq!(g.edge("a", "b", None), Some(&42));
    assert_eq!(g.edge("b", "a", None), Some(&42));
}

// ============================================================
// Graph - Additional removeEdge tests
// ============================================================

#[test]
fn remove_edge_no_effect_when_absent() {
    let mut g: Graph<(), ()> = Graph::new();
    g.remove_edge("a", "b", None);
    assert!(!g.has_edge("a", "b", None));
    assert_eq!(g.edge_count(), 0);
}

#[test]
fn remove_edge_correctly_removes_neighbors() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.remove_edge("a", "b", None);
    assert_eq!(g.successors("a").unwrap(), Vec::<String>::new());
    assert_eq!(g.neighbors("a").unwrap(), Vec::<String>::new());
    assert_eq!(g.predecessors("b").unwrap(), Vec::<String>::new());
    assert_eq!(g.neighbors("b").unwrap(), Vec::<String>::new());
}

#[test]
fn remove_edge_correctly_decrements_neighbor_count_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "b", None, Some("foo"));
    g.remove_edge("a", "b", None);
    assert!(g.has_edge("a", "b", Some("foo")));
    assert_eq!(g.successors("a").unwrap(), vec!["b"]);
    assert_eq!(g.neighbors("a").unwrap(), vec!["b"]);
    assert_eq!(g.predecessors("b").unwrap(), vec!["a"]);
    assert_eq!(g.neighbors("b").unwrap(), vec!["a"]);
}

#[test]
fn remove_edge_works_with_undirected() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("h", "g", None, None);
    g.remove_edge("g", "h", None);
    assert_eq!(g.neighbors("g").unwrap(), Vec::<String>::new());
    assert_eq!(g.neighbors("h").unwrap(), Vec::<String>::new());
}

// ============================================================
// Graph - Additional inEdges tests
// ============================================================

#[test]
fn in_edges_returns_none_for_unknown_node() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.in_edges("a", None), None);
}

#[test]
fn in_edges_returns_empty_for_source_node() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let in_e = g.in_edges("a", None).unwrap();
    assert!(in_e.is_empty());
}

#[test]
fn in_edges_works_for_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "b", None, Some("bar"));
    g.set_edge("a", "b", None, Some("foo"));
    let in_e = g.in_edges("a", None).unwrap();
    assert!(in_e.is_empty());
    let in_b = g.in_edges("b", None).unwrap();
    assert_eq!(in_b.len(), 3);
}

// ============================================================
// Graph - Additional outEdges tests
// ============================================================

#[test]
fn out_edges_returns_none_for_unknown_node() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.out_edges("a", None), None);
}

#[test]
fn out_edges_returns_all_outgoing() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let out_a = g.out_edges("a", None).unwrap();
    assert_eq!(out_a.len(), 1);
    assert_eq!(out_a[0].v, "a");
    assert_eq!(out_a[0].w, "b");
    let out_b = g.out_edges("b", None).unwrap();
    assert_eq!(out_b.len(), 1);
    let out_c = g.out_edges("c", None).unwrap();
    assert!(out_c.is_empty());
}

#[test]
fn out_edges_works_for_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "b", None, Some("bar"));
    g.set_edge("a", "b", None, Some("foo"));
    let out_a = g.out_edges("a", None).unwrap();
    assert_eq!(out_a.len(), 3);
    let out_b = g.out_edges("b", None).unwrap();
    assert!(out_b.is_empty());
}

// ============================================================
// Graph - Additional nodeEdges tests
// ============================================================

#[test]
fn node_edges_returns_none_for_unknown_node() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.node_edges("a", None), None);
}

#[test]
fn node_edges_returns_all_incident_edges() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let ne_a = g.node_edges("a", None).unwrap();
    assert_eq!(ne_a.len(), 1);
    let ne_b = g.node_edges("b", None).unwrap();
    assert_eq!(ne_b.len(), 2);
    let ne_c = g.node_edges("c", None).unwrap();
    assert_eq!(ne_c.len(), 1);
}

#[test]
fn node_edges_works_for_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "b", None, Some("bar"));
    g.set_edge("a", "b", None, Some("foo"));
    let ne_a = g.node_edges("a", None).unwrap();
    assert_eq!(ne_a.len(), 3);
    let ne_b = g.node_edges("b", None).unwrap();
    assert_eq!(ne_b.len(), 3);
}

// ============================================================
// Graph - Undirected additional tests
// ============================================================

#[test]
fn undirected_in_edges_and_out_edges_are_same() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    let in_b = g.in_edges("b", None).unwrap();
    let out_b = g.out_edges("b", None).unwrap();
    assert_eq!(in_b.len(), out_b.len());
}

#[test]
fn undirected_edge_retrieval_either_direction() {
    let mut g: Graph<(), i32> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("a", "b", Some(42), None);
    assert_eq!(g.edge("a", "b", None), Some(&42));
    assert_eq!(g.edge("b", "a", None), Some(&42));
}

#[test]
fn undirected_neighbors_returns_all() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let mut neighbors = g.neighbors("b").unwrap();
    neighbors.sort();
    assert_eq!(neighbors, vec!["a", "c"]);
}

// ============================================================
// Graph - setDefaultEdgeLabel tests
// ============================================================

#[test]
fn set_default_edge_label_does_not_change_existing() {
    let mut g: Graph<(), String> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_default_edge_label(|_| "foo".to_string());
    assert_eq!(g.edge("a", "b", None), None);
}

#[test]
fn set_default_edge_label_not_used_with_explicit_value() {
    let mut g: Graph<(), String> = Graph::new();
    g.set_default_edge_label(|_| "foo".to_string());
    g.set_edge("a", "b", Some("bar".to_string()), None);
    assert_eq!(g.edge("a", "b", None), Some(&"bar".to_string()));
}

// ============================================================
// Graph - setDefaultNodeLabel tests
// ============================================================

#[test]
fn set_default_node_label_does_not_change_existing() {
    let mut g: Graph<String, ()> = Graph::new();
    g.set_node("a", None);
    g.set_default_node_label(|_| "foo".to_string());
    // "a" already existed without a value; adding the default label factory does not update it
    assert_eq!(g.node("a"), None);
}

#[test]
fn set_default_node_label_not_used_with_explicit_value() {
    let mut g: Graph<String, ()> = Graph::new();
    g.set_default_node_label(|_| "foo".to_string());
    g.set_node("a", Some("bar".to_string()));
    assert_eq!(g.node("a"), Some(&"bar".to_string()));
}

// ============================================================
// Algorithm - Additional components tests
// ============================================================

#[test]
fn components_single_node() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("a", None);
    let comps = alg::components(&g);
    assert_eq!(comps.len(), 1);
    assert_eq!(comps[0].len(), 1);
}

// ============================================================
// Algorithm - Additional find_cycles tests
// ============================================================

#[test]
fn find_cycles_finds_single_cycle() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c", "a"], None);
    let cycles = alg::find_cycles(&g);
    assert_eq!(cycles.len(), 1);
    let mut cycle = cycles[0].clone();
    cycle.sort();
    assert_eq!(cycle, vec!["a", "b", "c"]);
}

#[test]
fn find_cycles_finds_two_separate_cycles() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "a"], None);
    g.set_path(&["c", "d", "c"], None);
    let mut cycles = alg::find_cycles(&g);
    assert_eq!(cycles.len(), 2);
    for cycle in &mut cycles {
        cycle.sort();
    }
    cycles.sort();
    assert_eq!(cycles[0], vec!["a", "b"]);
    assert_eq!(cycles[1], vec!["c", "d"]);
}

// ============================================================
// Algorithm - Additional tarjan tests
// ============================================================

#[test]
fn tarjan_chain_all_singletons() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    let sccs = alg::tarjan(&g);
    assert_eq!(sccs.len(), 3);
    for scc in &sccs {
        assert_eq!(scc.len(), 1);
    }
}

// ============================================================
// Algorithm - Additional preorder / postorder tests
// ============================================================

#[test]
fn preorder_multiple_roots() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "d", None, None);
    let result = alg::preorder(&g, &["a", "c"]);
    assert_eq!(result.len(), 4);
    // a should come before b, c should come before d
    let pos = |v: &str| result.iter().position(|x| x == v).unwrap();
    assert!(pos("a") < pos("b"));
    assert!(pos("c") < pos("d"));
}

#[test]
fn postorder_multiple_roots() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "d", None, None);
    let result = alg::postorder(&g, &["a", "c"]);
    assert_eq!(result.len(), 4);
    // b should come before a, d should come before c
    let pos = |v: &str| result.iter().position(|x| x == v).unwrap();
    assert!(pos("b") < pos("a"));
    assert!(pos("d") < pos("c"));
}

// ============================================================
// Graph - setGraph / graph_label tests (from graph-test.ts "setGraph")
// ============================================================

#[test]
fn set_graph_label_and_get() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_graph_label("foo".to_string());
    assert_eq!(g.graph_label::<String>(), Some(&"foo".to_string()));
}

#[test]
fn graph_label_defaults_to_none() {
    let g: Graph<(), ()> = Graph::new();
    assert_eq!(g.graph_label::<String>(), None);
}

// ============================================================
// Graph - setNode additional tests (from graph-test.ts "setNode")
// ============================================================

#[test]
fn set_node_creates_with_no_label() {
    let mut g: Graph<&str, ()> = Graph::new();
    g.set_node("a", None);
    assert!(g.has_node("a"));
    assert_eq!(g.node("a"), None);
    assert_eq!(g.node_count(), 1);
}

#[test]
fn set_node_uses_stringified_id() {
    // In Rust, node IDs are always strings. This test verifies
    // that "1" as a string key works correctly.
    let mut g: Graph<(), ()> = Graph::new();
    g.set_node("1", None);
    assert!(g.has_node("1"));
    assert_eq!(g.nodes(), vec!["1"]);
}

// ============================================================
// Graph - setNodeDefaults additional tests
// ============================================================

#[test]
fn set_default_node_label_with_constant_fn() {
    let mut g: Graph<String, ()> = Graph::new();
    g.set_default_node_label(|_| "foo".to_string());
    g.set_node("a", None);
    assert_eq!(g.node("a"), Some(&"foo".to_string()));
}

#[test]
fn set_default_node_label_with_name_fn() {
    let mut g: Graph<String, ()> = Graph::new();
    g.set_default_node_label(|v| format!("{}-foo", v));
    g.set_node("a", None);
    assert_eq!(g.node("a"), Some(&"a-foo".to_string()));
}

// ============================================================
// Graph - setParent additional tests (from graph-test.ts)
// ============================================================

#[test]
fn set_parent_creates_child_if_not_exist() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("parent", None);
    g.set_parent("a", Some("parent"));
    assert!(g.has_node("a"));
    assert_eq!(g.parent("a"), Some("parent"));
}

#[test]
fn set_parent_has_parent_none_if_never_invoked() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_node("a", None);
    assert_eq!(g.parent("a"), None);
}

#[test]
fn set_parent_removes_parent_on_none() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("a", Some("parent"));
    g.set_parent("a", None);
    assert_eq!(g.parent("a"), None);
    let mut top = g.children(None);
    top.sort();
    assert_eq!(top, vec!["a", "parent"]);
}

#[test]
fn set_parent_stringified_id() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("2", Some("1"));
    g.set_parent("3", Some("2"));
    assert_eq!(g.parent("2"), Some("1"));
    assert_eq!(g.parent("3"), Some("2"));
}

// The JS test "preserves the tree invariant" expects setParent("a", "c") to throw
// when c is a descendant of a. Our Rust implementation does not currently enforce this.
#[test]
#[should_panic]
fn set_parent_preserves_tree_invariant() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    g.set_parent("c", Some("b"));
    g.set_parent("b", Some("a"));
    // This should panic because "a" is an ancestor of "c"
    g.set_parent("a", Some("c"));
}

// ============================================================
// Graph - children additional (from graph-test.ts)
// ============================================================

#[test]
fn children_returns_empty_for_unknown_compound_node() {
    let g: Graph<(), ()> = Graph::with_options(GraphOptions {
        compound: true,
        ..Default::default()
    });
    // node "a" does not exist
    assert!(g.children(Some("a")).is_empty());
}

#[test]
fn children_returns_empty_for_non_compound_without_node() {
    let g: Graph<(), ()> = Graph::new();
    assert!(g.children(Some("a")).is_empty());
}

// ============================================================
// Graph - setEdge additional tests (from graph-test.ts)
// ============================================================

#[test]
fn set_edge_changes_value_for_multi_edge() {
    let mut g: Graph<(), &str> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", Some("value"), Some("name"));
    g.set_edge("a", "b", None, Some("name"));
    // After setting with None, the old value should still be retained
    assert_eq!(g.edge("a", "b", Some("name")), Some(&"value"));
    assert!(g.has_edge("a", "b", Some("name")));
}

#[test]
fn set_edge_undirected_id_order() {
    // Tests undirected edges where id has different order than stringified id
    let mut g: Graph<(), &str> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("9", "10", Some("foo"), None);
    assert!(g.has_edge("9", "10", None));
    assert!(g.has_edge("10", "9", None));
    assert_eq!(g.edge("9", "10", None), Some(&"foo"));
}

#[test]
fn set_edge_stringified_ids() {
    let mut g: Graph<(), &str> = Graph::new();
    g.set_edge("1", "2", Some("foo"), None);
    let edges = g.edges();
    assert_eq!(edges.len(), 1);
    assert_eq!(edges[0].v, "1");
    assert_eq!(edges[0].w, "2");
    assert_eq!(g.edge("1", "2", None), Some(&"foo"));
}

#[test]
fn set_edge_stringified_ids_multigraph() {
    let mut g: Graph<(), &str> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("1", "2", Some("foo"), Some("3"));
    assert_eq!(g.edge("1", "2", Some("3")), Some(&"foo"));
    let edges = g.edges();
    assert_eq!(edges.len(), 1);
    assert_eq!(edges[0].v, "1");
    assert_eq!(edges[0].w, "2");
    assert_eq!(edges[0].name, Some("3".to_string()));
}

// ============================================================
// Graph - setDefaultEdgeLabel additional tests (from graph-test.ts)
// ============================================================

#[test]
fn set_default_edge_label_does_not_override_existing_multi_edge() {
    let mut g: Graph<(), String> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", Some("old".to_string()), Some("name"));
    g.set_default_edge_label(|_| "should not set this".to_string());
    g.set_edge("a", "b", None, Some("name"));
    assert_eq!(g.edge("a", "b", Some("name")), Some(&"old".to_string()));
}

// ============================================================
// Graph - edge additional tests (from graph-test.ts)
// ============================================================

#[test]
fn edge_returns_none_for_nonexistent_edge() {
    let g: Graph<(), i32> = Graph::new();
    assert_eq!(g.edge("a", "b", None), None);
    assert_eq!(g.edge("a", "b", Some("foo")), None);
}

#[test]
fn edge_returns_value_of_multi_edge() {
    let mut g: Graph<(), i32> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", Some(42), Some("foo"));
    assert_eq!(g.edge("a", "b", Some("foo")), Some(&42));
    assert_eq!(g.edge("a", "b", None), None);
}

#[test]
fn edge_undirected_returns_either_direction() {
    let mut g: Graph<(), i32> = Graph::with_options(GraphOptions {
        directed: false,
        ..Default::default()
    });
    g.set_edge("a", "b", Some(42), None);
    assert_eq!(g.edge("a", "b", None), Some(&42));
    assert_eq!(g.edge("b", "a", None), Some(&42));
}

// ============================================================
// Graph - edge_by_obj tests (from graph-test.ts "can take an edge object")
// ============================================================

#[test]
fn edge_by_obj_simple() {
    let mut g: Graph<(), &str> = Graph::new();
    g.set_edge("a", "b", Some("value"), None);
    let e = Edge::new("a", "b");
    assert_eq!(g.edge_by_obj(&e), Some(&"value"));
}

#[test]
fn edge_by_obj_multigraph() {
    let mut g: Graph<(), &str> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", Some("value"), Some("name"));
    let e = Edge::with_name("a", "b", "name");
    assert_eq!(g.edge_by_obj(&e), Some(&"value"));
}

// ============================================================
// Graph - removeEdge additional (from graph-test.ts)
// ============================================================

#[test]
fn remove_edge_by_name_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, Some("foo"));
    g.remove_edge("a", "b", Some("foo"));
    assert!(!g.has_edge("a", "b", Some("foo")));
    assert_eq!(g.edge_count(), 0);
}

// ============================================================
// Graph - inEdges additional tests (from graph-test.ts)
// ============================================================

#[test]
fn in_edges_returns_edges_that_point_at_node() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    assert_eq!(g.in_edges("a", None).unwrap().len(), 0);
    let in_b = g.in_edges("b", None).unwrap();
    assert_eq!(in_b.len(), 1);
    assert_eq!(in_b[0].v, "a");
    assert_eq!(in_b[0].w, "b");
    let in_c = g.in_edges("c", None).unwrap();
    assert_eq!(in_c.len(), 1);
    assert_eq!(in_c[0].v, "b");
    assert_eq!(in_c[0].w, "c");
}

#[test]
fn in_edges_filtered_by_source_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "b", None, Some("foo"));
    g.set_edge("a", "c", None, None);
    g.set_edge("b", "c", None, None);
    g.set_edge("z", "a", None, None);
    g.set_edge("z", "b", None, None);
    assert_eq!(g.in_edges("a", Some("b")).unwrap().len(), 0);
    let in_b_from_a = g.in_edges("b", Some("a")).unwrap();
    assert_eq!(in_b_from_a.len(), 2);
}

// ============================================================
// Graph - outEdges additional tests (from graph-test.ts)
// ============================================================

#[test]
fn out_edges_returns_edges_from_node() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let out_a = g.out_edges("a", None).unwrap();
    assert_eq!(out_a.len(), 1);
    assert_eq!(out_a[0].v, "a");
    assert_eq!(out_a[0].w, "b");
    let out_b = g.out_edges("b", None).unwrap();
    assert_eq!(out_b.len(), 1);
    assert_eq!(out_b[0].v, "b");
    assert_eq!(out_b[0].w, "c");
    let out_c = g.out_edges("c", None).unwrap();
    assert!(out_c.is_empty());
}

#[test]
fn out_edges_filtered_by_target_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "b", None, Some("foo"));
    g.set_edge("a", "c", None, None);
    g.set_edge("b", "c", None, None);
    g.set_edge("z", "a", None, None);
    g.set_edge("z", "b", None, None);
    let out_a_to_b = g.out_edges("a", Some("b")).unwrap();
    assert_eq!(out_a_to_b.len(), 2);
    let out_b_to_a = g.out_edges("b", Some("a")).unwrap();
    assert!(out_b_to_a.is_empty());
}

// ============================================================
// Graph - nodeEdges additional tests (from graph-test.ts)
// ============================================================

#[test]
fn node_edges_between_specific_nodes_multigraph() {
    let mut g: Graph<(), ()> = Graph::with_options(GraphOptions {
        multigraph: true,
        ..Default::default()
    });
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "b", None, Some("foo"));
    g.set_edge("a", "c", None, None);
    g.set_edge("b", "c", None, None);
    g.set_edge("z", "a", None, None);
    g.set_edge("z", "b", None, None);
    let ne_a_b = g.node_edges("a", Some("b")).unwrap();
    assert_eq!(ne_a_b.len(), 2);
    let ne_b_a = g.node_edges("b", Some("a")).unwrap();
    assert_eq!(ne_b_a.len(), 2);
}

// ============================================================
// Algorithm - topsort additional tests (from topsort-test.ts)
// ============================================================

#[test]
fn topsort_sorts_earlier_nodes_before_later() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["b", "c", "a"], None);
    let result = alg::topsort(&g).unwrap();
    assert_eq!(result, vec!["b", "c", "a"]);
}

#[test]
fn topsort_cycle_with_extra_edge() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["b", "c", "a", "b"], None);
    g.set_edge("b", "d", None, None);
    assert!(alg::topsort(&g).is_err());
}

#[test]
fn topsort_cycle_with_isolated_node() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["b", "c", "a", "b"], None);
    g.set_node("d", None);
    assert!(alg::topsort(&g).is_err());
}

// ============================================================
// Algorithm - is_acyclic additional tests (from is-acyclic-test.ts)
// ============================================================

#[test]
fn is_acyclic_false_for_single_node_cycle() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "a"], None);
    assert!(!alg::is_acyclic(&g));
}

// ============================================================
// Algorithm - find_cycles additional tests (from find-cycles-test.ts)
// ============================================================

#[test]
fn find_cycles_single_node_self_loop() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "a"], None);
    let cycles = alg::find_cycles(&g);
    assert_eq!(cycles.len(), 1);
    assert_eq!(cycles[0], vec!["a"]);
}

#[test]
fn find_cycles_two_node_cycle() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "a"], None);
    let mut cycles = alg::find_cycles(&g);
    assert_eq!(cycles.len(), 1);
    cycles[0].sort();
    assert_eq!(cycles[0], vec!["a", "b"]);
}

#[test]
fn find_cycles_triangle() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c", "a"], None);
    let mut cycles = alg::find_cycles(&g);
    assert_eq!(cycles.len(), 1);
    cycles[0].sort();
    assert_eq!(cycles[0], vec!["a", "b", "c"]);
}

#[test]
fn find_cycles_multiple_mixed() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "a"], None);
    g.set_path(&["c", "d", "e", "c"], None);
    g.set_path(&["f", "g", "g"], None);
    g.set_node("h", None);
    let mut cycles = alg::find_cycles(&g);
    for c in &mut cycles {
        c.sort();
    }
    cycles.sort();
    assert_eq!(cycles.len(), 3);
    assert_eq!(cycles[0], vec!["a", "b"]);
    assert_eq!(cycles[1], vec!["c", "d", "e"]);
    assert_eq!(cycles[2], vec!["g"]);
}

// ============================================================
// Algorithm - tarjan additional tests (from tarjan-test.ts)
// ============================================================

#[test]
fn tarjan_singletons_for_non_scc_nodes() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c"], None);
    g.set_edge("d", "c", None, None);
    let mut sccs: Vec<Vec<String>> = alg::tarjan(&g)
        .into_iter()
        .map(|mut s| {
            s.sort();
            s
        })
        .collect();
    sccs.sort();
    assert_eq!(sccs, vec![vec!["a"], vec!["b"], vec!["c"], vec!["d"]]);
}

#[test]
fn tarjan_single_component_for_cycle_of_1_edge() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "a"], None);
    let mut sccs: Vec<Vec<String>> = alg::tarjan(&g)
        .into_iter()
        .map(|mut s| {
            s.sort();
            s
        })
        .collect();
    sccs.sort();
    assert_eq!(sccs, vec![vec!["a", "b"]]);
}

#[test]
fn tarjan_single_component_for_triangle() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c", "a"], None);
    let mut sccs: Vec<Vec<String>> = alg::tarjan(&g)
        .into_iter()
        .map(|mut s| {
            s.sort();
            s
        })
        .collect();
    sccs.sort();
    assert_eq!(sccs, vec![vec!["a", "b", "c"]]);
}

#[test]
fn tarjan_multiple_components_with_singleton() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "a"], None);
    g.set_path(&["c", "d", "e", "c"], None);
    g.set_node("f", None);
    let mut sccs: Vec<Vec<String>> = alg::tarjan(&g)
        .into_iter()
        .map(|mut s| {
            s.sort();
            s
        })
        .collect();
    sccs.sort();
    assert_eq!(sccs, vec![vec!["a", "b"], vec!["c", "d", "e"], vec!["f"]]);
}

// ============================================================
// Algorithm - components additional tests (from components-test.ts)
// ============================================================

#[test]
fn components_returns_nodes_connected_by_neighbor_in_digraph() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "c", "a"], None);
    g.set_edge("d", "c", None, None);
    g.set_edge("e", "f", None, None);
    let mut comps: Vec<Vec<String>> = alg::components(&g)
        .into_iter()
        .map(|mut c| {
            c.sort();
            c
        })
        .collect();
    comps.sort();
    assert_eq!(comps.len(), 2);
    assert_eq!(comps[0], vec!["a", "b", "c", "d"]);
    assert_eq!(comps[1], vec!["e", "f"]);
}

// ============================================================
// Algorithm - preorder additional tests (from preorder-test.ts)
// ============================================================

#[test]
fn preorder_visits_each_node_once() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "d", "e"], None);
    g.set_path(&["a", "c", "d", "e"], None);
    let mut nodes = alg::preorder(&g, &["a"]);
    nodes.sort();
    assert_eq!(nodes, vec!["a", "b", "c", "d", "e"]);
}

#[test]
fn preorder_works_for_tree() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_path(&["a", "c", "d"], None);
    g.set_edge("c", "e", None, None);
    let nodes = alg::preorder(&g, &["a"]);
    let mut sorted = nodes.clone();
    sorted.sort();
    assert_eq!(sorted, vec!["a", "b", "c", "d", "e"]);
    let pos = |v: &str| nodes.iter().position(|x| x == v).unwrap();
    assert!(pos("b") > pos("a"));
    assert!(pos("c") > pos("a"));
    assert!(pos("d") > pos("c"));
    assert!(pos("e") > pos("c"));
}

#[test]
fn preorder_works_for_array_of_roots() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "d", None, None);
    g.set_node("e", None);
    g.set_node("f", None);
    let nodes = alg::preorder(&g, &["a", "c", "e"]);
    let pos = |v: &str| nodes.iter().position(|x| x == v).unwrap();
    assert!(pos("b") > pos("a"));
    assert!(pos("d") > pos("c"));
    let mut sorted = nodes.clone();
    sorted.sort();
    assert_eq!(sorted, vec!["a", "b", "c", "d", "e"]);
}

// ============================================================
// Algorithm - postorder additional tests (from postorder-test.ts)
// ============================================================

#[test]
fn postorder_visits_each_node_once() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_path(&["a", "b", "d", "e"], None);
    g.set_path(&["a", "c", "d", "e"], None);
    let mut nodes = alg::postorder(&g, &["a"]);
    nodes.sort();
    assert_eq!(nodes, vec!["a", "b", "c", "d", "e"]);
}

#[test]
fn postorder_works_for_tree() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_path(&["a", "c", "d"], None);
    g.set_edge("c", "e", None, None);
    let nodes = alg::postorder(&g, &["a"]);
    let pos = |v: &str| nodes.iter().position(|x| x == v).unwrap();
    assert!(pos("b") < pos("a"));
    assert!(pos("c") < pos("a"));
    assert!(pos("d") < pos("c"));
    assert!(pos("e") < pos("c"));
    let mut sorted = nodes.clone();
    sorted.sort();
    assert_eq!(sorted, vec!["a", "b", "c", "d", "e"]);
}

#[test]
fn postorder_works_for_array_of_roots() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("c", "d", None, None);
    g.set_node("e", None);
    g.set_node("f", None);
    let nodes = alg::postorder(&g, &["a", "b", "c", "e"]);
    let pos = |v: &str| nodes.iter().position(|x| x == v).unwrap();
    assert!(pos("b") < pos("a"));
    assert!(pos("d") < pos("c"));
    let mut sorted = nodes.clone();
    sorted.sort();
    assert_eq!(sorted, vec!["a", "b", "c", "d", "e"]);
}

#[test]
fn postorder_works_for_multiple_connected_roots() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("a", "c", None, None);
    g.set_edge("d", "c", None, None);
    let nodes = alg::postorder(&g, &["a", "d"]);
    let pos = |v: &str| nodes.iter().position(|x| x == v).unwrap();
    assert!(pos("b") < pos("a"));
    assert!(pos("c") < pos("a"));
    assert!(pos("c") < pos("d"));
    let mut sorted = nodes.clone();
    sorted.sort();
    assert_eq!(sorted, vec!["a", "b", "c", "d"]);
}

// ============================================================
// Graph - graph_label_mut test
// ============================================================

#[test]
fn graph_label_mut_allows_modification() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_graph_label(42i32);
    *g.graph_label_mut::<i32>().unwrap() = 99;
    assert_eq!(g.graph_label::<i32>(), Some(&99));
}

// ============================================================
// Graph - edge_mut test
// ============================================================

#[test]
fn edge_mut_allows_modification() {
    let mut g: Graph<(), i32> = Graph::new();
    g.set_edge("a", "b", Some(1), None);
    *g.edge_mut("a", "b", None).unwrap() = 42;
    assert_eq!(g.edge("a", "b", None), Some(&42));
}

// ============================================================
// Graph - deletes edge value if set with None (from graph-test.ts)
// In JS: setEdge("a","b","foo"); setEdge("a","b",undefined) => edge is undefined but exists
// In Rust: setting with None keeps old value (our design), so this tests our behavior.
// ============================================================

#[test]
fn set_edge_with_none_keeps_existing_value() {
    let mut g: Graph<(), &str> = Graph::new();
    g.set_edge("a", "b", Some("foo"), None);
    g.set_edge("a", "b", None, None);
    // Rust behavior: None does not overwrite existing value
    assert_eq!(g.edge("a", "b", None), Some(&"foo"));
    assert!(g.has_edge("a", "b", None));
}

// ============================================================
// Graph - edges returns keys for edges in graph (from graph-test.ts)
// ============================================================

#[test]
fn edges_returns_correct_edge_descriptors() {
    let mut g: Graph<(), ()> = Graph::new();
    g.set_edge("a", "b", None, None);
    g.set_edge("b", "c", None, None);
    let mut edges = g.edges();
    edges.sort_by(|a, b| a.v.cmp(&b.v).then(a.w.cmp(&b.w)));
    assert_eq!(edges.len(), 2);
    assert_eq!(edges[0].v, "a");
    assert_eq!(edges[0].w, "b");
    assert_eq!(edges[1].v, "b");
    assert_eq!(edges[1].w, "c");
}

// ============================================================
// Graph - Edge Display impl test
// ============================================================

#[test]
fn edge_display_format() {
    let e = Edge::new("a", "b");
    assert_eq!(format!("{}", e), "a->b");
    let e2 = Edge::with_name("a", "b", "foo");
    assert_eq!(format!("{}", e2), "a->b:foo");
}

// ============================================================
// Graph - Default impl test
// ============================================================

#[test]
fn graph_default_same_as_new() {
    let g1: Graph<(), ()> = Graph::new();
    let g2: Graph<(), ()> = Graph::default();
    assert_eq!(g1.node_count(), g2.node_count());
    assert_eq!(g1.edge_count(), g2.edge_count());
    assert_eq!(g1.is_directed(), g2.is_directed());
    assert_eq!(g1.is_multigraph(), g2.is_multigraph());
    assert_eq!(g1.is_compound(), g2.is_compound());
}

// ============================================================
// Graph - Debug impl test
// ============================================================

#[test]
fn graph_debug_format() {
    let g: Graph<i32, i32> = Graph::new();
    let debug = format!("{:?}", g);
    assert!(debug.contains("Graph"));
    assert!(debug.contains("directed"));
}