From a3bb5d6be2967705b5907a8b130b0e32176b2e2d Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin@altlinux.org>
Date: Tue, 8 Oct 2024 17:05:33 +0400
Subject: wip

---
 graph-checker/src/graph.rs | 56 +++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 51 insertions(+), 5 deletions(-)

(limited to 'graph-checker/src/graph.rs')

diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
index a4390d4..fd6fa63 100644
--- a/graph-checker/src/graph.rs
+++ b/graph-checker/src/graph.rs
@@ -121,6 +121,26 @@ fn iterate(n: usize) -> Vec<Vec<u32>> {
     return components;
 }
 
+impl Cutset {
+    pub fn is_dominating_in(&self, g: &Graph) -> bool {
+        'others: for ov in 0..self.graph.size {
+            if self.vertices[ov] == 1 {
+                continue;
+            }
+            for cv in 0..self.graph.size {
+                if self.vertices[cv] == 0 {
+                    continue;
+                }
+                if g.matrix[ov][cv] == 1 {
+                    continue 'others;
+                }
+            }
+            return false;
+        }
+        return true;
+    }
+}
+
 impl Graph {
     pub fn to_g6(&self) -> String {
         let mut g = vec![0; self.size];
@@ -253,13 +273,39 @@ impl Graph {
         return max_cutset.unwrap();
     }
 
-    fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
-        visited[*vertex] = 1;
+    pub 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);
+            if visited[i] == 0 && self.matrix[vertex][i] != 0 {
+                self.dfs(i, visited);
+            }
+        }
+    }
+
+    pub fn get_geodesics(&self, from: usize, to: usize) -> Vec<Vec<usize>> {
+        fn dfs(
+            g: &Graph,
+            next: usize,
+            to: usize,
+            path: Vec<usize>,
+            paths: &mut Vec<Vec<usize>>,
+        ) {
+            if next == to {
+                paths.push(path.clone());
+                return;
+            }
+            for i in 0..g.size {
+                if g.matrix[next][i] != 0 {
+                    let mut p = path.clone();
+                    p.push(i);
+                    dfs(g, i, to, p, paths);
+                }
             }
         }
+        let mut paths = Vec::new();
+        dfs(self, from, to, vec![from], &mut paths);
+        let d = paths.iter().map(Vec::len).min().unwrap();
+        return paths.into_iter().filter(|p| p.len() == d).collect();
     }
 
     fn count_components_partial(&self, included_vertices: &Vec<u32>) -> usize {
@@ -278,7 +324,7 @@ impl Graph {
                     break;
                 }
             }
-            self.dfs(&next, &mut visited);
+            self.dfs(next, &mut visited);
             count += 1;
         }
         return count;
-- 
cgit v1.2.3