From 611180cde1b65e5e809e8bad94cb4dc6e858b608 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Wed, 19 Apr 2023 09:00:11 +0400
Subject: Added theorems from Gould 2003

---
 graph-checker/src/graph.rs | 120 ++++++++++++++++++++++++++++++++++++---------
 1 file changed, 96 insertions(+), 24 deletions(-)

(limited to 'graph-checker/src/graph.rs')

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,8 +261,27 @@ 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 {
@@ -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 {
-- 
cgit v1.2.3