Function kahns

pub fn kahns<'a, G, NI, D, M>(
    graph: &G,
    queue: D,
    in_degree_map: M,
    sorted_nodes: &'a mut [NI],
) -> Result<&'a [NI], AlgorithmError<NI>>
where
    G: Graph<NI>,
    NI: NodeIndex,
    D: Deque<NI>,
    M: MapTrait<NI, isize>,
    AlgorithmError<NI>: From<G::Error>,

Kahn’s algorithm for topological sorting

Performs a topological sort on a directed graph using Kahn’s algorithm (BFS-based). This algorithm tracks in-degrees of nodes and processes nodes with zero in-degree. It detects cycles and returns an error if the graph is not a DAG.

Arguments

• graph - The graph to sort topologically (must implement Graph)
• queue - Queue for BFS processing (nodes with zero in-degree)
• in_degree_map - Map to track in-degree count for each node
• sorted_nodes - Buffer to store the topologically sorted nodes

Returns

• Ok(&[NI]) slice of sorted nodes if successful
• Err(AlgorithmError::CycleDetected) if a cycle is found
• Err(AlgorithmError::QueueCapacityExceeded) if queue capacity exceeded
• Err(AlgorithmError::ResultCapacityExceeded) if result buffer is full

Time Complexity

O(V + E) where V is the number of vertices and E is the number of edges. For matrix-based graphs with optimized incoming_edges, the in-degree calculation is O(V) instead of O(V + E).