algods/graph/processing/
connection.rs

1use crate::graph::processing::dfs;
2use crate::graph::processing::TopologicalSort;
3use crate::graph::{DirectedGraph, UndirectedGraph};
4pub struct ConnectedComponent {
5    // Aims at answering the question are two vertives v and w connected in contant time
6    // after preprocessing the graph
7    // Identifier of the connected commponent vertices belong to
8    id: Vec<usize>,
9    // Indicates wether or not a vertex w in the graph is visited
10    marked: Vec<bool>,
11    // Number of connected components
12    nb_cc: usize,
13    // Whether or not the algorithm has run
14    ran: bool,
15}
16impl ConnectedComponent {
17    pub fn init(nb_vertices: usize) -> Self {
18        Self {
19            marked: vec![false; nb_vertices],
20            id: (0..nb_vertices).collect::<Vec<usize>>(),
21            nb_cc: 0,
22            ran: false,
23        }
24    }
25    pub fn find_cc(&mut self, graph: &UndirectedGraph) {
26        // builds all the connected components from a graph
27        let nb = graph.nb_vertices();
28        for v in 0..nb {
29            if !self.marked[v] {
30                // run DFS for each vertex in each component
31                dfs(graph, &mut self.marked, &mut self.id, v, v, true, true);
32                // here the connected component v is built
33                self.nb_cc += 1;
34            }
35        }
36        self.ran = true;
37    }
38    pub fn connected(&self, v: usize, w: usize) -> Option<bool> {
39        // finds out whether or not two vertices are connected
40        // run time complexity O(1)
41        if !self.marked[v] || !self.marked[w] {
42            return None;
43        }
44        Some(self.id[v] == self.id[w])
45    }
46    pub fn count(&self) -> usize {
47        self.nb_cc
48    }
49    pub fn is_bipartite(&self) -> Option<bool> {
50        if self.ran {
51            Some(self.nb_cc == 1)
52        } else {
53            None
54        }
55    }
56}
57
58pub struct StrongConnectedComponent {
59    // Aims at answering the question are two vertives v and w connected in contant time
60    // after preprocessing a directed graph
61    // Identifier of the strong connected commponents vertices belong to
62    id: Vec<usize>,
63    // Indicates wether or not a vertex w in the graph is visited
64    marked: Vec<bool>,
65    // Number of strong connected components
66    nb_scc: usize,
67}
68impl StrongConnectedComponent {
69    pub fn init(nb_vertices: usize) -> Self {
70        Self {
71            marked: vec![false; nb_vertices],
72            id: (0..nb_vertices).collect::<Vec<usize>>(),
73            nb_scc: 0,
74        }
75    }
76    pub fn find_scc(&mut self, graph: &DirectedGraph) {
77        // builds all the string connected components from a directed graph
78
79        // run dfs on the reverse graph
80        let nb = graph.nb_vertices();
81        let mut topo = TopologicalSort::init(nb);
82        topo.depth_first_order(&graph.reverse());
83        let order_second_dfs = topo.reverse_postorder();
84        // order_second_dfs.reverse();
85        for v in 0..nb {
86            let v = order_second_dfs[nb - 1 - v];
87            if !self.marked[v] {
88                // run DFS for each vertex in each component
89                dfs(graph, &mut self.marked, &mut self.id, v, v, true, true);
90                self.nb_scc += 1;
91            }
92        }
93    }
94    pub fn connected(&self, v: usize, w: usize) -> Option<bool> {
95        // finds out whether or not two vertices are in the same strong connected component
96        // run time complexity O(1)
97        if !self.marked[v] || !self.marked[w] {
98            return None;
99        }
100        Some(self.id[v] == self.id[w])
101    }
102    pub fn count(&self) -> usize {
103        self.nb_scc
104    }
105}
algods/graph/processing/connection.rs

algods/graph/processing/
connection.rs
