From 527d395e80b62fcc177151b1a1fa1de496afefcc Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Wed, 11 May 2022 11:08:42 +0400
Subject: Added algorithms for counting components and iterating over all
 cutsets

---
 src/main.rs | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 83 insertions(+), 1 deletion(-)

(limited to 'src')

diff --git a/src/main.rs b/src/main.rs
index 5d0f49b..5014ec5 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -39,6 +39,36 @@ impl fmt::Display for Graph {
     }
 }
 
+fn iterate(n: usize) -> Vec<Vec<i32>> {
+    let mut components = Vec::new();
+
+    let mut v: Vec<i32> = vec![0; n];
+    loop {
+        let mut sum: usize = 0;
+        for i in &v {
+            sum += *i as usize;
+        }
+
+        if sum == v.len() {
+            break;
+        }
+
+        let mut k = 0;
+        for i in 0..v.len() {
+            if v[i] == 1 {
+                v[i] = 0;
+            } else {
+                k = i;
+                break;
+            }
+        }
+        v[k] = 1;
+        components.push(v.clone());
+    }
+
+    return components;
+}
+
 impl Graph {
     fn from_g6(line: &String) -> Graph {
         let mut chars: Vec<u8> = Vec::new();
@@ -178,6 +208,50 @@ impl Graph {
         return cycle;
     }
 
+    fn cutsets(&self) -> Vec<Graph> {
+        let mut cs = Vec::new();
+        for vertices in iterate(self.size) {
+            let mut g = self.clone();
+            for vertice in 0..g.size {
+                for i in 0..g.size {
+                    if vertices[vertice] == 0 {
+                        g.matrix[vertice as usize][i as usize] = 0;
+                        g.matrix[i as usize][vertice as usize] = 0;
+                    }
+                }
+            }
+            cs.push(g);
+        }
+        return cs;
+    }
+
+    fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
+        visited[*vertex] = 1;
+        for i in 0..self.size {
+            if visited[i] == 0 && self.matrix[*vertex][i] != 0 {
+                self.dfs(&i, visited);
+            }
+        }
+        return;
+    }
+
+    fn count_components(&self) -> usize {
+        let mut visited = vec![0; self.size];
+        let mut count = 0;
+        while visited.iter().sum::<usize>() != visited.len() {
+            let mut next = 0;
+            for i in 0..self.size {
+                if visited[i] == 0 {
+                    next = i;
+                    break;
+                }
+            }
+            self.dfs(&next, &mut visited);
+            count += 1;
+        }
+        return count;
+    }
+
     fn get_closure(&self) -> Graph {
         self.get_closure_traced(false)
     }
@@ -213,9 +287,17 @@ fn main() {
         }
 
         if is_complete {
+            let components_count = g.count_components();
+            println!("Components count: {components_count}");
             println!("Graph: {line}\n{g}");
+
+            println!("Graph cutsets:");
+            for cutset in g.cutsets() {
+                println!("{cutset}\n");
+            }
+
             let cycle = g.get_hamiltonian_cycle();
-            print!("Cycle: ");
+            print!("Hamiltonian cycle: ");
             let start = 0;
             let mut current = start;
             loop {
-- 
cgit v1.2.3