bounded_graph 0.3.0

//! Tests for bounded acyclic graph functionality

use crate::{
    BoundedAcyclicDiGraph, BoundedAcyclicGraphError, BoundedAcyclicStableDiGraph,
    BoundedGraphError, FixedEdgeCount,
};
use petgraph::graph::NodeIndex;

#[test]
fn test_acyclic_prevents_simple_cycle() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<10>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    // Create edge n1 -> n2
    assert!(graph.add_edge(n1, n2, ()).is_ok());

    // Try to create cycle: n2 -> n1 (should fail)
    match graph.add_edge(n2, n1, ()) {
        Err(BoundedAcyclicGraphError::Acyclic(_)) => {} // Expected
        other => panic!("Expected Acyclic error, got: {:?}", other),
    }
}

#[test]
fn test_acyclic_prevents_longer_cycle() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<10>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());
    let n4 = graph.add_node(FixedEdgeCount::empty());

    // Create path: n1 -> n2 -> n3 -> n4
    assert!(graph.add_edge(n1, n2, ()).is_ok());
    assert!(graph.add_edge(n2, n3, ()).is_ok());
    assert!(graph.add_edge(n3, n4, ()).is_ok());

    // Try to create cycle: n4 -> n1 (should fail)
    assert!(matches!(
        graph.add_edge(n4, n1, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));

    // Also try n4 -> n2 (should also fail)
    assert!(matches!(
        graph.add_edge(n4, n2, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));
}

#[test]
fn test_acyclic_allows_valid_edges() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<10>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Create a diamond pattern (valid DAG)
    //   n1
    //  /  \
    // n2  n3
    assert!(graph.add_edge(n1, n2, ()).is_ok());
    assert!(graph.add_edge(n1, n3, ()).is_ok());

    // Both edges are valid (no cycle)
    assert_eq!(graph.edge_count(), 2);
}

#[test]
fn test_bounded_constraint_checked_before_acyclic() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<1>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // n1 -> n2 succeeds (n1 has 1 max outgoing)
    assert!(graph.add_edge(n1, n2, ()).is_ok());

    // n1 -> n3 fails due to bounded constraint (not cycle)
    assert!(matches!(
        graph.add_edge(n1, n3, ()),
        Err(BoundedAcyclicGraphError::Bounded(
            BoundedGraphError::EdgeRejected {
                source_rejected: true,
                target_rejected: false,
                ..
            }
        ))
    ));
}

#[test]
fn test_both_constraints_respected() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<2>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Create path: n1 -> n2 -> n3
    assert!(graph.add_edge(n1, n2, ()).is_ok());
    assert!(graph.add_edge(n2, n3, ()).is_ok());

    // Try n3 -> n1: would create cycle
    assert!(matches!(
        graph.add_edge(n3, n1, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));

    // Add another outgoing edge from n1 (within capacity)
    let n4 = graph.add_node(FixedEdgeCount::empty());
    assert!(graph.add_edge(n1, n4, ()).is_ok());

    // Try third edge from n1: exceeds capacity
    let n5 = graph.add_node(FixedEdgeCount::empty());
    assert!(matches!(
        graph.add_edge(n1, n5, ()),
        Err(BoundedAcyclicGraphError::Bounded(
            BoundedGraphError::EdgeRejected {
                source_rejected: true,
                target_rejected: false,
                ..
            }
        ))
    ));
}

#[test]
fn test_asymmetric_bounds_with_acyclic() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<2, 5>, ()>::new();
    let hub = graph.add_node(FixedEdgeCount::empty());
    let spoke1 = graph.add_node(FixedEdgeCount::empty());
    let spoke2 = graph.add_node(FixedEdgeCount::empty());
    let spoke3 = graph.add_node(FixedEdgeCount::empty());

    // Hub can send to multiple spokes (within outgoing limit of 5)
    assert!(graph.add_edge(hub, spoke1, ()).is_ok());
    assert!(graph.add_edge(hub, spoke2, ()).is_ok());
    assert!(graph.add_edge(hub, spoke3, ()).is_ok());

    // Spokes cannot create cycles back to hub
    assert!(matches!(
        graph.add_edge(spoke1, hub, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));
}

#[test]
fn test_can_add_edge_checks_both_constraints() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<2>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Initially all edges are valid
    assert!(graph.can_add_edge(n1, n2));
    assert!(graph.can_add_edge(n2, n3));

    // Add edge n1 -> n2
    graph.add_edge(n1, n2, ()).unwrap();

    // n2 -> n1 would create cycle
    assert!(!graph.can_add_edge(n2, n1));

    // Add second edge from n1
    graph.add_edge(n1, n3, ()).unwrap();

    // n1 is now at capacity (2 outgoing edges)
    let n4 = graph.add_node(FixedEdgeCount::empty());
    assert!(!graph.can_add_edge(n1, n4));
}

