Function partition_kway 

pub fn partition_kway(
    graph: &SqliteGraph,
    config: &PartitionConfig,
) -> Result<PartitionResult, SqliteGraphError>

Partition graph into k balanced partitions using BFS growth from seeds.

Creates k partitions by growing them from seed nodes using BFS while respecting size bounds. Unassigned nodes are assigned to their nearest partition by shortest path distance.

Arguments

• graph - The graph to partition
• config - Partitioning configuration (k, max_size, max_imbalance, seeds)

Returns

PartitionResult containing k balanced partitions.

Errors

• Returns SqliteGraphError::InvalidInput if config.k < 2

Algorithm

1. Validate config.k >= 2
2. Select seeds: use config.seeds or select k nodes by highest degree
3. Grow partitions using BFS while respecting max_size
4. For unassigned nodes: assign to nearest partition (shortest path)
5. Compute cut edges

Complexity

• Time: O(|V| + |E|) for single pass with size checks
• Space: O(|V| + k) for partition assignments

Example

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

// 4-way partition with size bounds
let config = PartitionConfig {
    k: 4,
    max_size: 100,
    max_imbalance: 0.1,
    seeds: None,
};
let result = partition_kway(&graph, &config)?;

for (i, partition) in result.partitions.iter().enumerate() {
    println!("Partition {}: {} nodes", i, partition.len());
}