bounded_graph 0.3.0

//! Bounded acyclic graph implementation.
//!
//! This module provides [`BoundedAcyclicGraph`], which combines both node capacity
//! constraints (from [`BoundedGraph`]) and cycle prevention (from petgraph's [`Acyclic`]).

use std::fmt::{self, Debug, Formatter};
use std::marker::PhantomData;

#[cfg(feature = "serde-1")]
use serde::{Deserialize, Deserializer, Serialize, Serializer};

use petgraph::data::{Build, DataMap, DataMapMut};
use petgraph::visit::{
    Data, EdgeCount, EdgeRef, GraphBase, GraphProp, IntoEdges, IntoEdgesDirected, NodeCount,
};
use petgraph::{
    acyclic::Acyclic,
    graph::{DefaultIx, EdgeIndex, IndexType, NodeIndex},
    stable_graph::StableGraph,
    Directed, Direction, EdgeType, Graph,
};

use crate::{BoundedAcyclicGraphError, BoundedGraph, BoundedGraphError, BoundedNode};

/// A bounded graph that also enforces acyclicity (DAG property).
///
/// `BoundedAcyclicGraph` wraps a [`BoundedGraph`] that uses petgraph's [`Acyclic`]
/// wrapper, providing both node capacity constraints and cycle prevention. All edge
/// additions are checked to ensure they don't violate either constraint.
///
/// # Type Parameters
///
/// * `N` - The node weight type, which must implement [`BoundedNode`]
/// * `E` - The edge weight type
/// * `G` - The underlying graph type (defaults to `Graph<N, E, Directed, DefaultIx>`)
///
/// # Examples
///
/// ```
/// use bounded_graph::{BoundedAcyclicDiGraph, FixedEdgeCount};
///
/// let mut dag = BoundedAcyclicDiGraph::<FixedEdgeCount<5>, ()>::new();
/// let n1 = dag.add_node(FixedEdgeCount::empty());
/// let n2 = dag.add_node(FixedEdgeCount::empty());
/// let n3 = dag.add_node(FixedEdgeCount::empty());
///
/// // Create a path: n1 -> n2 -> n3
/// assert!(dag.add_edge(n1, n2, ()).is_ok());
/// assert!(dag.add_edge(n2, n3, ()).is_ok());
///
/// // This would create a cycle, so it fails
/// assert!(dag.add_edge(n3, n1, ()).is_err());
/// ```
#[derive(Clone)]
pub struct BoundedAcyclicGraph<
    N,
    E,
    G: petgraph::visit::Visitable + GraphBase = Graph<N, E, Directed, DefaultIx>,
> {
    pub(crate) inner: BoundedGraph<N, E, Acyclic<G>>,
    pub(crate) _phantom: PhantomData<(N, E)>,
}

impl<N, E, G> Debug for BoundedAcyclicGraph<N, E, G>
where
    G: petgraph::visit::Visitable + GraphBase + Debug,
    G::NodeId: Debug,
    BoundedGraph<N, E, Acyclic<G>>: Debug,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        f.debug_struct("BoundedAcyclicGraph")
            .field("inner", &self.inner)
            .finish()
    }
}

#[cfg(feature = "serde-1")]
impl<N, E, G> Serialize for BoundedAcyclicGraph<N, E, G>
where
    G: petgraph::visit::Visitable + GraphBase + Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        // Serialize the underlying graph (not the Acyclic wrapper)
        self.inner.graph.inner().serialize(serializer)
    }
}

#[cfg(feature = "serde-1")]
impl<'de, N, E, Ix> Deserialize<'de> for BoundedAcyclicGraph<N, E, Graph<N, E, Directed, Ix>>
where
    Ix: IndexType,
    N: BoundedNode<Ix> + Deserialize<'de>,
    E: Clone + Deserialize<'de>,
    Graph<N, E, Directed, Ix>: Deserialize<'de>,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        let graph = Graph::<N, E, Directed, Ix>::deserialize(deserializer)?;
        // Use TryFrom to create Acyclic - this validates it's acyclic
        let acyclic = Acyclic::try_from(graph)
            .map_err(|_| serde::de::Error::custom("graph contains a cycle"))?;
        Ok(BoundedAcyclicGraph {
            inner: BoundedGraph {
                graph: acyclic,
                _phantom: PhantomData,
            },
            _phantom: PhantomData,
        })
    }
}