#[test]
fn test_update_edge_existing() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, i32>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    // Add edge with weight 10
    let e1 = graph.add_edge(n1, n2, 10).unwrap();

    // Update edge to weight 20 (should succeed, no new edge)
    let e2 = graph.update_edge(n1, n2, 20).unwrap();

    // Should be the same edge
    assert_eq!(e1, e2);
}

#[test]
fn test_update_edge_new_respects_constraints() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, i32>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    // Create edge n1 -> n2
    graph.add_edge(n1, n2, 10).unwrap();

    // Try to update/add n2 -> n1 (would create cycle)
    assert!(matches!(
        graph.update_edge(n2, n1, 20),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));
}

#[test]
fn test_remove_edge_allows_new_edges() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<1>, &str>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Add edge (reaches capacity)
    let e = graph.add_edge(n1, n2, "a->b").unwrap();
    assert!(matches!(
        graph.add_edge(n1, n3, "a->c"),
        Err(BoundedAcyclicGraphError::Bounded(
            BoundedGraphError::EdgeRejected {
                source_rejected: true,
                target_rejected: false,
                ..
            }
        ))
    ));

    // Remove edge successfully
    assert_eq!(graph.remove_edge(e), Some("a->b"));
    assert_eq!(graph.edge_count(), 0);

    // Now we can add a new edge from n1 since capacity is freed
    assert!(graph.add_edge(n1, n3, "a->c").is_ok());
    assert_eq!(graph.edge_count(), 1);
}

#[test]
fn test_remove_node_updates_graph() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, &str>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    graph.add_edge(n1, n2, "a->b").unwrap();
    graph.add_edge(n2, n3, "b->c").unwrap();

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

    // Remove middle node - should remove the node and connected edges
    assert!(graph.remove_node(n2).is_some());

    // Graph updated correctly - note that in Graph (not StableGraph),
    // removing a node causes the highest-indexed node to take its place
    assert_eq!(graph.node_count(), 2);
    assert_eq!(graph.edge_count(), 0); // Both edges connected to n2 removed
}

