From 30b7dc646f262ec6d97ac701859d0cf9008816c9 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Mon, 10 Apr 2023 16:31:57 +0400
Subject: Added is_free_of, is_2_connected and thorem 3.1

---
 graph-checker/src/graph.rs              | 88 ++++++++++++++++++++++++++++++++-
 graph-checker/src/main.rs               |  6 +++
 graph-checker/src/theorems/forbidden.rs | 27 ++++++++++
 graph-checker/src/theorems/mod.rs       |  1 +
 4 files changed, 121 insertions(+), 1 deletion(-)
 create mode 100644 graph-checker/src/theorems/forbidden.rs

diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
index 7ba6cb4..25d7f72 100644
--- a/graph-checker/src/graph.rs
+++ b/graph-checker/src/graph.rs
@@ -1,13 +1,14 @@
 use std::collections::HashSet;
 use std::fmt;
 
+// TODO: manual Debug impl
 #[derive(Clone, PartialEq, Eq)]
 pub struct Graph {
     pub size: usize,
     pub matrix: Vec<Vec<i32>>,
 }
 
-#[derive(Clone, PartialEq, Eq)]
+#[derive(Clone, PartialEq, Eq, Debug)]
 pub struct Cutset {
     pub cardinality: usize,
     pub vertices: Vec<i32>,
@@ -31,6 +32,25 @@ impl fmt::Display for Graph {
     }
 }
 
+// TODO: manual Debug impl
+impl fmt::Debug for Graph {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "\n")?;
+        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(());
+    }
+}
+
 fn iterate(n: usize) -> Vec<Vec<i32>> {
     let mut components = Vec::new();
 
@@ -216,6 +236,33 @@ impl Graph {
         self.count_components_partial(&vec![1; self.size])
     }
 
+    // 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 {
+            for j in 0..self.size {
+                if i == j {
+                    continue;
+                }
+                vertices[i] = 0;
+                vertices[j] = 0;
+                let c = self.count_components_partial(&vertices);
+                vertices[i] = 1;
+                vertices[j] = 1;
+
+                if c != 1 {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+
+    pub fn is_n_connected(&self, n: usize) -> bool {
+        // TODO: implement
+        todo!();
+    }
+
     pub fn get_closure(&self) -> Graph {
         self.get_closure_traced(false)
     }
@@ -329,4 +376,43 @@ impl Graph {
         }
         return false;
     }
+
+    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 {
+                if cutset.cardinality != g.size {
+                    continue;
+                }
+                if subg.is_isomorphic(g) {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
 }
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index 54af780..b3d8602 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -8,6 +8,7 @@ mod theorems;
 use crate::theorems::basic::{
     bondy_chvatal_hamiltonian_cycle, dirac_theorem, ore_theorem, posa_theorem,
 };
+use crate::theorems::forbidden;
 use crate::theorems::toughness::{theorem15, theorem25};
 
 struct Counters {
@@ -69,6 +70,11 @@ fn main() {
 
         let min_degree = g.min_degree() as f64;
 
+        // TODO: add counter
+        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);
diff --git a/graph-checker/src/theorems/forbidden.rs b/graph-checker/src/theorems/forbidden.rs
new file mode 100644
index 0000000..615cdb1
--- /dev/null
+++ b/graph-checker/src/theorems/forbidden.rs
@@ -0,0 +1,27 @@
+use crate::Graph;
+
+pub fn theorem3_1(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 z1 = Graph {
+        size: 4,
+        matrix: vec![
+            vec![0, 1, 0, 0],
+            vec![1, 0, 1, 1],
+            vec![0, 1, 0, 1],
+            vec![0, 1, 1, 0],
+        ],
+    };
+
+    let forbidden = vec![claw, z1];
+
+    return g.is_2_connected() && g.is_free_of(&forbidden);
+}
diff --git a/graph-checker/src/theorems/mod.rs b/graph-checker/src/theorems/mod.rs
index 2737cbd..1135759 100644
--- a/graph-checker/src/theorems/mod.rs
+++ b/graph-checker/src/theorems/mod.rs
@@ -1,2 +1,3 @@
 pub mod basic;
+pub mod forbidden;
 pub mod toughness;
-- 
cgit v1.2.3