graphrs/algorithms/components/
connectivity.rs

1use crate::{ext::vec::VecExt, Error, Graph};
2use std::collections::HashSet;
3use std::fmt::Display;
4use std::hash::Hash;
5
6/**
7Returns the components of a graph.
8A connected component is a maximal connected subgraph of an undirected graph.
9
10# Arguments:
11
12* `graph`: a [Graph](../../struct.Graph.html) instance that must be undirected.
13
14# Examples:
15
16```
17use graphrs::{Edge, Graph, GraphSpecs};
18use graphrs::{algorithms::components};
19let edges = vec![
20    Edge::new("n1", "n2"),
21    Edge::new("n2", "n3"),
22    Edge::new("n3", "n4"),
23    Edge::new("o1", "o2"),
24    Edge::new("p1", "p2"),
25    Edge::new("p2", "p3"),
26];
27let specs = GraphSpecs::undirected_create_missing();
28let graph: Graph<&str, ()> = Graph::new_from_nodes_and_edges(vec![], edges, specs).unwrap();
29let result = components::connected_components(&graph).unwrap();
30assert_eq!(result.len(), 3);
31```
32*/
33pub fn connected_components<T, A>(graph: &Graph<T, A>) -> Result<Vec<HashSet<T>>, Error>
34where
35    T: Hash + Eq + Clone + Ord + Display + Send + Sync,
36    A: Clone + Send + Sync,
37{
38    graph.ensure_undirected()?;
39    let mut seen = HashSet::new();
40    let mut return_vec = vec![];
41    for v in graph.get_all_node_names() {
42        if !seen.contains(v) {
43            let bfs = graph.breadth_first_search(&v).to_hashset();
44            seen = seen.union(&bfs).cloned().collect();
45            return_vec.push(bfs);
46        }
47    }
48    Ok(return_vec)
49}
50
51/**
52Returns the number of components in a graph.
53A connected component is a maximal connected subgraph of an undirected graph.
54
55# Arguments:
56
57* `graph`: a [Graph](../../struct.Graph.html) instance that must be undirected.
58
59# Examples:
60
61```
62use graphrs::{Edge, Graph, GraphSpecs};
63use graphrs::{algorithms::components};
64let edges = vec![
65    Edge::new("n1", "n2"),
66    Edge::new("n2", "n3"),
67    Edge::new("n3", "n4"),
68    Edge::new("o1", "o2"),
69    Edge::new("p1", "p2"),
70    Edge::new("p2", "p3"),
71];
72let specs = GraphSpecs::undirected_create_missing();
73let graph: Graph<&str, ()> = Graph::new_from_nodes_and_edges(vec![], edges, specs).unwrap();
74let result = components::number_of_connected_components(&graph).unwrap();
75assert_eq!(result, 3);
76```
77*/
78pub fn number_of_connected_components<T, A>(graph: &Graph<T, A>) -> Result<usize, Error>
79where
80    T: Hash + Eq + Clone + Ord + Display + Send + Sync,
81    A: Clone + Send + Sync,
82{
83    let result = connected_components(graph)?;
84    Ok(result.len())
85}
86
87/**
88Returns the set of nodes in the component of a graph containing a given node.
89
90# Arguments:
91
92* `graph`: a [Graph](../../struct.Graph.html) instance that must be undirected.
93* `node_name`: the node whose component is to be returned.
94
95# Examples:
96
97```
98use graphrs::{Edge, Graph, GraphSpecs};
99use graphrs::{algorithms::components};
100let edges = vec![
101    Edge::new("n1", "n2"),
102    Edge::new("n2", "n3"),
103    Edge::new("n3", "n4"),
104    Edge::new("o1", "o2"),
105    Edge::new("p1", "p2"),
106    Edge::new("p2", "p3"),
107];
108let specs = GraphSpecs::undirected_create_missing();
109let graph: Graph<&str, ()> = Graph::new_from_nodes_and_edges(vec![], edges, specs).unwrap();
110let result = components::node_connected_component(&graph, &"n2").unwrap();
111assert_eq!(result.len(), 4);
112```
113*/
114pub fn node_connected_component<T, A>(
115    graph: &Graph<T, A>,
116    node_name: &T,
117) -> Result<HashSet<T>, Error>
118where
119    T: Hash + Eq + Clone + Ord + Display + Send + Sync,
120    A: Clone + Send + Sync,
121{
122    graph.ensure_undirected()?;
123    let bfs = graph.breadth_first_search(node_name);
124    Ok(bfs.to_hashset())
125}
graphrs/algorithms/components/connectivity.rs

graphrs/algorithms/components/
connectivity.rs
