pub struct ConnectedComponents;Expand description
Connected Components algorithm implementations.
Implementations§
Source§impl ConnectedComponents
impl ConnectedComponents
Sourcepub fn weakly_connected<T: Transaction>(
tx: &T,
config: &ConnectedComponentsConfig,
) -> GraphResult<ComponentResult>
pub fn weakly_connected<T: Transaction>( tx: &T, config: &ConnectedComponentsConfig, ) -> GraphResult<ComponentResult>
Compute weakly connected components.
This treats the graph as undirected - two nodes are in the same weakly connected component if there’s a path between them ignoring edge direction.
Uses Union-Find with path compression for O(V + E * α(V)) time complexity, where α is the inverse Ackermann function (effectively constant).
§Arguments
tx- The transaction to use for graph accessconfig- Configuration parameters for the algorithm
§Returns
A ComponentResult containing component assignments for all nodes.
Sourcepub fn strongly_connected<T: Transaction>(
tx: &T,
config: &ConnectedComponentsConfig,
) -> GraphResult<ComponentResult>
pub fn strongly_connected<T: Transaction>( tx: &T, config: &ConnectedComponentsConfig, ) -> GraphResult<ComponentResult>
Compute strongly connected components using Tarjan’s algorithm.
In a strongly connected component, every node is reachable from every other node following edge directions. This is a stricter property than weak connectivity.
Uses Tarjan’s algorithm for O(V + E) time complexity.
§Arguments
tx- The transaction to use for graph accessconfig- Configuration parameters for the algorithm
§Returns
A ComponentResult containing component assignments for all nodes.
Sourcepub fn weakly_connected_for_nodes<T: Transaction>(
tx: &T,
nodes: &[EntityId],
config: &ConnectedComponentsConfig,
) -> GraphResult<ComponentResult>
pub fn weakly_connected_for_nodes<T: Transaction>( tx: &T, nodes: &[EntityId], config: &ConnectedComponentsConfig, ) -> GraphResult<ComponentResult>
Compute weakly connected components for a subset of nodes.
Only considers edges within the specified subgraph.
§Arguments
tx- The transaction to use for graph accessnodes- The nodes to include in the computationconfig- Configuration parameters for the algorithm
Sourcepub fn strongly_connected_for_nodes<T: Transaction>(
tx: &T,
nodes: &[EntityId],
config: &ConnectedComponentsConfig,
) -> GraphResult<ComponentResult>
pub fn strongly_connected_for_nodes<T: Transaction>( tx: &T, nodes: &[EntityId], config: &ConnectedComponentsConfig, ) -> GraphResult<ComponentResult>
Compute strongly connected components for a subset of nodes.
Only considers edges within the specified subgraph.
§Arguments
tx- The transaction to use for graph accessnodes- The nodes to include in the computationconfig- Configuration parameters for the algorithm