#[cfg(feature = "serde-1")]
impl<'de, N, E, Ix> Deserialize<'de> for BoundedAcyclicGraph<N, E, StableGraph<N, E, Directed, Ix>>
where
    Ix: IndexType,
    N: BoundedNode<Ix> + Deserialize<'de>,
    E: Clone + Deserialize<'de>,
    StableGraph<N, E, Directed, Ix>: Deserialize<'de>,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        let graph = StableGraph::<N, E, Directed, Ix>::deserialize(deserializer)?;
        // Use TryFrom to create Acyclic - this validates it's acyclic
        let acyclic = Acyclic::try_from(graph)
            .map_err(|_| serde::de::Error::custom("graph contains a cycle"))?;
        Ok(BoundedAcyclicGraph {
            inner: BoundedGraph {
                graph: acyclic,
                _phantom: PhantomData,
            },
            _phantom: PhantomData,
        })
    }
}

/// A directed bounded acyclic graph using [`Graph`] with default index type.
pub type BoundedAcyclicDiGraph<N, E> = BoundedAcyclicGraph<N, E, Graph<N, E, Directed, DefaultIx>>;

/// A directed bounded acyclic graph using [`StableGraph`] with default index type.
pub type BoundedAcyclicStableDiGraph<N, E> =
    BoundedAcyclicGraph<N, E, StableGraph<N, E, Directed, DefaultIx>>;

