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 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 87 insertions(+), 1 deletion(-)

(limited to 'graph-checker/src/graph.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;
+    }
 }
-- 
cgit v1.2.3