diff options
| -rw-r--r-- | src/main.rs | 39 |
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: "); |