impl<N, E, Ty, Ix, G> BoundedAcyclicGraph<N, E, G>
where
    Ty: EdgeType,
    Ix: IndexType,
    N: BoundedNode<Ix>,
    E: Clone,
    G: GraphBase<NodeId = NodeIndex<Ix>, EdgeId = EdgeIndex<Ix>>
        + Data<NodeWeight = N, EdgeWeight = E>
        + GraphProp<EdgeType = Ty>
        + DataMap
        + DataMapMut
        + Build
        + NodeCount
        + EdgeCount
        + petgraph::visit::Visitable
        + petgraph::visit::NodeIndexable,
    for<'a> &'a G: petgraph::visit::IntoNeighborsDirected
        + petgraph::visit::IntoNodeIdentifiers
        + petgraph::visit::IntoEdgesDirected
        + petgraph::visit::IntoEdges
        + GraphBase<NodeId = NodeIndex<Ix>>,
{
    /// Creates a new empty bounded acyclic graph.
    pub fn new() -> Self
    where
        G: Default,
    {
        Self {
            inner: BoundedGraph {
                graph: Acyclic::new(),
                _phantom: PhantomData,
            },
            _phantom: PhantomData,
        }
    }

    /// Checks if an edge can be added between two nodes.
    ///
    /// This checks both:
    /// - Node capacity constraints (via [`BoundedNode::can_add_edge`])
    /// - Acyclicity constraint (would the edge create a cycle?)
    ///
    /// # Arguments
    ///
    /// * `source` - The source node index
    /// * `target` - The target node index
    ///
    /// # Returns
    ///
    /// `true` if both constraints are satisfied, `false` otherwise.
    #[must_use = "checking edge validity is only useful if the result is used"]
    pub fn can_add_edge(&self, source: NodeIndex<Ix>, target: NodeIndex<Ix>) -> bool {
        // Check bounded constraints first
        let (source_weight, target_weight) = match (
            self.inner.graph.node_weight(source),
            self.inner.graph.node_weight(target),
        ) {
            (Some(s), Some(t)) => (s, t),
            _ => return false,
        };

        // Count edges in each direction using inner() to access the underlying graph
        let outgoing_count = self
            .inner
            .graph
            .inner()
            .edges_directed(source, Direction::Outgoing)
            .count();
        let incoming_count = self
            .inner
            .graph
            .inner()
            .edges_directed(target, Direction::Incoming)
            .count();

        let bounded_ok =
            source_weight.can_add_edge(Direction::Outgoing, outgoing_count, target_weight)
                && target_weight.can_add_edge(Direction::Incoming, incoming_count, source_weight);

        // Check acyclic constraint
        let acyclic_ok = self.inner.graph.is_valid_edge(source, target);

        bounded_ok && acyclic_ok
    }

    /// Adds a new node with the given weight to the graph.
    ///
    /// # Returns
    ///
    /// The index of the newly added node.
    #[must_use = "the node index is needed to reference the added node"]
    pub fn add_node(&mut self, node: N) -> NodeIndex<Ix> {
        self.inner.graph.add_node(node)
    }

    /// Adds a new edge from source to target with the given weight.
    ///
    /// This method checks both node capacity constraints and the acyclicity constraint
    /// before adding the edge.
    ///
    /// # Arguments
    ///
    /// * `source` - The source node index
    /// * `target` - The target node index
    /// * `edge` - The edge weight
    ///
    /// # Returns
    ///
    /// * `Ok(EdgeIndex)` - The index of the newly added edge
    /// * `Err(BoundedAcyclicGraphError)` - If the edge cannot be added
    ///
    /// # Errors
    ///
    /// Returns an error if:
    /// - Either node is at capacity ([`BoundedGraphError::EdgeRejected`])
    /// - Either node doesn't exist ([`BoundedGraphError::NodeNotFound`])
    /// - The edge would create a cycle ([`BoundedAcyclicGraphError::Acyclic`])
    #[must_use = "edge addition may fail due to capacity or acyclicity constraints"]
    pub fn add_edge(
        &mut self,
        source: NodeIndex<Ix>,
        target: NodeIndex<Ix>,
        edge: E,
    ) -> Result<EdgeIndex<Ix>, BoundedAcyclicGraphError<Ix>> {
        // First check bounded constraints (capacity)
        // Get node weights - return NodeNotFound if either doesn't exist
        let (source_weight, target_weight) = match (
            self.inner.graph.node_weight(source),
            self.inner.graph.node_weight(target),
        ) {
            (Some(s), Some(t)) => (s, t),
            (None, None) => return Err(BoundedGraphError::not_found(None, None).into()),
            (None, Some(_)) => return Err(BoundedGraphError::not_found(None, Some(target)).into()),
            (Some(_), None) => return Err(BoundedGraphError::not_found(Some(source), None).into()),
        };

        // Count edges in each direction using inner() to access the underlying graph
        let outgoing_count = self
            .inner
            .graph
            .inner()
            .edges_directed(source, Direction::Outgoing)
            .count();
        let incoming_count = self
            .inner
            .graph
            .inner()
            .edges_directed(target, Direction::Incoming)
            .count();

        // Check capacity for both nodes
        let source_has_space =
            source_weight.can_add_edge(Direction::Outgoing, outgoing_count, target_weight);
        let target_has_space =
            target_weight.can_add_edge(Direction::Incoming, incoming_count, source_weight);

        // Check bounded constraints first (early return if capacity issue)
        match (source_has_space, target_has_space) {
            (false, true) => return Err(BoundedGraphError::source_rejected(source, target).into()),
            (true, false) => return Err(BoundedGraphError::target_rejected(source, target).into()),
            (false, false) => return Err(BoundedGraphError::both_rejected(source, target).into()),
            (true, true) => {} // Continue to acyclic check
        }

        // Now check acyclic constraint using try_add_edge
        self.inner
            .graph
            .try_add_edge(source, target, edge)
            .map_err(Into::into)
    }

    /// Updates the edge from source to target with the given weight, or adds it if it doesn't exist.
    ///
    /// If an edge already exists, its weight is updated. Otherwise, this method attempts
    /// to add a new edge, respecting both bounded and acyclic constraints.
    ///
    /// # Returns
    ///
    /// * `Ok(EdgeIndex)` - The index of the updated or newly added edge
    /// * `Err(BoundedAcyclicGraphError)` - If adding a new edge would violate constraints
    #[must_use = "edge update may fail due to capacity or acyclicity constraints"]
    pub fn update_edge(
        &mut self,
        source: NodeIndex<Ix>,
        target: NodeIndex<Ix>,
        weight: E,
    ) -> Result<EdgeIndex<Ix>, BoundedAcyclicGraphError<Ix>> {
        // Check if edge already exists using inner() to access the underlying graph
        let edge_exists = self
            .inner
            .graph
            .inner()
            .edges(source)
            .any(|e| e.target() == target);

        if edge_exists {
            // Edge exists - try_update_edge on Acyclic won't create cycles
            self.inner
                .graph
                .try_update_edge(source, target, weight)
                .map_err(Into::into)
        } else {
            // Edge doesn't exist, use add_edge which checks all constraints
            self.add_edge(source, target, weight)
        }
    }

    /// Returns a reference to the inner [`BoundedGraph`].
    #[must_use]
    pub fn inner(&self) -> &BoundedGraph<N, E, Acyclic<G>> {
        &self.inner
    }

    /// Returns a reference to the underlying petgraph [`Acyclic`] wrapper.
    #[must_use]
    pub fn as_acyclic(&self) -> &Acyclic<G> {
        &self.inner.graph
    }

    /// Get an iterator over the nodes in topological order.
    ///
    /// This iterator yields nodes in an order such that for every edge from node A to node B,
    /// A appears before B in the iteration.
    #[must_use = "iterators are lazy and do nothing unless consumed"]
    pub fn topological_iter(&self) -> impl Iterator<Item = NodeIndex<Ix>> + '_ {
        self.inner.graph.nodes_iter()
    }

    /// Get the topological position of a node.
    ///
    /// The topological position represents the node's position in the topological ordering
    /// maintained by the acyclic graph.
    #[must_use]
    pub fn get_position(
        &self,
        node: NodeIndex<Ix>,
    ) -> Option<petgraph::acyclic::TopologicalPosition> {
        Some(self.inner.graph.get_position(node))
    }

    /// Get the node at a specific topological position.
    #[must_use]
    pub fn at_position(
        &self,
        pos: petgraph::acyclic::TopologicalPosition,
    ) -> Option<NodeIndex<Ix>> {
        self.inner.graph.at_position(pos)
    }

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

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

