Added check of Bondy - Chvatal theorem

1 files changed, 101 insertions, 25 deletions

diff --git a/src/main.rs b/src/main.rs
index 3e6e952..3aa9320 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,40 +1,116 @@
 use std::io::{self, BufRead};
+use std::fmt;
 
-fn read_graph(line: String) -> (usize, Vec<Vec<u8>>) {
-    let mut chars: Vec<u8> = Vec::new();
-    for character in line.chars() {
-        chars.push((character as i32 - 63) as u8);
+struct Graph {
+    size: usize,
+    matrix: Vec<Vec<u8>>
+}
+
+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(());
+    }
+}
+
+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<u8>> = vec![vec![0; size]; size];
+        let mut i = 0;
+        for col in 1..size {
+            for row in 0..col {
+                let bit: u8 = bytes[i / 6] >> (5 - i % 6) & 1;
+                matrix[row][col] = bit;
+                matrix[col][row] = bit;
+                i += 1;
+            }
+        }
+        return Graph { size, matrix };
+    }
+
+    fn degree(&self, vertex: usize) -> usize {
+        return self.matrix[vertex as usize].iter().sum::<u8>() as usize;
+    }
+
+    fn get_closure(&self) -> Graph {
+        let mut closure = self.clone();
+        for _ in 0..(closure.size * closure.size) {
+            for row in 0..closure.size {
+                for col in 0..closure.size {
+                    if row == col { continue }
+                    let sum = closure.degree(row) + closure.degree(col);
+                    if sum >= closure.size {
+                        closure.matrix[row][col] = 1;
+                    }
+                }
+            }
+        }
+        return closure;
     }
-    // TODO: spec allows multi-byte vector size
-    let n = chars[0] as usize;
-    let bytes = &chars[1..];
-
-    let mut mat: Vec<Vec<u8>> = vec![vec![0; n]; n];
-    let mut i = 0;
-    for col in 1..n {
-        for row in 0..col {
-            let bit: u8 = bytes[i / 6] >> (5 - i % 6) & 1;
-            mat[row][col] = bit;
-            mat[col][row] = bit;
-            i += 1;
+
+    fn is_complete(&self) -> bool {
+        for row in 0..self.size {
+            for col in 0..self.size {
+                if row != col && self.matrix[row][col] != 1 {
+                    return false;
+                }
+            }
         }
+        return true;
     }
-    return (n, mat);
 }
 
 fn main() {
     let stdin = io::stdin();
 
+    let mut count = 0;
     for line in stdin.lock().lines() {
-        let (n, mat) = read_graph(line.unwrap());
+        let line = line.unwrap();
+        let g = Graph::from_g6(&line);
+        let closure = g.get_closure();
 
-        println!("Vector of size {}", n);
-        for row in 0..n {
-            for col in 0..n {
-                print!("{} ", mat[row][col]);
-            }
-            println!("");
+        println!("Vector of size {}", g.size);
+        println!("{}", g);
+        println!("Its closure:");
+        println!("{}", closure);
+        if closure.is_complete() {
+            println!("Graph {} is Hamiltonian", &line);
+            count += 1;
+        }
+        else {
+            println!("Graph {} is not Hamiltonian", &line);
         }
+        println!("");
     }
-
+    println!("Count of Hamiltonian graphs: {}", count);
 }