Function topological_sort 

pub fn topological_sort(graph: &SqliteGraph) -> Result<Vec<i64>, TopoError>

Computes topological ordering of nodes in a directed graph.

Topological sort produces a linear ordering of nodes such that for every directed edge (u, v), node u appears before node v in the ordering. This is only possible for directed acyclic graphs (DAGs).

Arguments

• graph - The graph to sort

Returns

Ok(Vec<NodeId>) containing nodes in topological order, or Err(TopoError) if the graph contains cycles.

Algorithm

Two-phase approach:

1. Cycle detection - Use SCC decomposition to find non-trivial SCCs (cycles)
2. Kahn’s algorithm - For DAGs, process nodes with zero in-degree

Cycle Detection

Uses strongly_connected_components from plan 45-02:

• Non-trivial SCCs (components with >1 node) indicate cycles
• Extracts actual cycle path for debugging
• Returns helpful error message with cycle details

Kahn’s Algorithm

For valid DAGs:

1. Compute in-degree for all nodes
2. Add nodes with zero in-degree to queue
3. Repeatedly remove node from queue, add to result, decrement neighbors’ in-degrees
4. Add new zero in-degree nodes to queue
5. Return result when all nodes processed

Complexity

• Time: O(|V| + |E|)
• Space: O(|V|) for in-degree map and queue

Edge Cases

• Empty graph: Returns empty Vec
• Single node: Returns [node_id]
• Disconnected graph: Still produces valid topological order
• Graph with cycle: Returns CycleDetected error with cycle path

Example

use sqlitegraph::{SqliteGraph, algo::topological_sort};

let graph = SqliteGraph::open_in_memory()?;
// ... add nodes and edges forming a DAG ...

let ordering = topological_sort(&graph)?;
// Verify: for every edge (u, v), u appears before v in ordering

Errors

Returns TopoError::CycleDetected if the graph contains cycles. The error includes the cycle path and explanation for debugging.