// Separate impl block for inner_mut() that requires ImmutableEdgeBounds
impl<N, E, Ty, Ix, G> BoundedAcyclicGraph<N, E, G>
where
    Ty: EdgeType,
    Ix: IndexType,
    N: BoundedNode<Ix> + crate::ImmutableEdgeBounds,
    E: Clone,
    G: GraphBase<NodeId = NodeIndex<Ix>, EdgeId = EdgeIndex<Ix>>
        + Data<NodeWeight = N, EdgeWeight = E>
        + GraphProp<EdgeType = Ty>
        + DataMap
        + DataMapMut
        + Build
        + NodeCount
        + EdgeCount
        + petgraph::visit::Visitable
        + petgraph::visit::NodeIndexable,
    for<'a> &'a G: petgraph::visit::IntoNeighborsDirected
        + petgraph::visit::IntoNodeIdentifiers
        + petgraph::visit::IntoEdgesDirected
        + petgraph::visit::IntoEdges
        + GraphBase<NodeId = NodeIndex<Ix>>,
{
    /// Returns a mutable reference to the inner [`BoundedGraph`].
    ///
    /// This method is only available for node types with [`ImmutableEdgeBounds`](crate::ImmutableEdgeBounds)
    /// to prevent mutations that could violate edge bound constraints.
    ///
    /// # Safety
    ///
    /// Direct manipulation of the inner graph can violate the acyclic invariant.
    /// Use with caution.
    pub fn inner_mut(&mut self) -> &mut BoundedGraph<N, E, Acyclic<G>> {
        &mut self.inner
    }
}

// Concrete implementations for remove operations for Graph
impl<N, E, Ix> BoundedAcyclicGraph<N, E, Graph<N, E, Directed, Ix>>
where
    N: BoundedNode,
    Ix: IndexType,
{
    /// Removes an edge from the graph.
    ///
    /// Returns the edge weight if the edge existed, or `None` if it didn't.
    ///
    /// This operation updates the internal topological ordering in O(v) time.
    pub fn remove_edge(&mut self, edge: EdgeIndex<Ix>) -> Option<E> {
        self.inner.graph.remove_edge(edge)
    }

    /// Removes a node from the graph.
    ///
    /// Returns the node weight if the node existed, or `None` if it didn't.
    /// All edges connected to the node are also removed.
    ///
    /// This operation updates the internal topological ordering in O(v) time.
    pub fn remove_node(&mut self, node: NodeIndex<Ix>) -> Option<N> {
        self.inner.graph.remove_node(node)
    }
}

