Update toughness calculation to use binary search

1 files changed, 22 insertions, 13 deletions

diff --git a/src/main.rs b/src/main.rs
index 1b23bd0..f6aab8a 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -303,25 +303,34 @@ impl Graph {
         self.get_closure_traced(false)
     }
 
-    fn check_toughness(&self, t: i32) -> bool {
+    fn check_toughness(&self, t: f64) -> 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 {
+            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) -> i32 {
-        let max_t = 10; // Reasonable limit
-        for t in 1..max_t {
-            if self.check_toughness(t) == false {
-                return t - 1;
+    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 max_t;
+
+        return (left * 1e7).round() / 1e7;
     }
 
     fn is_complete(&self) -> bool {
@@ -383,11 +392,11 @@ fn main() {
 
         if !g.is_complete() {
             let toughness = g.get_toughness();
-            println!("Toughness of \"{}\" is {}", line, toughness);
-            if toughness >= 1 {
+            // println!("Toughness of \"{}\" is {}", line, toughness);
+            if toughness >= 1.0 {
                 counters.tough_1 += 1;
             }
-            if toughness >= 2 {
+            if toughness >= 2.0 {
                 counters.tough_2 += 1;
             }
         }