gryf 0.2.1

Graph data structure library with focus on convenience, versatility, correctness and performance.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

use rustc_hash::FxHashSet;

use crate::{
    core::{GraphBase, Neighbors, VertexSet, marker::Undirected},
    visit::{Dfs, Visitor},
};

pub fn dfs<G>(graph: &G) -> Vec<Vec<G::VertexId>>
where
    G: GraphBase<EdgeType = Undirected> + Neighbors + VertexSet,
{
    let mut traversal = Dfs::new(graph);
    let mut remaining = graph.vertices_by_id().collect::<FxHashSet<_>>();
    let mut components = Vec::new();

    while let Some(vertex) = remaining.iter().next().cloned() {
        if !remaining.contains(&vertex) {
            continue;
        }

        remaining.remove(&vertex);
        let mut component = vec![vertex.clone()];

        let visitor = traversal.start(vertex);

        for vertex in visitor.into_iter(graph) {
            remaining.remove(&vertex);
            component.push(vertex);
        }

        components.push(component);
    }

    components
}