Struct prepona::algo::ConnectedComponents

pub struct ConnectedComponents { /* fields omitted */ }

Finds connected components of an undirected graph.

Examples

use prepona::prelude::*;
use prepona::storage::Mat;
use prepona::graph::MatGraph;
use prepona::algo::ConnectedComponents;

//      a  ---  b  ---  d               g
//      |      /
//      c ___/              e  --- f
let mut graph = MatGraph::init(Mat::<usize>::init());
let a = graph.add_vertex();
let b = graph.add_vertex();
let c = graph.add_vertex();
let d = graph.add_vertex();
let e = graph.add_vertex();
let f = graph.add_vertex();
let g = graph.add_vertex();

graph.add_edge_unchecked(a, b, 1.into());
graph.add_edge_unchecked(a, c, 1.into());
graph.add_edge_unchecked(c, b, 1.into());
graph.add_edge_unchecked(b, d, 1.into());
graph.add_edge_unchecked(e, f, 1.into());

let ccs = ConnectedComponents::init(&graph).execute(&graph);

for cc in ccs {
    match cc.len() {
        1 => assert!(cc.contains(&g)),
        2 => assert!(vec![e, f].iter().all(|v_id| cc.contains(v_id))),
        4 => assert!(vec![a, b, c, d].iter().all(|v_id| cc.contains(v_id))),
        _ => panic!("Unknown component: {:?}", cc),
    }
}

Implementations

impl ConnectedComponents

pub fn init<G, W, E: Edge<W>>(_: &G) -> Self where
    G: Graph<W, E, UndirectedEdge> + Vertices + Neighbors, 

Initializes the structure.

pub fn execute<G, W, E: Edge<W>>(self, graph: &G) -> Vec<Vec<usize>> where
    G: Graph<W, E, UndirectedEdge> + Vertices + Neighbors, 

Finds connected components of an undirected graph.

Arguments

graph: Graph to search for its connected components.

Returns

Connected components of the graph.
Returned value will be vector of vectors. Each vector contains ids of vertices that are in a component.

Trait Implementations

impl DfsListener<ConnectedComponents> for ConnectedComponents

fn on_white(&mut self, dfs: &Dfs<'_, Self>, virt_id: usize)

Gets called by Dfs when visiting a vertex for the first time. This function may called multiple times because graph may not be connected.

fn on_finish(&mut self, _: &Dfs<'_, Self>)

Gets called by Dfs when finishing the algorithm. This function may called multiple times because graph may not be connected.

fn on_start(&mut self, dfs: &Dfs<'_, L>, virt_id: usize)

Gets called by Dfs when starting the algorithm. This function may called multiple times because graph may not be connected.

fn on_gray(&mut self, dfs: &Dfs<'_, L>, virt_id: usize)

Gets called by Dfs when visiting a vertex that has been on the stack(it’s now on top of the stack). This function may called multiple times because graph may not be connected.

fn on_black(&mut self, dfs: &Dfs<'_, L>, virt_id: usize)

Gets called by Dfs when a vertex is permanently visited(removed from the stack). This function may called multiple times because graph may not be connected.