Skip to main content

connected_components

sqlitegraph::algo

Function connected_components 

Source 
pub fn connected_components(
    graph: &SqliteGraph,
) -> Result<Vec<Vec<i64>>, SqliteGraphError>
Expand description

Finds all connected components in the graph using BFS.

A connected component is a maximal subgraph where any two nodes are connected by a path. This function uses bidirectional BFS (both incoming and outgoing edges).

§Arguments

  • graph - The graph to analyze

§Returns

Vector of components, where each component is a sorted vector of node IDs. Components are sorted by their smallest node ID.

§Complexity

Time: O(|V| + |E|) - visits each node and edge once Space: O(|V|) for visited set and BFS queue

§Example

use sqlitegraph::{SqliteGraph, algo::connected_components};
let graph = SqliteGraph::open_in_memory()?;
// ... add nodes and edges ...
let components = connected_components(&graph)?;