use std::collections::HashSet;
pub struct DecrementalConnectivity {
adjacent: Vec<HashSet<usize>>,
component: Vec<usize>,
count: usize,
visited: Vec<usize>,
dfs_id: usize,
}
impl DecrementalConnectivity {
pub fn new(adjacent: Vec<HashSet<usize>>) -> Result<Self, String> {
let n = adjacent.len();
if !is_forest(&adjacent) {
return Err("input graph is not a forest!".to_string());
}
let mut tmp = DecrementalConnectivity {
adjacent,
component: vec![0; n],
count: 0,
visited: vec![0; n],
dfs_id: 1,
};
tmp.component = tmp.calc_component();
Ok(tmp)
}
pub fn connected(&self, u: usize, v: usize) -> Option<bool> {
match (self.component.get(u), self.component.get(v)) {
(Some(a), Some(b)) => Some(a == b),
_ => None,
}
}
pub fn delete(&mut self, u: usize, v: usize) {
if !self.adjacent[u].contains(&v) || self.component[u] != self.component[v] {
panic!("delete called on the edge ({u}, {v}) which doesn't exist");
}
self.adjacent[u].remove(&v);
self.adjacent[v].remove(&u);
let mut queue: Vec<usize> = Vec::new();
if self.is_smaller(u, v) {
queue.push(u);
self.dfs_id += 1;
self.visited[v] = self.dfs_id;
} else {
queue.push(v);
self.dfs_id += 1;
self.visited[u] = self.dfs_id;
}
while !queue.is_empty() {
let ¤t = queue.last().unwrap();
self.dfs_step(&mut queue, self.dfs_id);
self.component[current] = self.count;
}
self.count += 1;
}
fn calc_component(&mut self) -> Vec<usize> {
let mut visited: Vec<bool> = vec![false; self.adjacent.len()];
let mut comp: Vec<usize> = vec![0; self.adjacent.len()];
for i in 0..self.adjacent.len() {
if visited[i] {
continue;
}
let mut queue: Vec<usize> = vec![i];
while let Some(current) = queue.pop() {
if !visited[current] {
for &neighbour in self.adjacent[current].iter() {
queue.push(neighbour);
}
}
visited[current] = true;
comp[current] = self.count;
}
self.count += 1;
}
comp
}
fn is_smaller(&mut self, u: usize, v: usize) -> bool {
let mut u_queue: Vec<usize> = vec![u];
let u_id = self.dfs_id;
self.visited[v] = u_id;
self.dfs_id += 1;
let mut v_queue: Vec<usize> = vec![v];
let v_id = self.dfs_id;
self.visited[u] = v_id;
self.dfs_id += 1;
while !u_queue.is_empty() && !v_queue.is_empty() {
self.dfs_step(&mut u_queue, u_id);
self.dfs_step(&mut v_queue, v_id);
}
u_queue.is_empty()
}
fn dfs_step(&mut self, queue: &mut Vec<usize>, dfs_id: usize) {
let u = queue.pop().unwrap();
self.visited[u] = dfs_id;
for &v in self.adjacent[u].iter() {
if self.visited[v] == dfs_id {
continue;
}
queue.push(v);
}
}
}
fn is_forest(adjacent: &Vec<HashSet<usize>>) -> bool {
let mut visited = vec![false; adjacent.len()];
for node in 0..adjacent.len() {
if visited[node] {
continue;
}
if has_cycle(adjacent, &mut visited, node, node) {
return false;
}
}
true
}
fn has_cycle(
adjacent: &Vec<HashSet<usize>>,
visited: &mut Vec<bool>,
node: usize,
parent: usize,
) -> bool {
visited[node] = true;
for &neighbour in adjacent[node].iter() {
if !adjacent[neighbour].contains(&node) {
panic!("the given graph does not strictly contain bidirectional edges\n {node} -> {neighbour} exists, but the other direction does not");
}
if !visited[neighbour] {
if has_cycle(adjacent, visited, neighbour, node) {
return true;
}
} else if neighbour != parent {
return true;
}
}
false
}
#[cfg(test)]
mod tests {
use std::collections::HashSet;
#[test]
fn construction_test() {
let mut adjacent = vec![
HashSet::from([0, 1, 2, 3]),
HashSet::from([0, 4]),
HashSet::from([0, 5, 6]),
HashSet::from([0]),
HashSet::from([1]),
HashSet::from([2]),
HashSet::from([2]),
HashSet::from([7, 8]),
HashSet::from([7]),
];
let dec_con = super::DecrementalConnectivity::new(adjacent.clone()).unwrap();
assert_eq!(dec_con.component, vec![0, 0, 0, 0, 0, 0, 0, 1, 1]);
adjacent[2].insert(4);
adjacent[4].insert(2);
assert!(super::DecrementalConnectivity::new(adjacent.clone()).is_err());
}
#[test]
#[should_panic(expected = "2 -> 4 exists")]
fn non_bidirectional_test() {
let adjacent = vec![
HashSet::from([0, 1, 2, 3]),
HashSet::from([0, 4]),
HashSet::from([0, 5, 6, 4]),
HashSet::from([0]),
HashSet::from([1]),
HashSet::from([2]),
HashSet::from([2]),
HashSet::from([7, 8]),
HashSet::from([7]),
];
super::DecrementalConnectivity::new(adjacent).unwrap();
}
#[test]
#[should_panic(expected = "delete called on the edge (2, 4)")]
fn delete_panic_test() {
let adjacent = vec![
HashSet::from([0, 1, 2, 3]),
HashSet::from([0, 4]),
HashSet::from([0, 5, 6]),
HashSet::from([0]),
HashSet::from([1]),
HashSet::from([2]),
HashSet::from([2]),
HashSet::from([7, 8]),
HashSet::from([7]),
];
let mut dec_con = super::DecrementalConnectivity::new(adjacent.clone()).unwrap();
dec_con.delete(2, 4);
}
#[test]
fn query_test() {
let adjacent = vec![
HashSet::from([0, 1, 2, 3]),
HashSet::from([0, 4]),
HashSet::from([0, 5, 6]),
HashSet::from([0]),
HashSet::from([1]),
HashSet::from([2]),
HashSet::from([2]),
HashSet::from([7, 8]),
HashSet::from([7]),
];
let mut dec_con1 = super::DecrementalConnectivity::new(adjacent.clone()).unwrap();
assert!(dec_con1.connected(3, 4).unwrap());
assert!(dec_con1.connected(5, 0).unwrap());
assert!(!dec_con1.connected(2, 7).unwrap());
assert!(dec_con1.connected(0, 9).is_none());
dec_con1.delete(0, 2);
assert!(dec_con1.connected(3, 4).unwrap());
assert!(!dec_con1.connected(5, 0).unwrap());
assert!(dec_con1.connected(5, 6).unwrap());
assert!(dec_con1.connected(8, 7).unwrap());
dec_con1.delete(7, 8);
assert!(!dec_con1.connected(8, 7).unwrap());
dec_con1.delete(1, 4);
assert!(!dec_con1.connected(1, 4).unwrap());
let mut dec_con2 = super::DecrementalConnectivity::new(adjacent.clone()).unwrap();
dec_con2.delete(4, 1);
assert!(!dec_con2.connected(1, 4).unwrap());
let mut dec_con3 = super::DecrementalConnectivity::new(adjacent.clone()).unwrap();
dec_con3.delete(1, 4);
assert!(!dec_con3.connected(4, 1).unwrap());
}
}