Add functions for checking and calculating toughness

1 files changed, 78 insertions, 14 deletions

diff --git a/src/main.rs b/src/main.rs
index e7163e7..1b23bd0 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -229,11 +229,11 @@ impl Graph {
         let mut cs = Vec::new();
         for vertices in iterate(self.size) {
             let mut g = self.clone();
-            for vertice in 0..g.size {
+            for vertex in 0..g.size {
                 for i in 0..g.size {
-                    if vertices[vertice] == 0 {
-                        g.matrix[vertice as usize][i as usize] = 0;
-                        g.matrix[i as usize][vertice as usize] = 0;
+                    if vertices[vertex] == 0 {
+                        g.matrix[vertex as usize][i as usize] = 0;
+                        g.matrix[i as usize][vertex as usize] = 0;
                     }
                 }
             }
@@ -271,11 +271,15 @@ impl Graph {
                 self.dfs(&i, visited);
             }
         }
-        return;
     }
 
-    fn count_components(&self) -> usize {
+    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;
@@ -291,10 +295,35 @@ impl Graph {
         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: i32) -> bool {
+        for cutset in self.cutsets() {
+            let components_count = cutset.graph.count_components_partial(&cutset.vertices) as i32;
+            let cut_cardinality = (self.size - cutset.cardinality) as i32;
+            if components_count > 1 && cut_cardinality < t * components_count {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    fn get_toughness(&self) -> i32 {
+        let max_t = 10; // Reasonable limit
+        for t in 1..max_t {
+            if self.check_toughness(t) == false {
+                return t - 1;
+            }
+        }
+        return max_t;
+    }
+
     fn is_complete(&self) -> bool {
         for row in 0..self.size {
             for col in 0..self.size {
@@ -318,30 +347,62 @@ impl Graph {
     }
 }
 
+struct Counters {
+    graphs: i32,
+    hamiltonian: i32,
+    tough_1: i32,
+    tough_2: i32,
+}
+
+impl Counters {
+    fn new() -> Counters {
+        return Counters {
+            graphs: 0,
+            hamiltonian: 0,
+            tough_1: 0,
+            tough_2: 0,
+        };
+    }
+}
+
 fn main() {
     let stdin = io::stdin();
 
-    let mut t = 0;
-    let mut count = 0;
+    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();
 
-        if is_complete {
-            count += 1;
+        if !g.is_complete() {
+            let toughness = g.get_toughness();
+            println!("Toughness of \"{}\" is {}", line, toughness);
+            if toughness >= 1 {
+                counters.tough_1 += 1;
+            }
+            if toughness >= 2 {
+                counters.tough_2 += 1;
+            }
         }
 
         if is_complete {
+            counters.hamiltonian += 1;
+        }
+
+        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}");
-            println!("Graph: {line}\n{g}");
 
             let cutset = g.max_independent_cutset();
             println!("Maximal independent cutset:\n{}", cutset.graph);
@@ -364,9 +425,12 @@ fn main() {
         }
 
         let elapsed = start.elapsed();
-        t += elapsed.as_nanos();
+        time += elapsed.as_nanos();
     }
 
-    println!("Count of Hamiltonian graphs: {}", count);
-    println!("Time elapsed: {}s", t as f64 / 1e9);
+    println!("Total count of graphs: {}", counters.graphs);
+    println!("Count of Hamiltonian graphs: {}", counters.hamiltonian);
+    println!("Count of 1-tough graphs: {}", counters.tough_1);
+    println!("Count of 2-tough graphs: {}", counters.tough_2);
+    println!("Time elapsed: {}s", time as f64 / 1e9);
 }