#[test]
fn test_remove_edge_maintains_acyclicity() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Create path: n1 -> n2 -> n3
    graph.add_edge(n1, n2, ()).unwrap();
    let e = graph.add_edge(n2, n3, ()).unwrap();

    // Cannot create cycle
    assert!(matches!(
        graph.add_edge(n3, n1, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));

    // Remove edge n2 -> n3
    assert!(graph.remove_edge(e).is_some());
    assert_eq!(graph.edge_count(), 1);

    // Now can add n3 -> n2 (no path from n2 to n3 anymore)
    assert!(graph.add_edge(n3, n2, ()).is_ok());

    // After adding n3->n2, we have: n1->n2 and n3->n2
    // n3->n1 is OK (no path from n1 to n3)
    assert!(graph.add_edge(n3, n1, ()).is_ok());

    // But n2->n1 would create cycle: n1->n2->n1
    assert!(matches!(
        graph.add_edge(n2, n1, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));
}

#[test]
fn test_remove_node_maintains_acyclicity() {
    // Use StableGraph to keep node indices stable after removal
    let mut graph = BoundedAcyclicStableDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());
    let n4 = graph.add_node(FixedEdgeCount::empty());

    // Create path: n1 -> n2 -> n3 -> n4
    graph.add_edge(n1, n2, ()).unwrap();
    graph.add_edge(n2, n3, ()).unwrap();
    graph.add_edge(n3, n4, ()).unwrap();

    // Can't add n4 -> n1 (would create cycle)
    assert!(matches!(
        graph.add_edge(n4, n1, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));

    // Remove middle node n2
    assert!(graph.remove_node(n2).is_some());
    assert_eq!(graph.node_count(), 3);
    assert_eq!(graph.edge_count(), 1); // Only n3 -> n4 remains

    // After removing n2: n1 (isolated), n3 -> n4
    // Now n4 -> n1 is OK (no path from n1 to n4)
    assert!(graph.add_edge(n4, n1, ()).is_ok());

    // But n1 -> n3 would create cycle: n1 -> n3 -> n4 -> n1
    assert!(matches!(
        graph.add_edge(n1, n3, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));

    // n1 -> n4 is OK (just adds another path to existing n4 -> n1)
    // Wait, no! n1 -> n4 with existing n4 -> n1 creates a cycle!
    assert!(matches!(
        graph.add_edge(n1, n4, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));
}

#[test]
fn test_remove_node_allows_new_topology() {
    let mut graph = BoundedAcyclicStableDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Create: n1 -> n2 -> n3
    graph.add_edge(n1, n2, ()).unwrap();
    graph.add_edge(n2, n3, ()).unwrap();

    // Can't add n3 -> n1 (cycle)
    assert!(matches!(
        graph.add_edge(n3, n1, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));

    // Remove n2
    graph.remove_node(n2).unwrap();

    // Now n1 and n3 are disconnected, so n3 -> n1 is OK
    assert!(graph.add_edge(n3, n1, ()).is_ok());
}

#[test]
fn test_remove_nonexistent_edge() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    let e = graph.add_edge(n1, n2, ()).unwrap();

    // Remove edge once - succeeds
    assert!(graph.remove_edge(e).is_some());

    // Remove same edge again - returns None
    assert!(graph.remove_edge(e).is_none());
}

#[test]
fn test_remove_nonexistent_node() {
    let mut graph = BoundedAcyclicStableDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());

    // Remove node once - succeeds
    assert!(graph.remove_node(n1).is_some());

    // Remove same node again - returns None (StableGraph marks as removed)
    assert!(graph.remove_node(n1).is_none());
}

#[test]
fn test_topological_ordering() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Create path: n1 -> n2 -> n3
    graph.add_edge(n1, n2, ()).unwrap();
    graph.add_edge(n2, n3, ()).unwrap();

    // Get topological order
    let topo_order: Vec<_> = graph.topological_iter().collect();

    // n1 should come before n2, and n2 before n3
    let pos1 = topo_order.iter().position(|&n| n == n1).unwrap();
    let pos2 = topo_order.iter().position(|&n| n == n2).unwrap();
    let pos3 = topo_order.iter().position(|&n| n == n3).unwrap();

    assert!(pos1 < pos2);
    assert!(pos2 < pos3);
}

#[test]
fn test_topological_position_methods() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    graph.add_edge(n1, n2, ()).unwrap();

    // Get positions
    let pos1 = graph.get_position(n1);
    let pos2 = graph.get_position(n2);

    assert!(pos1.is_some());
    assert!(pos2.is_some());

    // Reverse lookup
    assert_eq!(graph.at_position(pos1.unwrap()), Some(n1));
    assert_eq!(graph.at_position(pos2.unwrap()), Some(n2));
}

#[test]
fn test_stable_graph_acyclic() {
    let mut graph = BoundedAcyclicStableDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    // Create edge
    assert!(graph.add_edge(n1, n2, ()).is_ok());

    // Remove first node
    graph.remove_node(n1);

    // Can still add nodes (stable graph maintains indices)
    let n3 = graph.add_node(FixedEdgeCount::empty());
    assert!(graph.add_edge(n2, n3, ()).is_ok());
}

#[test]
fn test_complex_dag_structure() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<10>, ()>::new();

    // Create a more complex DAG
    //      n1
    //     /  \
    //   n2    n3
    //    |  X  |
    //   n4    n5
    //     \  /
    //      n6

    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());
    let n4 = graph.add_node(FixedEdgeCount::empty());
    let n5 = graph.add_node(FixedEdgeCount::empty());
    let n6 = graph.add_node(FixedEdgeCount::empty());

    // Top level
    assert!(graph.add_edge(n1, n2, ()).is_ok());
    assert!(graph.add_edge(n1, n3, ()).is_ok());

    // Middle level (crossing edges)
    assert!(graph.add_edge(n2, n4, ()).is_ok());
    assert!(graph.add_edge(n2, n5, ()).is_ok());
    assert!(graph.add_edge(n3, n4, ()).is_ok());
    assert!(graph.add_edge(n3, n5, ()).is_ok());

    // Bottom level
    assert!(graph.add_edge(n4, n6, ()).is_ok());
    assert!(graph.add_edge(n5, n6, ()).is_ok());

    // All valid edges added
    assert_eq!(graph.edge_count(), 8);

    // Try to create cycle from bottom to top
    assert!(matches!(
        graph.add_edge(n6, n1, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));
}

