diff options
Diffstat (limited to 'graph-checker/src/graph.rs')
| -rw-r--r-- | graph-checker/src/graph.rs | 276 |
1 files changed, 276 insertions, 0 deletions
diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs new file mode 100644 index 0000000..4c06660 --- /dev/null +++ b/graph-checker/src/graph.rs @@ -0,0 +1,276 @@ +use std::fmt; + +pub struct Graph { + pub size: usize, + pub matrix: Vec<Vec<i32>>, +} + +pub struct Cutset { + pub cardinality: usize, + pub vertices: Vec<i32>, + pub graph: Graph, +} + +impl Clone for Graph { + fn clone(&self) -> Self { + let mut matrix = vec![vec![0; self.size]; self.size]; + for row in 0..self.size { + for col in 0..self.size { + matrix[row][col] = self.matrix[row][col]; + } + } + return Graph { + size: self.size, + matrix, + }; + } +} + +impl fmt::Display for Graph { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + for row in 0..self.size { + for col in 0..self.size { + write!(f, "{}", self.matrix[row][col])?; + if col < self.size - 1 { + write!(f, " ")?; + } + } + if row < self.size - 1 { + write!(f, "\n")?; + } + } + return Ok(()); + } +} + +fn iterate(n: usize) -> Vec<Vec<i32>> { + let mut components = Vec::new(); + + let mut v: Vec<i32> = vec![0; n]; + loop { + let mut sum: usize = 0; + for i in &v { + sum += *i as usize; + } + + if sum == v.len() { + break; + } + + let mut k = 0; + for i in 0..v.len() { + if v[i] == 1 { + v[i] = 0; + } else { + k = i; + break; + } + } + v[k] = 1; + components.push(v.clone()); + } + + return components; +} + +impl Graph { + pub fn from_g6(line: &String) -> Graph { + let mut chars: Vec<u8> = Vec::new(); + for character in line.chars() { + chars.push((character as i32 - 63) as u8); + } + // TODO: spec allows multi-byte vector size + let size = chars[0] as usize; + let bytes = &chars[1..]; + + let mut matrix: Vec<Vec<i32>> = vec![vec![0; size]; size]; + let mut i = 0; + for col in 1..size { + for row in 0..col { + let bit: i32 = (bytes[i / 6] >> (5 - i % 6) & 1) as i32; + matrix[row][col] = bit; + matrix[col][row] = bit; + i += 1; + } + } + return Graph { size, matrix }; + } + + pub fn degree(&self, vertex: usize) -> usize { + let mut sum: usize = 0; + for i in &self.matrix[vertex] { + sum += if *i == 0 { 0 } else { 1 } as usize; + } + return sum; + } + + pub fn min_degree(&self) -> usize { + let mut min = self.size + 1; + for i in 0..self.size { + let d = self.degree(i); + if d < min { + min = d; + } + } + return min; + } + + pub fn get_closure_traced(&self, trace_steps: bool) -> Graph { + let mut step = if trace_steps { 2 } else { 1 }; + + let mut closure = self.clone(); + for _ in 0..(closure.size * closure.size) { + let mut changed = false; + for row in 0..closure.size { + for col in 0..closure.size { + if row == col || closure.matrix[row][col] != 0 { + continue; + } + let sum = closure.degree(row) + closure.degree(col); + if sum >= closure.size { + closure.matrix[row][col] = step; + if trace_steps { + step += 1; + } + changed = true; + } + } + } + if !changed { + break; + } + } + return closure; + } + + pub fn cutsets(&self) -> Vec<Cutset> { + let mut cs = Vec::new(); + for vertices in iterate(self.size) { + let mut g = self.clone(); + for vertex in 0..g.size { + for i in 0..g.size { + if vertices[vertex] == 0 { + g.matrix[vertex as usize][i as usize] = 0; + g.matrix[i as usize][vertex as usize] = 0; + } + } + } + let cardinality = vertices.iter().sum::<i32>() as usize; + cs.push(Cutset { + cardinality, + vertices: vertices.clone(), + graph: g, + }); + } + return cs; + } + + pub fn max_independent_cutset(&self) -> Cutset { + let mut max_cutset = None; + for cutset in self.cutsets() { + if cutset.graph.is_independent() { + match &max_cutset { + None => max_cutset = Some(cutset), + Some(m_cutset) => { + if cutset.cardinality > m_cutset.cardinality { + max_cutset = Some(cutset); + } + } + }; + } + } + return max_cutset.unwrap(); + } + + fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) { + visited[*vertex] = 1; + for i in 0..self.size { + if visited[i] == 0 && self.matrix[*vertex][i] != 0 { + self.dfs(&i, visited); + } + } + } + + fn count_components_partial(&self, included_vertices: &Vec<i32>) -> usize { + let mut visited = vec![0; self.size]; + for i in 0..included_vertices.len() { + if included_vertices[i] == 0 { + visited[i] = 1; + } + } + let mut count = 0; + while visited.iter().sum::<usize>() != visited.len() { + let mut next = 0; + for i in 0..self.size { + if visited[i] == 0 { + next = i; + break; + } + } + self.dfs(&next, &mut visited); + count += 1; + } + return count; + } + + pub fn count_components(&self) -> usize { + self.count_components_partial(&vec![1; self.size]) + } + + pub fn get_closure(&self) -> Graph { + self.get_closure_traced(false) + } + + pub fn check_toughness(&self, t: f64) -> bool { + for cutset in self.cutsets() { + let components_count = + cutset.graph.count_components_partial(&cutset.vertices) as f64; + let cut_cardinality = (self.size - cutset.cardinality) as f64; + if components_count > 1.0 && cut_cardinality < t * components_count + { + return false; + } + } + return true; + } + + pub fn get_toughness(&self) -> f64 { + let mut left: f64 = 0.0; + let mut right: f64 = 1024.0; // Reasonable limit + let eps: f64 = 1e-9; + + while (right - left).abs() > eps { + let mid = (left + right) / 2.0; + + if self.check_toughness(mid) == false { + right = mid; + } else { + left = mid; + } + } + + return (left * 1e7).round() / 1e7; + } + + pub fn is_complete(&self) -> bool { + for row in 0..self.size { + for col in 0..self.size { + if row != col && self.matrix[row][col] == 0 { + return false; + } + } + } + return true; + } + + pub fn is_independent(&self) -> bool { + for row in 0..self.size { + for col in 0..self.size { + if row != col && self.matrix[row][col] != 0 { + return false; + } + } + } + return true; + } +} |