wip

1 files changed, 63 insertions, 0 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;