#[test]
fn test_error_display_messages() {
    use petgraph::acyclic::AcyclicEdgeError;
    use petgraph::graph::NodeIndex;

    let err1 = BoundedAcyclicGraphError::<u32>::Bounded(BoundedGraphError::source_rejected(
        NodeIndex::new(0),
        NodeIndex::new(1),
    ));
    let err2 = BoundedAcyclicGraphError::<u32>::Bounded(BoundedGraphError::target_rejected(
        NodeIndex::new(0),
        NodeIndex::new(1),
    ));
    let err3 = BoundedAcyclicGraphError::<u32>::Bounded(BoundedGraphError::both_rejected(
        NodeIndex::new(0),
        NodeIndex::new(1),
    ));
    let err4 = BoundedAcyclicGraphError::<u32>::Bounded(BoundedGraphError::not_found(
        Some(NodeIndex::new(0)),
        None,
    ));
    let err5 = BoundedAcyclicGraphError::<u32>::Acyclic(AcyclicEdgeError::SelfLoop);

    assert_eq!(err1.to_string(), "source node 0 rejected the outgoing edge");
    assert_eq!(err2.to_string(), "target node 1 rejected the incoming edge");
    assert_eq!(
        err3.to_string(),
        "both nodes rejected the edge (source: 0, target: 1)"
    );
    assert_eq!(err4.to_string(), "source node 0 not found");
    assert_eq!(err5.to_string(), "adding edge would create a self-loop");
}

#[test]
fn test_self_loop_prevention() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<10>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());

    // Self-loop would create a cycle
    assert!(matches!(
        graph.add_edge(n1, n1, ()),
        Err(BoundedAcyclicGraphError::Acyclic(_))
    ));
}

#[test]
fn test_empty_graph() {
    let graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();

    assert_eq!(graph.node_count(), 0);
    assert_eq!(graph.edge_count(), 0);
}

#[test]
fn test_default_construction() {
    let graph: BoundedAcyclicDiGraph<FixedEdgeCount<5>, ()> = Default::default();

    assert_eq!(graph.node_count(), 0);
    assert_eq!(graph.edge_count(), 0);
}

#[test]
fn test_debug_format() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, i32>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    graph.add_edge(n1, n2, 100).unwrap();

    let debug_str = format!("{:?}", graph);
    assert!(debug_str.contains("BoundedAcyclicGraph"));
}

#[test]
fn test_inner_access() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, i32>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let e = graph.add_edge(n1, n2, 42).unwrap();

    // Test inner() - read access
    let inner = graph.inner();
    assert_eq!(*inner.edge_weight(e).unwrap(), 42);
    assert_eq!(inner.node_count(), 2);
    assert_eq!(inner.edge_count(), 1);
}

#[test]
fn test_as_acyclic() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    graph.add_edge(n1, n2, ()).unwrap();

    // Access the underlying Acyclic wrapper
    let acyclic = graph.as_acyclic();
    assert!(acyclic.is_valid_edge(n1, n2));
    assert!(!acyclic.is_valid_edge(n2, n1)); // Would create cycle
}

#[test]
fn test_update_edge_existing_edge() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, String>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    // Add initial edge
    let e1 = graph.add_edge(n1, n2, "original".to_string()).unwrap();
    assert_eq!(graph.edge_count(), 1);

    // Update existing edge - should reuse the same edge
    let e2 = graph.update_edge(n1, n2, "updated".to_string()).unwrap();
    assert_eq!(e1, e2); // Same edge index
    assert_eq!(graph.edge_count(), 1); // Still only one edge

    // Verify weight was updated
    let weight = graph.inner().edge_weight(e2).unwrap();
    assert_eq!(weight, "updated");
}

#[test]
fn test_update_edge_new_edge_violates_acyclic() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, i32>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    // Create edge n1 -> n2
    graph.add_edge(n1, n2, 10).unwrap();

    // Try to update (add) edge n2 -> n1, which would create a cycle
    let result = graph.update_edge(n2, n1, 20);
    assert!(matches!(result, Err(BoundedAcyclicGraphError::Acyclic(_))));
}

#[test]
fn test_add_edge_with_nonexistent_source_node() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());

    // Create an invalid node index
    let invalid = NodeIndex::new(999);

    // Try to add edge with invalid source
    let result = graph.add_edge(invalid, n1, ());
    assert!(matches!(
        result,
        Err(BoundedAcyclicGraphError::Bounded(
            BoundedGraphError::NodeNotFound {
                source: None,
                target: Some(_)
            }
        ))
    ));
}

#[test]
fn test_add_edge_with_nonexistent_target_node() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());

    // Create an invalid node index
    let invalid = NodeIndex::new(999);

    // Try to add edge with invalid target
    let result = graph.add_edge(n1, invalid, ());
    assert!(matches!(
        result,
        Err(BoundedAcyclicGraphError::Bounded(
            BoundedGraphError::NodeNotFound {
                source: Some(_),
                target: None
            }
        ))
    ));
}

