From cf1396c9ac9a37d5f5b0821f1572be17bcca3aa7 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sun, 9 Apr 2023 18:03:28 +0400 Subject: Changed structure of project and renamed binary --- .gitignore | 6 +- Cargo.lock | 7 - Cargo.toml | 8 - graph-checker/Cargo.lock | 7 + graph-checker/Cargo.toml | 6 + graph-checker/src/main.rs | 585 ++++++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 585 ---------------------------------------------- 7 files changed, 602 insertions(+), 602 deletions(-) delete mode 100644 Cargo.lock delete mode 100644 Cargo.toml create mode 100644 graph-checker/Cargo.lock create mode 100644 graph-checker/Cargo.toml create mode 100644 graph-checker/src/main.rs delete mode 100644 src/main.rs diff --git a/.gitignore b/.gitignore index 956d7f0..0f66a9c 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,8 @@ -# Rust -/target .* +!.gitignore + +# Rust +target # Python venv diff --git a/Cargo.lock b/Cargo.lock deleted file mode 100644 index 41ac3f5..0000000 --- a/Cargo.lock +++ /dev/null @@ -1,7 +0,0 @@ -# This file is automatically @generated by Cargo. -# It is not intended for manual editing. -version = 3 - -[[package]] -name = "coursework-year3" -version = "0.1.0" diff --git a/Cargo.toml b/Cargo.toml deleted file mode 100644 index 69fb7fe..0000000 --- a/Cargo.toml +++ /dev/null @@ -1,8 +0,0 @@ -[package] -name = "coursework-year3" -version = "0.1.0" -edition = "2021" - -# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html - -[dependencies] diff --git a/graph-checker/Cargo.lock b/graph-checker/Cargo.lock new file mode 100644 index 0000000..41ac3f5 --- /dev/null +++ b/graph-checker/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "coursework-year3" +version = "0.1.0" diff --git a/graph-checker/Cargo.toml b/graph-checker/Cargo.toml new file mode 100644 index 0000000..ffce39c --- /dev/null +++ b/graph-checker/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "graph-checker" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs new file mode 100644 index 0000000..e09d15f --- /dev/null +++ b/graph-checker/src/main.rs @@ -0,0 +1,585 @@ +use std::fmt; +use std::io::{self, BufRead}; +use std::time::Instant; + +struct Graph { + size: usize, + matrix: Vec>, +} + +struct Cutset { + cardinality: usize, + vertices: Vec, + 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> { + let mut components = Vec::new(); + + let mut v: Vec = 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 { + fn from_g6(line: &String) -> Graph { + let mut chars: Vec = 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![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 }; + } + + 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; + } + + 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; + } + + 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; + } + + fn get_hamiltonian_cycle(&self) -> Vec { + let closure = self.get_closure_traced(true); + + let mut cycle = Vec::new(); + for i in 0..self.size - 1 { + cycle.push(i + 1); + } + cycle.push(0); + + loop { + let mut start = 0; + let mut m = 0; + + let mut end = start; + let mut new_start = start; + let mut current = start; + loop { + let next = cycle[current]; + let val = closure.matrix[current][next]; + // println!("{current} -> {next} = {val}"); + if val > m { + m = val; + end = current; + new_start = next; + } + current = next; + if current == start { + break; + } + } + if m == 1 { + break; + } + // println!("New start: {new_start}, end: {end}, m = {m}"); + start = new_start; + + let mut s = start; + let mut current = cycle[start]; + while current != end { + let next = cycle[current]; + let u1 = closure.matrix[start][next]; + let u2 = closure.matrix[end][current]; + if u1 < m && u2 < m { + s = current; + break; + } + current = next; + } + // println!("s = {s}"); + + let mut new_cycle = Vec::new(); + new_cycle.push(start); + let mut current = cycle[s]; + while current != end { + new_cycle.push(current); + current = cycle[current]; + } + new_cycle.push(end); + { + let mut tmp = Vec::new(); + let mut current = cycle[start]; + while current != s { + tmp.push(current); + current = cycle[current]; + } + tmp.push(s); + tmp.reverse(); + for i in tmp { + new_cycle.push(i); + } + } + for i in 0..self.size - 1 { + cycle[new_cycle[i]] = new_cycle[i + 1]; + } + cycle[new_cycle[self.size - 1]] = new_cycle[0]; + } + + return cycle; + } + + fn cutsets(&self) -> Vec { + 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::() as usize; + cs.push(Cutset { + cardinality, + vertices: vertices.clone(), + graph: g, + }); + } + return cs; + } + + 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) { + 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) -> 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::() != 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; + } + + fn count_components(&self) -> usize { + self.count_components_partial(&vec![1; self.size]) + } + + fn get_closure(&self) -> Graph { + self.get_closure_traced(false) + } + + 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; + } + + 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; + } + + 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; + } + + 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; + } +} + +struct Counters { + graphs: i32, + tough_1: i32, + tough_2: i32, + bch_hamiltonian: i32, + t15_hamiltonian: i32, + t25_hamiltonian: i32, + dirac_hamiltonian: i32, + ore_hamiltonian: i32, + posa_hamiltonian: i32, +} + +impl Counters { + fn new() -> Counters { + return Counters { + graphs: 0, + tough_1: 0, + tough_2: 0, + bch_hamiltonian: 0, + t15_hamiltonian: 0, + t25_hamiltonian: 0, + dirac_hamiltonian: 0, + ore_hamiltonian: 0, + posa_hamiltonian: 0, + }; + } +} + +fn theorem15(g: &Graph, toughness: f64, min_degree: f64) -> bool { + let max_ind_cutset_size = g.max_independent_cutset().cardinality as f64; + let third_of_size = g.size as f64 / 3.0; + let tmp = if third_of_size > max_ind_cutset_size - 1.0 { + third_of_size + } else { + max_ind_cutset_size - 1.0 + }; + + return toughness >= 1.0 && min_degree >= tmp; +} + +fn theorem25(g: &Graph, toughness: f64, min_degree: f64) -> bool { + return min_degree > g.size as f64 / (toughness + 1.0) - 1.0; +} + +fn dirac_theorem(g: &Graph) -> bool { + for vertex in 0..g.size { + if (g.degree(vertex) as f64) < g.size as f64 / 2.0 { + return false; + } + } + return true; +} + +fn ore_theorem(g: &Graph) -> bool { + for v1 in 0..g.size { + for v2 in 0..g.size { + if v1 == v2 || g.matrix[v1][v2] != 0 { + continue; + } + let d1 = g.degree(v1); + let d2 = g.degree(v2); + if d1 + d2 < g.size { + return false; + } + } + } + return true; +} + +fn posa_theorem(g: &Graph) -> bool { + let mut degrees = Vec::new(); + for v in 0..g.size { + degrees.push(g.degree(v)); + } + + let end = if g.size % 2 == 0 { + g.size / 2 + } else { + (g.size - 1) / 2 + }; + + for k in 1..end { + let mut cnt = 0; + for d in °rees { + if *d <= k { + cnt += 1; + } + } + if cnt >= k { + return false; + } + } + if g.size % 2 != 0 { + let mut cnt = 0; + for d in °rees { + if *d <= end { + cnt += 1; + } + } + if cnt > end { + return false; + } + } + return true; +} + +fn main() { + let stdin = io::stdin(); + + let mut time = 0; + let mut counters = Counters::new(); + + for line in stdin.lock().lines() { + let line = line.unwrap(); + + let g = Graph::from_g6(&line); + counters.graphs += 1; + + let start = Instant::now(); + let closure = g.get_closure(); + let is_complete = closure.is_complete(); + + let toughness = if g.is_complete() { + f64::MAX + } else { + g.get_toughness() + }; + + if toughness >= 1.0 { + counters.tough_1 += 1; + } + if toughness >= 2.0 { + counters.tough_2 += 1; + } + + let min_degree = g.min_degree() as f64; + + if theorem15(&g, toughness, min_degree) { + counters.t15_hamiltonian += 1; + println!("g6:bigalke-jung:{}", line); + } + + if theorem25(&g, toughness, min_degree) { + counters.t25_hamiltonian += 1; + println!("g6:bauer:{}", line); + } + + if dirac_theorem(&g) { + counters.dirac_hamiltonian += 1; + println!("g6:dirac:{}", line); + } + + if ore_theorem(&g) { + counters.ore_hamiltonian += 1; + println!("g6:ore:{}", line); + } + + if posa_theorem(&g) { + counters.posa_hamiltonian += 1; + println!("g6:posa:{}", line); + } + + if is_complete { + counters.bch_hamiltonian += 1; + println!("g6:bondy-chvatal:{}", line); + } + + if is_complete && false { + println!("Graph: {line}\n{g}"); + + let components_count = g.count_components(); + println!("Components count: {components_count}"); + let min_degree = g.min_degree(); + println!("Minimal degree: {min_degree}"); + + let cutset = g.max_independent_cutset(); + println!("Maximal independent cutset:\n{}", cutset.graph); + println!("Included vertices: {:?}", cutset.vertices); + println!("Cutset cardinality: {}", cutset.cardinality); + + let cycle = g.get_hamiltonian_cycle(); + print!("Hamiltonian cycle: "); + let start = 0; + let mut current = start; + loop { + print!("{}", current + 1); + print!(" -> "); + current = cycle[current]; + if current == start { + println!("{}", current + 1); + break; + } + } + } + + let elapsed = start.elapsed(); + time += elapsed.as_nanos(); + } + + println!("Total count of graphs: {}", counters.graphs); + println!("Count of 1-tough graphs: {}", counters.tough_1); + println!("Count of 2-tough graphs: {}", counters.tough_2); + println!( + "Count of Dirac's Hamiltonian graphs: {}", + counters.dirac_hamiltonian + ); + println!( + "Count of Ore's Hamiltonian graphs: {}", + counters.ore_hamiltonian + ); + println!( + "Count of Posa's Hamiltonian graphs: {}", + counters.posa_hamiltonian + ); + println!( + "Count of Bondy-Chvatal Hamiltonian graphs: {}", + counters.bch_hamiltonian + ); + println!( + "Count of Theorem 15 Hamiltonian graphs: {}", + counters.t15_hamiltonian + ); + println!( + "Count of Theorem 25 Hamiltonian graphs: {}", + counters.t25_hamiltonian + ); + println!("Time elapsed: {}s", time as f64 / 1e9); +} diff --git a/src/main.rs b/src/main.rs deleted file mode 100644 index e09d15f..0000000 --- a/src/main.rs +++ /dev/null @@ -1,585 +0,0 @@ -use std::fmt; -use std::io::{self, BufRead}; -use std::time::Instant; - -struct Graph { - size: usize, - matrix: Vec>, -} - -struct Cutset { - cardinality: usize, - vertices: Vec, - 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> { - let mut components = Vec::new(); - - let mut v: Vec = 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 { - fn from_g6(line: &String) -> Graph { - let mut chars: Vec = 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![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 }; - } - - 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; - } - - 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; - } - - 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; - } - - fn get_hamiltonian_cycle(&self) -> Vec { - let closure = self.get_closure_traced(true); - - let mut cycle = Vec::new(); - for i in 0..self.size - 1 { - cycle.push(i + 1); - } - cycle.push(0); - - loop { - let mut start = 0; - let mut m = 0; - - let mut end = start; - let mut new_start = start; - let mut current = start; - loop { - let next = cycle[current]; - let val = closure.matrix[current][next]; - // println!("{current} -> {next} = {val}"); - if val > m { - m = val; - end = current; - new_start = next; - } - current = next; - if current == start { - break; - } - } - if m == 1 { - break; - } - // println!("New start: {new_start}, end: {end}, m = {m}"); - start = new_start; - - let mut s = start; - let mut current = cycle[start]; - while current != end { - let next = cycle[current]; - let u1 = closure.matrix[start][next]; - let u2 = closure.matrix[end][current]; - if u1 < m && u2 < m { - s = current; - break; - } - current = next; - } - // println!("s = {s}"); - - let mut new_cycle = Vec::new(); - new_cycle.push(start); - let mut current = cycle[s]; - while current != end { - new_cycle.push(current); - current = cycle[current]; - } - new_cycle.push(end); - { - let mut tmp = Vec::new(); - let mut current = cycle[start]; - while current != s { - tmp.push(current); - current = cycle[current]; - } - tmp.push(s); - tmp.reverse(); - for i in tmp { - new_cycle.push(i); - } - } - for i in 0..self.size - 1 { - cycle[new_cycle[i]] = new_cycle[i + 1]; - } - cycle[new_cycle[self.size - 1]] = new_cycle[0]; - } - - return cycle; - } - - fn cutsets(&self) -> Vec { - 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::() as usize; - cs.push(Cutset { - cardinality, - vertices: vertices.clone(), - graph: g, - }); - } - return cs; - } - - 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) { - 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) -> 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::() != 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; - } - - fn count_components(&self) -> usize { - self.count_components_partial(&vec![1; self.size]) - } - - fn get_closure(&self) -> Graph { - self.get_closure_traced(false) - } - - 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; - } - - 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; - } - - 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; - } - - 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; - } -} - -struct Counters { - graphs: i32, - tough_1: i32, - tough_2: i32, - bch_hamiltonian: i32, - t15_hamiltonian: i32, - t25_hamiltonian: i32, - dirac_hamiltonian: i32, - ore_hamiltonian: i32, - posa_hamiltonian: i32, -} - -impl Counters { - fn new() -> Counters { - return Counters { - graphs: 0, - tough_1: 0, - tough_2: 0, - bch_hamiltonian: 0, - t15_hamiltonian: 0, - t25_hamiltonian: 0, - dirac_hamiltonian: 0, - ore_hamiltonian: 0, - posa_hamiltonian: 0, - }; - } -} - -fn theorem15(g: &Graph, toughness: f64, min_degree: f64) -> bool { - let max_ind_cutset_size = g.max_independent_cutset().cardinality as f64; - let third_of_size = g.size as f64 / 3.0; - let tmp = if third_of_size > max_ind_cutset_size - 1.0 { - third_of_size - } else { - max_ind_cutset_size - 1.0 - }; - - return toughness >= 1.0 && min_degree >= tmp; -} - -fn theorem25(g: &Graph, toughness: f64, min_degree: f64) -> bool { - return min_degree > g.size as f64 / (toughness + 1.0) - 1.0; -} - -fn dirac_theorem(g: &Graph) -> bool { - for vertex in 0..g.size { - if (g.degree(vertex) as f64) < g.size as f64 / 2.0 { - return false; - } - } - return true; -} - -fn ore_theorem(g: &Graph) -> bool { - for v1 in 0..g.size { - for v2 in 0..g.size { - if v1 == v2 || g.matrix[v1][v2] != 0 { - continue; - } - let d1 = g.degree(v1); - let d2 = g.degree(v2); - if d1 + d2 < g.size { - return false; - } - } - } - return true; -} - -fn posa_theorem(g: &Graph) -> bool { - let mut degrees = Vec::new(); - for v in 0..g.size { - degrees.push(g.degree(v)); - } - - let end = if g.size % 2 == 0 { - g.size / 2 - } else { - (g.size - 1) / 2 - }; - - for k in 1..end { - let mut cnt = 0; - for d in °rees { - if *d <= k { - cnt += 1; - } - } - if cnt >= k { - return false; - } - } - if g.size % 2 != 0 { - let mut cnt = 0; - for d in °rees { - if *d <= end { - cnt += 1; - } - } - if cnt > end { - return false; - } - } - return true; -} - -fn main() { - let stdin = io::stdin(); - - let mut time = 0; - let mut counters = Counters::new(); - - for line in stdin.lock().lines() { - let line = line.unwrap(); - - let g = Graph::from_g6(&line); - counters.graphs += 1; - - let start = Instant::now(); - let closure = g.get_closure(); - let is_complete = closure.is_complete(); - - let toughness = if g.is_complete() { - f64::MAX - } else { - g.get_toughness() - }; - - if toughness >= 1.0 { - counters.tough_1 += 1; - } - if toughness >= 2.0 { - counters.tough_2 += 1; - } - - let min_degree = g.min_degree() as f64; - - if theorem15(&g, toughness, min_degree) { - counters.t15_hamiltonian += 1; - println!("g6:bigalke-jung:{}", line); - } - - if theorem25(&g, toughness, min_degree) { - counters.t25_hamiltonian += 1; - println!("g6:bauer:{}", line); - } - - if dirac_theorem(&g) { - counters.dirac_hamiltonian += 1; - println!("g6:dirac:{}", line); - } - - if ore_theorem(&g) { - counters.ore_hamiltonian += 1; - println!("g6:ore:{}", line); - } - - if posa_theorem(&g) { - counters.posa_hamiltonian += 1; - println!("g6:posa:{}", line); - } - - if is_complete { - counters.bch_hamiltonian += 1; - println!("g6:bondy-chvatal:{}", line); - } - - if is_complete && false { - println!("Graph: {line}\n{g}"); - - let components_count = g.count_components(); - println!("Components count: {components_count}"); - let min_degree = g.min_degree(); - println!("Minimal degree: {min_degree}"); - - let cutset = g.max_independent_cutset(); - println!("Maximal independent cutset:\n{}", cutset.graph); - println!("Included vertices: {:?}", cutset.vertices); - println!("Cutset cardinality: {}", cutset.cardinality); - - let cycle = g.get_hamiltonian_cycle(); - print!("Hamiltonian cycle: "); - let start = 0; - let mut current = start; - loop { - print!("{}", current + 1); - print!(" -> "); - current = cycle[current]; - if current == start { - println!("{}", current + 1); - break; - } - } - } - - let elapsed = start.elapsed(); - time += elapsed.as_nanos(); - } - - println!("Total count of graphs: {}", counters.graphs); - println!("Count of 1-tough graphs: {}", counters.tough_1); - println!("Count of 2-tough graphs: {}", counters.tough_2); - println!( - "Count of Dirac's Hamiltonian graphs: {}", - counters.dirac_hamiltonian - ); - println!( - "Count of Ore's Hamiltonian graphs: {}", - counters.ore_hamiltonian - ); - println!( - "Count of Posa's Hamiltonian graphs: {}", - counters.posa_hamiltonian - ); - println!( - "Count of Bondy-Chvatal Hamiltonian graphs: {}", - counters.bch_hamiltonian - ); - println!( - "Count of Theorem 15 Hamiltonian graphs: {}", - counters.t15_hamiltonian - ); - println!( - "Count of Theorem 25 Hamiltonian graphs: {}", - counters.t25_hamiltonian - ); - println!("Time elapsed: {}s", time as f64 / 1e9); -} -- cgit v1.2.3