Add Dirac's, Ore's, Posa's theorems

1 files changed, 145 insertions, 15 deletions

diff --git a/src/main.rs b/src/main.rs
index f6aab8a..41a5f5b 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -324,8 +324,7 @@ impl Graph {
 
             if self.check_toughness(mid) == false {
                 right = mid;
-            }
-            else {
+            } else {
                 left = mid;
             }
         }
@@ -358,22 +357,110 @@ impl Graph {
 
 struct Counters {
     graphs: i32,
-    hamiltonian: 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,
-            hamiltonian: 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();
 
@@ -390,19 +477,43 @@ fn main() {
         let closure = g.get_closure();
         let is_complete = closure.is_complete();
 
-        if !g.is_complete() {
-            let toughness = g.get_toughness();
-            // println!("Toughness of \"{}\" is {}", line, toughness);
-            if toughness >= 1.0 {
-                counters.tough_1 += 1;
-            }
-            if toughness >= 2.0 {
-                counters.tough_2 += 1;
-            }
+        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;
+        }
+
+        if theorem25(&g, toughness, min_degree) {
+            counters.t25_hamiltonian += 1;
+        }
+
+        if dirac_theorem(&g) {
+            counters.dirac_hamiltonian += 1;
+        }
+
+        if ore_theorem(&g) {
+            counters.ore_hamiltonian += 1;
+        }
+
+        if posa_theorem(&g) {
+            counters.posa_hamiltonian += 1;
         }
 
         if is_complete {
-            counters.hamiltonian += 1;
+            counters.bch_hamiltonian += 1;
         }
 
         if is_complete && false {
@@ -438,8 +549,27 @@ fn main() {
     }
 
     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!( "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);
 }