#[test]
fn test_can_add_edge_with_invalid_nodes() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());

    let invalid = NodeIndex::new(999);

    // can_add_edge should return false for invalid nodes
    assert!(!graph.can_add_edge(invalid, n1));
    assert!(!graph.can_add_edge(n1, invalid));
    assert!(!graph.can_add_edge(invalid, invalid));
}

#[test]
fn test_topological_methods() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    graph.add_edge(n1, n2, ()).unwrap();
    graph.add_edge(n2, n3, ()).unwrap();

    // Test get_position
    let pos1 = graph.get_position(n1);
    let pos2 = graph.get_position(n2);
    let pos3 = graph.get_position(n3);

    assert!(pos1.is_some());
    assert!(pos2.is_some());
    assert!(pos3.is_some());

    // Test at_position (reverse lookup)
    assert_eq!(graph.at_position(pos1.unwrap()), Some(n1));
    assert_eq!(graph.at_position(pos2.unwrap()), Some(n2));
    assert_eq!(graph.at_position(pos3.unwrap()), Some(n3));
}

#[test]
fn test_clone_graph() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, i32>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    graph.add_edge(n1, n2, 42).unwrap();

    // Clone the graph
    let cloned = graph.clone();

    assert_eq!(graph.node_count(), cloned.node_count());
    assert_eq!(graph.edge_count(), cloned.edge_count());

    // Verify the cloned graph has the same structure
    let edge = cloned
        .inner()
        .find_edge(n1, n2)
        .expect("Edge not found in clone");
    assert_eq!(*cloned.inner().edge_weight(edge).unwrap(), 42);
}

#[test]
fn test_bounded_acyclic_error_variants() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<1>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Fill up n1's outgoing capacity (limit is 1)
    graph.add_edge(n1, n2, ()).unwrap();

    // Try to add another outgoing edge from n1 - should fail with source_rejected
    let result = graph.add_edge(n1, n3, ());
    assert!(matches!(
        result,
        Err(BoundedAcyclicGraphError::Bounded(
            BoundedGraphError::EdgeRejected {
                source_rejected: true,
                target_rejected: false,
                ..
            }
        ))
    ));
}

#[test]
fn test_target_node_full_error() {
    // Use asymmetric bounds: 1 outgoing, 1 incoming
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<1, 1>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    // Fill up n3's incoming capacity (limit is 1)
    graph.add_edge(n1, n3, ()).unwrap();

    // n2 still has outgoing capacity, but n3 is full for incoming
    // Try to add another incoming edge to n3 - should fail with target_rejected
    let result = graph.add_edge(n2, n3, ());
    assert!(
        matches!(
            result,
            Err(BoundedAcyclicGraphError::Bounded(
                BoundedGraphError::EdgeRejected {
                    source_rejected: false,
                    target_rejected: true,
                    ..
                }
            ))
        ),
        "Expected target_rejected, got: {:?}",
        result
    );
}

#[test]
fn test_both_nodes_full_error() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<1, 1>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());
    let n4 = graph.add_node(FixedEdgeCount::empty());

    // Fill up n2's outgoing capacity (limit 1)
    graph.add_edge(n2, n1, ()).unwrap();

    // Fill up n4's incoming capacity (limit 1)
    graph.add_edge(n3, n4, ()).unwrap();

    // Try to add edge from n2 (full outgoing) to n4 (full incoming)
    let result = graph.add_edge(n2, n4, ());
    assert!(matches!(
        result,
        Err(BoundedAcyclicGraphError::Bounded(
            BoundedGraphError::EdgeRejected {
                source_rejected: true,
                target_rejected: true,
                ..
            }
        ))
    ));
}

#[test]
fn test_can_add_edge_with_nonexistent_nodes() {
    let graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = NodeIndex::new(0);
    let n2 = NodeIndex::new(1);

    // Both nodes don't exist
    assert!(!graph.can_add_edge(n1, n2));
}

#[test]
fn test_can_add_edge_returns_false_for_cycle() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    graph.add_edge(n1, n2, ()).unwrap();

    // Check that can_add_edge correctly identifies potential cycle
    assert!(!graph.can_add_edge(n2, n1));
}

#[test]
fn test_can_add_edge_returns_false_when_source_full() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<1>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    graph.add_edge(n1, n2, ()).unwrap();

    // n1 is at capacity
    assert!(!graph.can_add_edge(n1, n3));
}

#[test]
fn test_update_edge_with_nonexistent_edge_adds_it() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, String>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    // Edge doesn't exist yet
    let edge_idx = graph.update_edge(n1, n2, "new edge".to_string()).unwrap();

    assert_eq!(graph.edge_count(), 1);
    assert_eq!(graph.inner().edge_weight(edge_idx).unwrap(), "new edge");
}

