Added theorems from Gould 2003

3 files changed, 391 insertions, 89 deletions

diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
index 25d7f72..581c522 100644
--- a/graph-checker/src/graph.rs
+++ b/graph-checker/src/graph.rs
@@ -51,6 +51,31 @@ impl fmt::Debug for Graph {
     }
 }
 
+// TODO: impl Cutset
+fn trim_cutset(cutset: &Cutset) -> Graph {
+    let mut mat = vec![vec![0; cutset.cardinality]; cutset.cardinality];
+
+    let mut i = 0;
+    for vi in 0..cutset.graph.size {
+        if cutset.vertices[vi] == 0 {
+            continue;
+        }
+        let mut j = 0;
+        for vj in 0..cutset.graph.size {
+            if cutset.vertices[vj] == 0 {
+                continue;
+            }
+            mat[i][j] = cutset.graph.matrix[vi][vj];
+            j += 1;
+        }
+        i += 1;
+    }
+    return Graph {
+        size: cutset.cardinality,
+        matrix: mat,
+    };
+}
+
 fn iterate(n: usize) -> Vec<Vec<i32>> {
     let mut components = Vec::new();
 
@@ -236,10 +261,29 @@ impl Graph {
         self.count_components_partial(&vec![1; self.size])
     }
 
+    pub fn is_connected(&self) -> bool {
+        self.count_components() == 1
+    }
+
     // TODO: replace with is_n_connected
     pub fn is_2_connected(&self) -> bool {
         let mut vertices = vec![1; self.size];
         for i in 0..self.size {
+            vertices[i] = 0;
+            let c = self.count_components_partial(&vertices);
+            vertices[i] = 1;
+
+            if c != 1 {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    // TODO: replace with is_n_connected
+    pub fn is_3_connected(&self) -> bool {
+        let mut vertices = vec![1; self.size];
+        for i in 0..self.size {
             for j in 0..self.size {
                 if i == j {
                     continue;
@@ -258,11 +302,63 @@ impl Graph {
         return true;
     }
 
+    // TODO: replace with is_n_connected
+    pub fn is_4_connected(&self) -> bool {
+        let mut vertices = vec![1; self.size];
+        for i in 0..self.size {
+            for j in 0..self.size {
+                for k in 0..self.size {
+                    if i == j || j == k || i == k {
+                        continue;
+                    }
+                    vertices[i] = 0;
+                    vertices[j] = 0;
+                    vertices[k] = 0;
+                    let c = self.count_components_partial(&vertices);
+                    vertices[i] = 1;
+                    vertices[j] = 1;
+                    vertices[k] = 1;
+
+                    if c != 1 {
+                        return false;
+                    }
+                }
+            }
+        }
+        return true;
+    }
+
     pub fn is_n_connected(&self, n: usize) -> bool {
         // TODO: implement
         todo!();
     }
 
+    pub fn neighbors(&self, vert: i32) -> Vec<i32> {
+        let mut res = Vec::new();
+
+        for i in 0..self.size as i32 {
+            if i != vert && self.matrix[i as usize][vert as usize] != 0 {
+                res.push(i);
+            }
+        }
+
+        return res;
+    }
+
+    pub fn is_locally_connected(&self) -> bool {
+        for i in 0..self.size {
+            let neighbors = self.neighbors(i as i32);
+            let mut part = vec![0; self.size];
+            for neighbor in &neighbors {
+                part[*neighbor as usize] = 1;
+            }
+            if self.count_components_partial(&part) != 1 {
+                return false;
+            }
+        }
+        return true;
+    }
+
     pub fn get_closure(&self) -> Graph {
         self.get_closure_traced(false)
     }
@@ -378,30 +474,6 @@ impl Graph {
     }
 
     pub fn is_free_of(&self, graphs: &Vec<Graph>) -> bool {
-        fn trim_cutset(cutset: &Cutset) -> Graph {
-            let mut mat = vec![vec![0; cutset.cardinality]; cutset.cardinality];
-
-            let mut i = 0;
-            for vi in 0..cutset.graph.size {
-                if cutset.vertices[vi] == 0 {
-                    continue;
-                }
-                let mut j = 0;
-                for vj in 0..cutset.graph.size {
-                    if cutset.vertices[vj] == 0 {
-                        continue;
-                    }
-                    mat[i][j] = cutset.graph.matrix[vi][vj];
-                    j += 1;
-                }
-                i += 1;
-            }
-            return Graph {
-                size: cutset.cardinality,
-                matrix: mat,
-            };
-        }
-
         for cutset in self.cutsets() {
             let subg = trim_cutset(&cutset);
             for g in graphs {
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index b3d8602..351fe42 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -55,83 +55,112 @@ fn main() {
         let closure = g.get_closure();
         let is_complete = closure.is_complete();
 
-        let toughness = if g.is_complete() {
-            f64::MAX
-        } else {
-            g.get_toughness()
-        };
+        // 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;
-        }
+        // if toughness >= 1.0 {
+        //     counters.tough_1 += 1;
+        // }
+        // if toughness >= 2.0 {
+        //     counters.tough_2 += 1;
+        // }
 
-        let min_degree = g.min_degree() as f64;
+        // let min_degree = g.min_degree() as f64;
 
         // TODO: add counter
-        if forbidden::theorem3_1(&g) {
-            println!("g6:t3_1:{}", line);
-        }
+        // if forbidden::theorem3_1(&g) {
+        //     println!("g6:t3_1:{}", line);
+        // }
 
-        if theorem15(&g, toughness, min_degree) {
-            counters.t15_hamiltonian += 1;
-            println!("g6:bigalke-jung:{}", line);
-        }
+        // TODO: add counter
+        // if forbidden::theorem3_2(&g) {
+        //     println!("g6:t3_2:{}", line);
+        // }
 
-        if theorem25(&g, toughness, min_degree) {
-            counters.t25_hamiltonian += 1;
-            println!("g6:bauer:{}", line);
-        }
+        // TODO: add counter
+        // if forbidden::corollary3_5(&g) {
+        //     println!("g6:c3_5:{}", line);
+        // }
+
+        // if forbidden::theorem85(&g) {
+        //     println!("g6:t85:{}", line);
+        // }
+        // if forbidden::theorem86(&g) {
+        //     println!("g6:t86:{}", line);
+        // }
+        // if forbidden::theorem87(&g) {
+        //     println!("g6:t87:{}", line);
+        // }
+        // if forbidden::theorem88(&g) {
+        //     println!("g6:t88:{}", line);
+        // }
+        // if forbidden::theorem96(&g) {
+        //     println!("g6:t96:{}", line);
+        // }
+        // if forbidden::conjecture17(&g) {
+        //     println!("g6:conj17:{}", line);
+        // }
+
+        // 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 = bondy_chvatal_hamiltonian_cycle(&g);
-            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;
-                }
-            }
-        }
+        // 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 = bondy_chvatal_hamiltonian_cycle(&g);
+        //     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();
diff --git a/graph-checker/src/theorems/forbidden.rs b/graph-checker/src/theorems/forbidden.rs
index 615cdb1..8c70916 100644
--- a/graph-checker/src/theorems/forbidden.rs
+++ b/graph-checker/src/theorems/forbidden.rs
@@ -25,3 +25,204 @@ pub fn theorem3_1(g: &Graph) -> bool {
 
     return g.is_2_connected() && g.is_free_of(&forbidden);
 }
+
+pub fn theorem3_2(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let forbidden = vec![claw];
+    return g.size >= 3
+        && g.is_connected()
+        && g.is_locally_connected()
+        && g.is_free_of(&forbidden);
+}
+
+pub fn corollary3_5(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let ig = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 0, 0],
+            vec![1, 0, 1, 0],
+            vec![0, 1, 0, 1],
+            vec![0, 0, 1, 0],
+        ],
+    };
+
+    let ag = Graph {
+        size: 5,
+        matrix: vec![
+            vec![0, 1, 1, 0, 0],
+            vec![1, 0, 0, 1, 0],
+            vec![1, 0, 0, 0, 1],
+            vec![0, 1, 0, 0, 0],
+            vec![0, 0, 1, 0, 0],
+        ],
+    };
+
+    let is_2 = g.is_2_connected();
+    let claw_free = g.is_free_of(&vec![claw]);
+    return (is_2 && claw_free && g.is_free_of(&vec![ig]))
+        || (is_2 && claw_free && g.is_free_of(&vec![ag]));
+}
+
+// 2003 Gould
+
+pub fn theorem85(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let ng = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 1, 1, 0, 0],
+            vec![1, 0, 1, 0, 0, 1],
+            vec![1, 1, 0, 0, 1, 0],
+            vec![1, 0, 0, 0, 0, 0],
+            vec![0, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 0, 0, 0],
+        ],
+    };
+
+    return g.is_2_connected() && g.is_free_of(&vec![claw, ng]);
+}
+
+pub fn theorem86(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let p6 = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 0, 0, 0, 0],
+            vec![1, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 1, 0, 0],
+            vec![0, 0, 1, 0, 1, 0],
+            vec![0, 0, 0, 1, 0, 1],
+            vec![0, 0, 0, 0, 1, 0],
+        ],
+    };
+
+    return g.is_2_connected() && g.is_free_of(&vec![claw, p6]);
+}
+
+pub fn theorem87(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let z2 = Graph {
+        size: 5,
+        matrix: vec![
+            vec![0, 1, 0, 0, 0],
+            vec![1, 0, 1, 0, 0],
+            vec![0, 1, 0, 1, 1],
+            vec![0, 0, 1, 0, 1],
+            vec![0, 0, 1, 1, 1],
+        ],
+    };
+
+    return g.is_2_connected() && g.is_free_of(&vec![claw, z2]);
+}
+
+pub fn theorem88(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let wg = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 1, 0, 0, 0],
+            vec![1, 0, 1, 0, 1, 0],
+            vec![1, 1, 0, 1, 0, 0],
+            vec![0, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 0, 0, 1],
+            vec![0, 0, 0, 0, 1, 0],
+        ],
+    };
+
+    return g.is_2_connected() && g.is_free_of(&vec![claw, wg]);
+}
+
+pub fn theorem96(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    let ng = Graph {
+        size: 6,
+        matrix: vec![
+            vec![0, 1, 1, 1, 0, 0],
+            vec![1, 0, 1, 0, 0, 1],
+            vec![1, 1, 0, 0, 1, 0],
+            vec![1, 0, 0, 0, 0, 0],
+            vec![0, 0, 1, 0, 0, 0],
+            vec![0, 1, 0, 0, 0, 0],
+        ],
+    };
+
+    return g.is_3_connected() && g.is_free_of(&vec![claw, ng]);
+}
+
+pub fn conjecture17(g: &Graph) -> bool {
+    let claw = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 1, 1],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+            vec![1, 0, 0, 0],
+        ],
+    };
+
+    return g.is_4_connected() && g.is_free_of(&vec![claw]);
+}