// Concrete implementations for remove operations for StableGraph
impl<N, E, Ix> BoundedAcyclicGraph<N, E, StableGraph<N, E, Directed, Ix>>
where
    N: BoundedNode,
    Ix: IndexType,
{
    /// Removes an edge from the graph.
    ///
    /// Returns the edge weight if the edge existed, or `None` if it didn't.
    ///
    /// This operation updates the internal topological ordering in O(v) time.
    pub fn remove_edge(&mut self, edge: EdgeIndex<Ix>) -> Option<E> {
        self.inner.graph.remove_edge(edge)
    }

    /// Removes a node from the graph.
    ///
    /// Returns the node weight if the node existed, or `None` if it didn't.
    /// All edges connected to the node are also removed.
    ///
    /// This operation updates the internal topological ordering in O(v) time.
    pub fn remove_node(&mut self, node: NodeIndex<Ix>) -> Option<N> {
        self.inner.graph.remove_node(node)
    }
}

impl<N, E, Ty, Ix, G> Default for BoundedAcyclicGraph<N, E, G>
where
    Ty: EdgeType,
    Ix: IndexType,
    N: BoundedNode<Ix>,
    E: Clone,
    G: GraphBase<NodeId = NodeIndex<Ix>, EdgeId = EdgeIndex<Ix>>
        + Data<NodeWeight = N, EdgeWeight = E>
        + GraphProp<EdgeType = Ty>
        + DataMap
        + DataMapMut
        + Build
        + NodeCount
        + EdgeCount
        + petgraph::visit::Visitable
        + petgraph::visit::NodeIndexable
        + Default,
    for<'a> &'a G: petgraph::visit::IntoNeighborsDirected
        + petgraph::visit::IntoNodeIdentifiers
        + petgraph::visit::IntoEdgesDirected
        + petgraph::visit::IntoEdges
        + GraphBase<NodeId = NodeIndex<Ix>>,
{
    fn default() -> Self {
        Self::new()
    }
}

// TryFrom implementation for Graph
impl<N, E, Ix> TryFrom<Graph<N, E, Directed, Ix>>
    for BoundedAcyclicGraph<N, E, Graph<N, E, Directed, Ix>>
where
    Ix: IndexType,
    N: BoundedNode<Ix>,
    E: Clone,
{
    type Error = BoundedAcyclicGraphError<Ix>;

    /// Attempts to create a bounded acyclic graph from an existing petgraph Graph.
    ///
    /// This validates that:
    /// 1. The graph is acyclic (contains no cycles)
    /// 2. All existing edges respect the node capacity constraints
    ///
    /// # Examples
    ///
    /// ```
    /// use petgraph::Graph;
    /// use bounded_graph::{BoundedAcyclicGraph, FixedEdgeCount};
    /// use std::convert::TryFrom;
    ///
    /// 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());
    ///
    /// // Create a DAG: n1 -> n2 -> n3
    /// pg.add_edge(n1, n2, ());
    /// pg.add_edge(n2, n3, ());
    ///
    /// // This succeeds - graph is acyclic and respects bounds
    /// let bounded_dag = BoundedAcyclicGraph::try_from(pg).unwrap();
    /// ```
    ///
    /// # Errors
    ///
    /// Returns an error if:
    /// - The graph contains a cycle ([`BoundedAcyclicGraphError::Acyclic`])
    /// - Any edge violates node capacity constraints ([`BoundedAcyclicGraphError::Bounded`])
    fn try_from(graph: Graph<N, E, Directed, Ix>) -> Result<Self, Self::Error> {
        // First validate bounded constraints
        for node in graph.node_indices() {
            let node_weight = graph
                .node_weight(node)
                .ok_or_else(|| BoundedGraphError::not_found(Some(node), None))?;

            // Count outgoing edges
            let outgoing_count = graph.edges_directed(node, Direction::Outgoing).count();

            // Count incoming edges
            let incoming_count = graph.edges_directed(node, Direction::Incoming).count();

            // Check outgoing capacity
            for edge in graph.edges_directed(node, Direction::Outgoing) {
                let target = edge.target();
                let target_weight = graph
                    .node_weight(target)
                    .ok_or_else(|| BoundedGraphError::not_found(None, Some(target)))?;

                if !node_weight.can_add_edge(Direction::Outgoing, outgoing_count - 1, target_weight)
                {
                    return Err(BoundedGraphError::source_rejected(node, target).into());
                }
            }

            // Check incoming capacity
            for edge in graph.edges_directed(node, Direction::Incoming) {
                let source = edge.source();
                let source_weight = graph
                    .node_weight(source)
                    .ok_or_else(|| BoundedGraphError::not_found(Some(source), None))?;

                if !node_weight.can_add_edge(Direction::Incoming, incoming_count - 1, source_weight)
                {
                    return Err(BoundedGraphError::target_rejected(source, node).into());
                }
            }
        }

        // Now validate acyclicity - try to convert to Acyclic
        let acyclic = Acyclic::try_from(graph).map_err(|_| {
            // The error from try_from for Acyclic is the graph itself if it has cycles
            // We need to return an appropriate error
            use petgraph::acyclic::AcyclicEdgeError;
            BoundedAcyclicGraphError::Acyclic(AcyclicEdgeError::InvalidEdge)
        })?;

        Ok(BoundedAcyclicGraph {
            inner: crate::BoundedGraph {
                graph: acyclic,
                _phantom: PhantomData,
            },
            _phantom: PhantomData,
        })
    }
}