#[test]
fn test_update_edge_violating_acyclic_fails() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    graph.add_edge(n1, n2, ()).unwrap();

    // Trying to update an edge that doesn't exist but would create a cycle
    let result = graph.update_edge(n2, n1, ());
    assert!(matches!(result, Err(BoundedAcyclicGraphError::Acyclic(_))));
}

#[test]
fn test_update_edge_violating_bounded_fails() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<1>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    graph.add_edge(n1, n2, ()).unwrap();

    // n1 is at capacity, can't add another edge
    let result = graph.update_edge(n1, n3, ());
    assert!(matches!(
        result,
        Err(BoundedAcyclicGraphError::Bounded(
            BoundedGraphError::EdgeRejected {
                source_rejected: true,
                target_rejected: false,
                ..
            }
        ))
    ));
}

#[test]
fn test_at_position_with_various_positions() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());

    graph.add_edge(n1, n2, ()).unwrap();
    graph.add_edge(n2, n3, ()).unwrap();

    // Get all positions
    let pos1 = graph.get_position(n1).unwrap();
    let pos2 = graph.get_position(n2).unwrap();
    let pos3 = graph.get_position(n3).unwrap();

    // Verify at_position works for all nodes
    assert_eq!(graph.at_position(pos1), Some(n1));
    assert_eq!(graph.at_position(pos2), Some(n2));
    assert_eq!(graph.at_position(pos3), Some(n3));
}

#[test]
fn test_stable_graph_remove_edge_returns_none_for_invalid() {
    let mut graph = BoundedAcyclicStableDiGraph::<FixedEdgeCount<5>, ()>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    let edge = graph.add_edge(n1, n2, ()).unwrap();

    // Remove the edge
    assert!(graph.remove_edge(edge).is_some());

    // Try to remove the same edge again
    assert!(graph.remove_edge(edge).is_none());
}

#[test]
fn test_stable_graph_operations_with_complex_topology() {
    let mut graph = BoundedAcyclicStableDiGraph::<FixedEdgeCount<10>, i32>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());
    let n3 = graph.add_node(FixedEdgeCount::empty());
    let n4 = graph.add_node(FixedEdgeCount::empty());

    // Create diamond pattern
    graph.add_edge(n1, n2, 10).unwrap();
    graph.add_edge(n1, n3, 20).unwrap();
    graph.add_edge(n2, n4, 30).unwrap();
    graph.add_edge(n3, n4, 40).unwrap();

    assert_eq!(graph.node_count(), 4);
    assert_eq!(graph.edge_count(), 4);

    // Remove middle node n2
    graph.remove_node(n2);

    // StableGraph keeps indices stable
    assert_eq!(graph.node_count(), 3);
    assert_eq!(graph.edge_count(), 2); // Lost edges from/to n2

    // Can still work with remaining nodes
    let n5 = graph.add_node(FixedEdgeCount::empty());
    graph.add_edge(n3, n5, 50).unwrap();

    assert_eq!(graph.edge_count(), 3);
}

#[test]
fn test_edge_weight_with_complex_type() {
    #[derive(Debug, Clone, PartialEq)]
    struct ComplexWeight {
        value: i32,
        label: String,
    }

    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ComplexWeight>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    let weight = ComplexWeight {
        value: 42,
        label: "test".to_string(),
    };

    let edge = graph.add_edge(n1, n2, weight.clone()).unwrap();

    assert_eq!(graph.inner().edge_weight(edge).unwrap(), &weight);
}

#[test]
fn test_empty_graph_operations() {
    let graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();

    assert_eq!(graph.node_count(), 0);
    assert_eq!(graph.edge_count(), 0);

    // topological_iter should work on empty graph
    let nodes: Vec<_> = graph.topological_iter().collect();
    assert_eq!(nodes.len(), 0);
}

#[test]
fn test_single_node_graph() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, i32>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());

    assert_eq!(graph.node_count(), 1);
    assert_eq!(graph.edge_count(), 0);

    // Get position of single node
    let pos = graph.get_position(n1);
    assert!(pos.is_some());
    assert_eq!(graph.at_position(pos.unwrap()), Some(n1));
}

#[test]
fn test_multiple_parallel_edges_attempt() {
    let mut graph = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, String>::new();
    let n1 = graph.add_node(FixedEdgeCount::empty());
    let n2 = graph.add_node(FixedEdgeCount::empty());

    // Add first edge
    let e1 = graph.add_edge(n1, n2, "first".to_string()).unwrap();

    // Update_edge with same nodes should update, not add parallel edge
    let e2 = graph.update_edge(n1, n2, "second".to_string()).unwrap();

    // Should be the same edge (updated)
    assert_eq!(e1, e2);
    assert_eq!(graph.edge_count(), 1);
    assert_eq!(graph.inner().edge_weight(e2).unwrap(), "second");
}

