wip

3 files changed, 147 insertions, 21 deletions

diff --git a/graph-checker/src/compute.rs b/graph-checker/src/compute.rs
index b43d64c..a9e88ae 100644
--- a/graph-checker/src/compute.rs
+++ b/graph-checker/src/compute.rs
@@ -1,6 +1,69 @@
 use crate::graph::{Graph, GraphProfile};
 use crate::theorems::{basic, forbidden, toughness};
 
+pub fn dominating_numbers(g: Graph) -> (String, Option<u32>, u32) {
+    let line = g.to_g6();
+    let mut independent_dominating = None;
+
+    let mut smallest_geodesic = None;
+    let mut geodesic_sets = Vec::new();
+
+    let mut done = false;
+
+    for cs in g.cutsets() {
+        if done {
+            break;
+        }
+        let dom = cs.is_dominating_in(&g);
+        let idp = cs.graph.is_independent();
+        if independent_dominating.is_none() && dom && idp {
+            independent_dominating = Some(cs.cardinality as u32);
+        }
+
+        let mut visited = vec![0; g.size];
+        for vx in &cs.vertices {
+            if *vx == 1 {
+                g.dfs(*vx as usize, &mut visited);
+            }
+            if visited.iter().sum::<usize>() == g.size {
+                let geodesic_size: u32 = cs.vertices.iter().sum();
+                if let Some(smallest_geodesic) = smallest_geodesic {
+                    if geodesic_size > smallest_geodesic {
+                        done = true;
+                        break;
+                    }
+                } else {
+                    smallest_geodesic = Some(geodesic_size);
+                }
+                println!("cs {:?}", cs.vertices);
+                geodesic_sets.push(cs.vertices.clone());
+            }
+        }
+    }
+
+    println!("geodesic_sets = {}", geodesic_sets.len());
+    let mut fg = g.size as u32;
+    println!("start");
+    for check in &geodesic_sets {
+        println!("{:?}", check);
+        let mut verts = check.clone();
+        for set in &geodesic_sets {
+            for v in 0..g.size {
+                if check[v] == set[v] {
+                    verts[v] = 0;
+                }
+            }
+        }
+        let new_fg = verts.iter().sum::<u32>();
+        if new_fg < fg {
+            fg = new_fg;
+        }
+    }
+    println!("end");
+
+    (line, independent_dominating, fg)
+}
+
 pub fn apply_theorems(g: Graph) -> GraphProfile {
     // let db = db.clone();
     // counters.graphs += 1;
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;
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index a62143c..bea7d6a 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -35,22 +35,39 @@ async fn main() -> Result<(), sqlx::Error> {
 
     // gi.par_bridge().for_each(|_| {});
 
-    let gi = GengIterator::new(9);
-
-    let start = Instant::now();
-    let tasks: Vec<_> = gi
-        .map(|g| {
-            // let db = db.clone();
-            tokio::spawn(compute::async_theorems1(g))
-        })
-        .collect();
-
-    let res = futures::future::join_all(tasks).await;
-    let elapsed = start.elapsed();
-    let time = elapsed.as_nanos();
-    let res = res.iter().map(|e| e.as_ref().unwrap()).collect::<Vec<_>>();
-    println!("len = {}", res.len());
-    println!("Time elapsed: {}s", time as f64 / 1e9);
+    let gi = GengIterator::new(7);
+
+    // let start = Instant::now();
+    // let tasks: Vec<_> = gi
+    //     .map(|g| {
+    //         // let db = db.clone();
+    //         tokio::spawn(compute::async_theorems1(g))
+    //     })
+    //     .collect();
+
+    // let res: Vec<_> = gi.par_bridge().map(compute::apply_theorems).collect();
+    // let res: Vec<_> =
+    //     gi.par_bridge().map(compute::dominating_numbers).collect();
+    let res: Vec<_> = gi.map(compute::dominating_numbers).collect();
+
+    for pair in &res {
+        if let Some(cardinality) = pair.1 {
+            if pair.2 != 0 {
+                println!("{} {:?} {}", pair.0, cardinality, pair.2);
+            }
+        }
+    }
+
+    // for (a, b) in &res {
+    //     println!("{a} {b:?}");
+    // }
+
+    // let res = futures::future::join_all(tasks).await;
+    // let elapsed = start.elapsed();
+    // let time = elapsed.as_nanos();
+    // let res = res.iter().map(|e| e.as_ref().unwrap()).collect::<Vec<_>>();
+    // println!("len = {}", res.len());
+    // println!("Time elapsed: {}s", time as f64 / 1e9);
 
     // let start = Instant::now();
     // let res = gi