// TryFrom implementation for StableGraph
impl<N, E, Ix> TryFrom<StableGraph<N, E, Directed, Ix>>
    for BoundedAcyclicGraph<N, E, StableGraph<N, E, Directed, Ix>>
where
    Ix: IndexType,
    N: BoundedNode<Ix>,
    E: Clone,
{
    type Error = BoundedAcyclicGraphError<Ix>;

    /// Attempts to create a bounded acyclic graph from an existing petgraph StableGraph.
    ///
    /// This validates that:
    /// 1. The graph is acyclic (contains no cycles)
    /// 2. All existing edges respect the node capacity constraints
    ///
    /// # Examples
    ///
    /// ```
    /// use petgraph::stable_graph::StableGraph;
    /// use bounded_graph::{BoundedAcyclicGraph, FixedEdgeCount};
    /// use std::convert::TryFrom;
    ///
    /// let mut pg = StableGraph::new();
    /// let n1 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    /// let n2 = pg.add_node(FixedEdgeCount::<3, 3>::empty());
    ///
    /// // Create a DAG: n1 -> n2
    /// pg.add_edge(n1, n2, ());
    ///
    /// // This succeeds - graph is acyclic and respects bounds
    /// let bounded_dag = BoundedAcyclicGraph::try_from(pg).unwrap();
    /// ```
    ///
    /// # Errors
    ///
    /// Returns an error if:
    /// - The graph contains a cycle ([`BoundedAcyclicGraphError::Acyclic`])
    /// - Any edge violates node capacity constraints ([`BoundedAcyclicGraphError::Bounded`])
    fn try_from(graph: StableGraph<N, E, Directed, Ix>) -> Result<Self, Self::Error> {
        // First validate bounded constraints
        for node in graph.node_indices() {
            let node_weight = graph
                .node_weight(node)
                .ok_or_else(|| BoundedGraphError::not_found(Some(node), None))?;

            // Count outgoing edges
            let outgoing_count = graph.edges_directed(node, Direction::Outgoing).count();

            // Count incoming edges
            let incoming_count = graph.edges_directed(node, Direction::Incoming).count();

            // Check outgoing capacity
            for edge in graph.edges_directed(node, Direction::Outgoing) {
                let target = edge.target();
                let target_weight = graph
                    .node_weight(target)
                    .ok_or_else(|| BoundedGraphError::not_found(None, Some(target)))?;

                if !node_weight.can_add_edge(Direction::Outgoing, outgoing_count - 1, target_weight)
                {
                    return Err(BoundedGraphError::source_rejected(node, target).into());
                }
            }

            // Check incoming capacity
            for edge in graph.edges_directed(node, Direction::Incoming) {
                let source = edge.source();
                let source_weight = graph
                    .node_weight(source)
                    .ok_or_else(|| BoundedGraphError::not_found(Some(source), None))?;

                if !node_weight.can_add_edge(Direction::Incoming, incoming_count - 1, source_weight)
                {
                    return Err(BoundedGraphError::target_rejected(source, node).into());
                }
            }
        }

        // Now validate acyclicity - try to convert to Acyclic
        let acyclic = Acyclic::try_from(graph).map_err(|_| {
            use petgraph::acyclic::AcyclicEdgeError;
            BoundedAcyclicGraphError::Acyclic(AcyclicEdgeError::InvalidEdge)
        })?;

        Ok(BoundedAcyclicGraph {
            inner: crate::BoundedGraph {
                graph: acyclic,
                _phantom: PhantomData,
            },
            _phantom: PhantomData,
        })
    }
}