#[test]
fn test_try_from_graph_success_dag() {
    use petgraph::Graph;
    use std::convert::TryFrom;

    // Create a valid DAG
    let mut pg = Graph::new();
    let n1 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    let n2 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    let n3 = pg.add_node(FixedEdgeCount::<3, 3>::empty());

    // Build a DAG: n1 -> n2 -> n3
    pg.add_edge(n1, n2, ());
    pg.add_edge(n2, n3, ());

    // Convert should succeed
    let dag = BoundedAcyclicDiGraph::try_from(pg).unwrap();

    assert_eq!(dag.node_count(), 3);
    assert_eq!(dag.edge_count(), 2);
}

#[test]
fn test_try_from_graph_with_cycle() {
    use petgraph::Graph;
    use std::convert::TryFrom;

    // Create a graph with a cycle
    let mut pg = Graph::new();
    let n1 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    let n2 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    let n3 = pg.add_node(FixedEdgeCount::<3, 3>::empty());

    // Build a cycle: n1 -> n2 -> n3 -> n1
    pg.add_edge(n1, n2, ());
    pg.add_edge(n2, n3, ());
    pg.add_edge(n3, n1, ()); // Creates cycle

    // Conversion should fail
    let result = BoundedAcyclicDiGraph::try_from(pg);
    assert!(result.is_err());
    assert!(matches!(
        result.unwrap_err(),
        BoundedAcyclicGraphError::Acyclic(_)
    ));
}

#[test]
fn test_try_from_graph_violates_bounded_constraints() {
    use petgraph::Graph;
    use std::convert::TryFrom;

    // Create a DAG but violates bounded constraints
    let mut pg = Graph::new();
    let n1 = pg.add_node(FixedEdgeCount::<2, 2>::empty()); // Max 2 outgoing
    let n2 = pg.add_node(FixedEdgeCount::<2, 2>::empty());
    let n3 = pg.add_node(FixedEdgeCount::<2, 2>::empty());
    let n4 = pg.add_node(FixedEdgeCount::<2, 2>::empty());

    // Create DAG with too many outgoing edges from n1
    pg.add_edge(n1, n2, ());
    pg.add_edge(n1, n3, ());
    pg.add_edge(n1, n4, ()); // Exceeds capacity

    // Conversion should fail with bounded error
    let result = BoundedAcyclicDiGraph::try_from(pg);
    assert!(result.is_err());
    assert!(matches!(
        result.unwrap_err(),
        BoundedAcyclicGraphError::Bounded(_)
    ));
}

#[test]
fn test_try_from_graph_empty_dag() {
    use petgraph::Graph;
    use std::convert::TryFrom;

    // Empty graph is a valid DAG
    let pg = Graph::<FixedEdgeCount<2, 2>, ()>::new();
    let dag = BoundedAcyclicDiGraph::try_from(pg).unwrap();

    assert_eq!(dag.node_count(), 0);
    assert_eq!(dag.edge_count(), 0);
}

#[test]
fn test_try_from_graph_complex_dag() {
    use petgraph::Graph;
    use std::convert::TryFrom;

    // Create a more complex DAG structure
    let mut pg = Graph::new();
    let n1 = pg.add_node(FixedEdgeCount::<5, 5>::empty());
    let n2 = pg.add_node(FixedEdgeCount::<5, 5>::empty());
    let n3 = pg.add_node(FixedEdgeCount::<5, 5>::empty());
    let n4 = pg.add_node(FixedEdgeCount::<5, 5>::empty());
    let n5 = pg.add_node(FixedEdgeCount::<5, 5>::empty());

    // Diamond shape: n1 -> n2,n3 -> n4, n5
    pg.add_edge(n1, n2, ());
    pg.add_edge(n1, n3, ());
    pg.add_edge(n2, n4, ());
    pg.add_edge(n3, n4, ());
    pg.add_edge(n2, n5, ());

    // Should succeed - it's a DAG
    let dag = BoundedAcyclicDiGraph::try_from(pg).unwrap();
    assert_eq!(dag.edge_count(), 5);
}

