Function partition_bfs_level 

pub fn partition_bfs_level(
    graph: &SqliteGraph,
    seeds: Vec<i64>,
    k: usize,
) -> Result<PartitionResult, SqliteGraphError>

Partition graph using BFS-level assignment.

Runs multi-source BFS from seed nodes, assigning each node to the partition of the seed that reaches it first (by BFS level). Ties are broken by choosing the partition with the smallest seed ID.

Arguments

• graph - The graph to partition
• seeds - Seed node IDs for each partition (one per partition)
• k - Number of partitions to create

Returns

PartitionResult containing k partitions, cut edges, and node mapping.

Errors

Returns error if graph traversal fails.

Algorithm

1. Initialize k partitions with seed nodes
2. Run multi-source BFS: all seeds in queue at level 0
3. For each node discovered, assign to partition of first seed to reach it
4. Compute cut edges from partition assignments

Complexity

• Time: O(|V| + |E|) - single BFS pass
• Space: O(|V|) for partition assignments and BFS queue

Edge Cases

• Empty seeds: Use first k nodes by ID as seeds
• seeds.len() > k: Use only first k seeds
• seeds.len() < k: Create empty partitions to match k
• Disconnected components: Each component assigned to nearest seed

Example

let graph = SqliteGraph::open_in_memory()?;
// ... build graph ...

// 2-way partition using nodes 1 and 5 as seeds
let result = partition_bfs_level(&graph, vec![1, 5], 2)?;

println!("Partition 0: {:?}, Partition 1: {:?}", result.partitions[0], result.partitions[1]);
println!("Cut edges: {}", result.cut_edges.len());