1 files changed, 32 insertions, 7 deletions

diff --git a/src/main.rs b/src/main.rs
index e8ad69d..1cc0520 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -103,7 +103,7 @@ impl Graph {
     fn min_degree(&self) -> usize {
         let mut min = self.size + 1;
         for i in 0..self.size {
-            let d = self.degree(i); 
+            let d = self.degree(i);
             if d < min {
                 min = d;
             }
@@ -219,7 +219,7 @@ impl Graph {
         return cycle;
     }
 
-    fn cutsets(&self) -> Vec<Graph> {
+    fn cutsets(&self) -> Vec<(Vec<i32>, Graph)> {
         let mut cs = Vec::new();
         for vertices in iterate(self.size) {
             let mut g = self.clone();
@@ -231,11 +231,26 @@ impl Graph {
                     }
                 }
             }
-            cs.push(g);
+            cs.push((vertices, g));
         }
         return cs;
     }
 
+    fn max_independent_cutset(&self) -> Option<(Vec<i32>, Graph)> {
+        let mut cardinality = 0;
+        let mut max_cutset = None;
+        for (vertices, cutset) in self.cutsets() {
+            if cutset.is_independent() {
+                let c: i32 = vertices.iter().sum();
+                if c > cardinality {
+                    cardinality = c;
+                    max_cutset = Some((vertices, cutset));
+                }
+            }
+        }
+        return max_cutset;
+    }
+
     fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
         visited[*vertex] = 1;
         for i in 0..self.size {
@@ -277,6 +292,17 @@ impl Graph {
         }
         return true;
     }
+
+    fn is_independent(&self) -> bool {
+        for row in 0..self.size {
+            for col in 0..self.size {
+                if row != col && self.matrix[row][col] != 0 {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
 }
 
 fn main() {
@@ -304,10 +330,9 @@ fn main() {
             println!("Minimal degree: {min_degree}");
             println!("Graph: {line}\n{g}");
 
-            println!("Graph cutsets:");
-            for cutset in g.cutsets() {
-                println!("{cutset}\n");
-            }
+            let (vertices, cutset) = g.max_independent_cutset().unwrap();
+            println!("Maximal independent cutset:\n{cutset}");
+            println!("Cutset cardinality: {}", vertices.iter().sum::<i32>());
 
             let cycle = g.get_hamiltonian_cycle();
             print!("Hamiltonian cycle: ");