#[test]
fn test_try_from_stable_graph_success() {
    use petgraph::stable_graph::StableGraph;
    use std::convert::TryFrom;

    // Create a StableGraph DAG
    let mut pg = StableGraph::new();
    let n1 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    let n2 = pg.add_node(FixedEdgeCount::<3, 3>::empty());

    pg.add_edge(n1, n2, ());

    // Convert to BoundedAcyclicGraph
    let dag = BoundedAcyclicStableDiGraph::try_from(pg).unwrap();

    assert_eq!(dag.node_count(), 2);
    assert_eq!(dag.edge_count(), 1);
}

#[test]
fn test_try_from_stable_graph_with_cycle() {
    use petgraph::stable_graph::StableGraph;
    use std::convert::TryFrom;

    // Create a StableGraph with cycle
    let mut pg = StableGraph::new();
    let n1 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    let n2 = pg.add_node(FixedEdgeCount::<3, 3>::empty());

    pg.add_edge(n1, n2, ());
    pg.add_edge(n2, n1, ()); // Cycle

    // Conversion should fail
    let result = BoundedAcyclicStableDiGraph::try_from(pg);
    assert!(result.is_err());
    assert!(matches!(
        result.unwrap_err(),
        BoundedAcyclicGraphError::Acyclic(_)
    ));
}

#[test]
fn test_try_from_stable_graph_violates_capacity() {
    use petgraph::stable_graph::StableGraph;
    use std::convert::TryFrom;

    // Create StableGraph that violates capacity - all nodes same type
    let mut pg = StableGraph::new();
    let n1 = pg.add_node(FixedEdgeCount::<1, 1>::empty()); // Max 1 outgoing
    let n2 = pg.add_node(FixedEdgeCount::<1, 1>::empty());
    let n3 = pg.add_node(FixedEdgeCount::<1, 1>::empty());

    pg.add_edge(n1, n2, ());
    pg.add_edge(n1, n3, ()); // Exceeds n1's capacity

    // Conversion should fail
    let result = BoundedAcyclicStableDiGraph::try_from(pg);
    assert!(result.is_err());
    assert!(matches!(
        result.unwrap_err(),
        BoundedAcyclicGraphError::Bounded(_)
    ));
}

#[test]
fn test_try_from_preserves_topological_order() {
    use petgraph::Graph;
    use std::convert::TryFrom;

    // Create a linear DAG
    let mut pg = Graph::new();
    let n1 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    let n2 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    let n3 = pg.add_node(FixedEdgeCount::<3, 3>::empty());

    pg.add_edge(n1, n2, ());
    pg.add_edge(n2, n3, ());

    let dag = BoundedAcyclicDiGraph::try_from(pg).unwrap();

    // Collect topological ordering
    let topo_order: Vec<_> = dag.topological_iter().collect();

    // Should have all nodes
    assert_eq!(topo_order.len(), 3);

    // n1 should come before n2 and n3
    let n1_pos = topo_order.iter().position(|&n| n == n1).unwrap();
    let n2_pos = topo_order.iter().position(|&n| n == n2).unwrap();
    let n3_pos = topo_order.iter().position(|&n| n == n3).unwrap();

    assert!(n1_pos < n2_pos);
    assert!(n2_pos < n3_pos);
}

#[test]
fn test_try_from_preserves_node_and_edge_data() {
    use petgraph::Graph;
    use std::convert::TryFrom;

    // Create a DAG with data
    let mut pg = Graph::new();
    let n1 = pg.add_node(FixedEdgeCount::<3, 3, String>::new("Node1".to_string()));
    let n2 = pg.add_node(FixedEdgeCount::<3, 3, String>::new("Node2".to_string()));

    pg.add_edge(n1, n2, "EdgeData");

    let dag = BoundedAcyclicDiGraph::try_from(pg).unwrap();

    // Verify node data
    assert_eq!(dag.inner().node_weight(n1).unwrap().data, "Node1");
    assert_eq!(dag.inner().node_weight(n2).unwrap().data, "Node2");

    // Verify edge data
    let edge = dag.inner().find_edge(n1, n2).unwrap();
    assert_eq!(*dag.inner().edge_weight(edge).unwrap(), "EdgeData");
}

#[test]
fn test_try_from_self_loop_fails() {
    use petgraph::Graph;
    use std::convert::TryFrom;

    // Create graph with self-loop (not a DAG)
    let mut pg = Graph::new();
    let n1 = pg.add_node(FixedEdgeCount::<3, 3>::empty());

    pg.add_edge(n1, n1, ()); // Self-loop

    // Should fail - self-loops create cycles
    let result = BoundedAcyclicDiGraph::try_from(pg);
    assert!(result.is_err());
    assert!(matches!(
        result.unwrap_err(),
        BoundedAcyclicGraphError::Acyclic(_)
    ));
}