From 4492e3ad29265b0e12df65776954ed4dbd56cf39 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Wed, 11 May 2022 12:17:44 +0400
Subject: Refactored cutset code

---
 src/main.rs | 50 ++++++++++++++++++++++++++++++++------------------
 1 file changed, 32 insertions(+), 18 deletions(-)

diff --git a/src/main.rs b/src/main.rs
index 1cc0520..e7163e7 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -4,7 +4,13 @@ use std::time::Instant;
 
 struct Graph {
     size: usize,
-    matrix: Vec<Vec<u32>>,
+    matrix: Vec<Vec<i32>>,
+}
+
+struct Cutset {
+    cardinality: usize,
+    vertices: Vec<i32>,
+    graph: Graph,
 }
 
 impl Clone for Graph {
@@ -79,11 +85,11 @@ impl Graph {
         let size = chars[0] as usize;
         let bytes = &chars[1..];
 
-        let mut matrix: Vec<Vec<u32>> = vec![vec![0; size]; size];
+        let mut matrix: Vec<Vec<i32>> = vec![vec![0; size]; size];
         let mut i = 0;
         for col in 1..size {
             for row in 0..col {
-                let bit: u32 = (bytes[i / 6] >> (5 - i % 6) & 1) as u32;
+                let bit: i32 = (bytes[i / 6] >> (5 - i % 6) & 1) as i32;
                 matrix[row][col] = bit;
                 matrix[col][row] = bit;
                 i += 1;
@@ -219,7 +225,7 @@ impl Graph {
         return cycle;
     }
 
-    fn cutsets(&self) -> Vec<(Vec<i32>, Graph)> {
+    fn cutsets(&self) -> Vec<Cutset> {
         let mut cs = Vec::new();
         for vertices in iterate(self.size) {
             let mut g = self.clone();
@@ -231,24 +237,31 @@ impl Graph {
                     }
                 }
             }
-            cs.push((vertices, g));
+            let cardinality = vertices.iter().sum::<i32>() as usize;
+            cs.push(Cutset {
+                cardinality,
+                vertices: vertices.clone(),
+                graph: g,
+            });
         }
         return cs;
     }
 
-    fn max_independent_cutset(&self) -> Option<(Vec<i32>, Graph)> {
-        let mut cardinality = 0;
+    fn max_independent_cutset(&self) -> Cutset {
         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));
-                }
+        for cutset in self.cutsets() {
+            if cutset.graph.is_independent() {
+                match &max_cutset {
+                    None => max_cutset = Some(cutset),
+                    Some(m_cutset) => {
+                        if cutset.cardinality > m_cutset.cardinality {
+                            max_cutset = Some(cutset);
+                        }
+                    }
+                };
             }
         }
-        return max_cutset;
+        return max_cutset.unwrap();
     }
 
     fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
@@ -330,9 +343,10 @@ fn main() {
             println!("Minimal degree: {min_degree}");
             println!("Graph: {line}\n{g}");
 
-            let (vertices, cutset) = g.max_independent_cutset().unwrap();
-            println!("Maximal independent cutset:\n{cutset}");
-            println!("Cutset cardinality: {}", vertices.iter().sum::<i32>());
+            let cutset = g.max_independent_cutset();
+            println!("Maximal independent cutset:\n{}", cutset.graph);
+            println!("Included vertices: {:?}", cutset.vertices);
+            println!("Cutset cardinality: {}", cutset.cardinality);
 
             let cycle = g.get_hamiltonian_cycle();
             print!("Hamiltonian cycle: ");
-- 
cgit v1.2.3