summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/main.rs585
1 files changed, 0 insertions, 585 deletions
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<Vec<i32>>,
-}
-
-struct Cutset {
- cardinality: usize,
- vertices: Vec<i32>,
- 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 {
- 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 };
- }
-
- 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<usize> {
- 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<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;
- }
-
- 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;
- }
-
- 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 &degrees {
- if *d <= k {
- cnt += 1;
- }
- }
- if cnt >= k {
- return false;
- }
- }
- if g.size % 2 != 0 {
- let mut cnt = 0;
- for d in &degrees {
- 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);
-}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 16:52:41 +0000