wip

2 files changed, 38 insertions, 348 deletions

diff --git a/graph-checker/src/compute.rs b/graph-checker/src/compute.rs
index b14c2cd..2d0ddcc 100644
--- a/graph-checker/src/compute.rs
+++ b/graph-checker/src/compute.rs
@@ -1,329 +1,79 @@
-use crate::graph::{Graph, GraphProfile};
-use crate::theorems::{basic, forbidden, toughness};
+use crate::graph::Graph;
 
-pub fn dominating_numbers(g: Graph) -> (String, Option<u32>, u32) {
+pub fn dominating_numbers(g: Graph) -> (String, Option<u32>, Option<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;
+    let mut min_size = g.size as u32;
 
     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 geodesics = Vec::new();
         let mut visited = vec![0; g.size];
         for a in 0..cs.graph.size {
-            if cs.vertices[a] == 1 {
+            if cs.vertices[a] == 0 {
                 continue;
             }
-            for b in 0..cs.graph.size {
-                if cs.vertices[b] == 1 {
+            for b in a..cs.graph.size {
+                if cs.vertices[b] == 0 {
                     continue;
                 }
                 if a != b {
-                    // let mut gds = g.get_geodesics(a, b);
                     for geod in g.get_geodesics(a, b) {
                         for i in geod {
                             visited[i] = 1;
                         }
                     }
-                    // geodesics.append(&mut gds);
                 }
             }
         }
         if visited.iter().sum::<usize>() == g.size {
             geodesic_sets.push(cs.vertices.clone());
-        }
-    }
-
-    // println!("geodesic_sets = {}", geodesic_sets.len());
-    let mut fg = g.size as u32;
-    // println!("start");
-    for i in 0..geodesic_sets.len() {
-        let check = &geodesic_sets[i];
-        // println!("{:?}", check);
-        let mut verts = check.clone();
-        for j in 0..geodesic_sets.len() {
-            if i == j {
-                continue;
+            let tmp = cs.vertices.into_iter().sum::<u32>();
+            if tmp < min_size {
+                min_size = tmp;
             }
-            let set = &geodesic_sets[j];
-            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");
 
-    if fg != 0 && fg != g.size as u32 && fg != 1 {
-        println!("{line} {independent_dominating:?} {fg}");
-    }
+    let geodesic_sets: Vec<_> = geodesic_sets
+        .into_iter()
+        .filter(|s| s.iter().sum::<u32>() == min_size)
+        .collect();
 
-    (line, independent_dominating, fg)
-}
-
-pub fn apply_theorems(g: Graph) -> GraphProfile {
-    // let db = db.clone();
-    // counters.graphs += 1;
-    let line = g.to_g6();
-    let mut profile = GraphProfile::new(&line);
-
-    let closure = g.get_closure();
-    let is_complete = closure.is_complete();
-
-    let toughness = if g.is_complete() {
-        f64::MAX
+    let mut fg = None;
+    if geodesic_sets.len() == 1 {
+        fg = Some(0)
     } else {
-        g.get_toughness()
-    };
-
-    if toughness >= 1.0 {
-        profile.insert("tough_1".to_string(), true);
-    }
-    if toughness >= 2.0 {
-        profile.insert("tough_2".to_string(), true);
-    }
-    let min_degree = g.min_degree() as f64;
-
-    if forbidden::theorem3_1(&g) {
-        profile.insert("t3_1".to_string(), true);
-        // println!("g6:t3_1:{}", line);
-    }
-
-    if forbidden::theorem3_2(&g) {
-        profile.insert("t3_2".to_string(), true);
-        // println!("g6:t3_2:{}", line);
-    }
-
-    if forbidden::corollary3_5(&g) {
-        profile.insert("c3_5".to_string(), true);
-        // println!("g6:c3_5:{}", line);
-    }
-    if forbidden::theorem85(&g) {
-        profile.insert("t85".to_string(), true);
-        // println!("g6:t85:{}", line);
-    }
-    if forbidden::theorem86(&g) {
-        profile.insert("t86".to_string(), true);
-        // println!("g6:t86:{}", line);
-    }
-    if forbidden::theorem87(&g) {
-        profile.insert("t87".to_string(), true);
-        // println!("g6:t87:{}", line);
-    }
-    if forbidden::theorem88(&g) {
-        profile.insert("t88".to_string(), true);
-        // println!("g6:t88:{}", line);
-    }
-    if forbidden::theorem96(&g) {
-        profile.insert("t96".to_string(), true);
-        // println!("g6:t96:{}", line);
-    }
-    if forbidden::conjecture17(&g) {
-        profile.insert("conj17".to_string(), true);
-        // println!("g6:conj17:{}", line);
-    }
-    if forbidden::theorem_all_2con(&g) {
-        profile.insert("all_2c".to_string(), true);
-        // println!("g6:all_2c:{}", line);
-    }
-    if toughness::theorem15(&g, toughness, min_degree) {
-        profile.insert("t15_hamiltonian".to_string(), true);
-        // println!("g6:bigalke-jung:{}", line);
-    }
-    if toughness::theorem25(&g, toughness, min_degree) {
-        profile.insert("t25_hamiltonian".to_string(), true);
-        // println!("g6:bauer:{}", line);
-    }
-    if basic::dirac_theorem(&g) {
-        profile.insert("dirac_hamiltonian".to_string(), true);
-        // println!("g6:dirac:{}", line);
-    }
-    if basic::ore_theorem(&g) {
-        profile.insert("ore_hamiltonian".to_string(), true);
-        // println!("g6:ore:{}", line);
-    }
-    if basic::posa_theorem(&g) {
-        profile.insert("posa_hamiltonian".to_string(), true);
-        // println!("g6:posa:{}", line);
-    }
-    if is_complete {
-        profile.insert("bch_hamiltonian".to_string(), true);
-        // println!("g6:bondy-chvatal:{}", line);
-    }
-
-    if is_complete && false {
-        // println!("Graph: {line}\n{g}");
-
-        let components_count = g.count_components();
-        // println!("Components count: {components_count}");
-        let min_degree = g.min_degree();
-        // println!("Minimal degree: {min_degree}");
-
-        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 = basic::bondy_chvatal_hamiltonian_cycle(&g);
-        print!("Hamiltonian cycle: ");
-        let start = 0;
-        let mut current = start;
-        loop {
-            print!("{}", current + 1);
-            print!(" -> ");
-            current = cycle[current];
-            if current == start {
-                // println!("{}", current + 1);
-                break;
+        for i in 0..geodesic_sets.len() {
+            let check = &geodesic_sets[i];
+            let mut verts = check.clone();
+            for j in 0..geodesic_sets.len() {
+                if i == j {
+                    continue;
+                }
+                let set = &geodesic_sets[j];
+                for v in 0..g.size {
+                    if check[v] == set[v] {
+                        verts[v] = 0;
+                    }
+                }
             }
-        }
-    }
-
-    // let _ = sqlx::query!("INSERT INTO graphs (g6) VALUES (?);", line)
-    //     .execute(&db)
-    //     .await;
-
-    profile
-}
-
-pub async fn async_theorems1(g: Graph) -> GraphProfile {
-    // counters.graphs += 1;
-    let line = g.to_g6();
-    let mut profile = GraphProfile::new(&line);
-
-    let closure = g.get_closure();
-    let is_complete = closure.is_complete();
-
-    let toughness = if g.is_complete() {
-        f64::MAX
-    } else {
-        g.get_toughness()
-    };
-
-    if toughness >= 1.0 {
-        profile.insert("tough_1".to_string(), true);
-    }
-    if toughness >= 2.0 {
-        profile.insert("tough_2".to_string(), true);
-    }
-    let min_degree = g.min_degree() as f64;
-
-    if forbidden::theorem3_1(&g) {
-        profile.insert("t3_1".to_string(), true);
-        // println!("g6:t3_1:{}", line);
-    }
-
-    if forbidden::theorem3_2(&g) {
-        profile.insert("t3_2".to_string(), true);
-        // println!("g6:t3_2:{}", line);
-    }
-
-    if forbidden::corollary3_5(&g) {
-        profile.insert("c3_5".to_string(), true);
-        // println!("g6:c3_5:{}", line);
-    }
-    if forbidden::theorem85(&g) {
-        profile.insert("t85".to_string(), true);
-        // println!("g6:t85:{}", line);
-    }
-    if forbidden::theorem86(&g) {
-        profile.insert("t86".to_string(), true);
-        // println!("g6:t86:{}", line);
-    }
-    if forbidden::theorem87(&g) {
-        profile.insert("t87".to_string(), true);
-        // println!("g6:t87:{}", line);
-    }
-    if forbidden::theorem88(&g) {
-        profile.insert("t88".to_string(), true);
-        // println!("g6:t88:{}", line);
-    }
-    if forbidden::theorem96(&g) {
-        profile.insert("t96".to_string(), true);
-        // println!("g6:t96:{}", line);
-    }
-    if forbidden::conjecture17(&g) {
-        profile.insert("conj17".to_string(), true);
-        // println!("g6:conj17:{}", line);
-    }
-    if forbidden::theorem_all_2con(&g) {
-        profile.insert("all_2c".to_string(), true);
-        // println!("g6:all_2c:{}", line);
-    }
-    if toughness::theorem15(&g, toughness, min_degree) {
-        profile.insert("t15_hamiltonian".to_string(), true);
-        // println!("g6:bigalke-jung:{}", line);
-    }
-    if toughness::theorem25(&g, toughness, min_degree) {
-        profile.insert("t25_hamiltonian".to_string(), true);
-        // println!("g6:bauer:{}", line);
-    }
-    if basic::dirac_theorem(&g) {
-        profile.insert("dirac_hamiltonian".to_string(), true);
-        // println!("g6:dirac:{}", line);
-    }
-    if basic::ore_theorem(&g) {
-        profile.insert("ore_hamiltonian".to_string(), true);
-        // println!("g6:ore:{}", line);
-    }
-    if basic::posa_theorem(&g) {
-        profile.insert("posa_hamiltonian".to_string(), true);
-        // println!("g6:posa:{}", line);
-    }
-    if is_complete {
-        profile.insert("bch_hamiltonian".to_string(), true);
-        // println!("g6:bondy-chvatal:{}", line);
-    }
-
-    if is_complete && false {
-        // println!("Graph: {line}\n{g}");
-
-        let components_count = g.count_components();
-        // println!("Components count: {components_count}");
-        let min_degree = g.min_degree();
-        // println!("Minimal degree: {min_degree}");
-
-        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 = basic::bondy_chvatal_hamiltonian_cycle(&g);
-        print!("Hamiltonian cycle: ");
-        let start = 0;
-        let mut current = start;
-        loop {
-            print!("{}", current + 1);
-            print!(" -> ");
-            current = cycle[current];
-            if current == start {
-                // println!("{}", current + 1);
-                break;
+            let new_fg = verts.iter().sum::<u32>();
+            if new_fg > 0 {
+                if new_fg < fg.unwrap_or(g.size as u32) {
+                    fg = Some(new_fg);
+                }
             }
         }
     }
 
-    // let _ =
-    //     sqlx::query!("INSERT INTO graphs (g6) VALUES (?);", line)
-    //         .execute(&db)
-    //         .await;
+    println!("{line} {independent_dominating:?} {fg:?}");
 
-    profile
+    (line, independent_dominating, fg)
 }
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index f7aec5c..677e037 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -6,10 +6,6 @@ use std::time::Instant;
 use tokio;
 
 mod graph;
-use crate::graph::Graph;
-
-mod theorems;
-// use crate::theorems::{basic, forbidden, toughness};
 
 mod geng;
 use crate::geng::GengIterator;
@@ -31,44 +27,18 @@ async fn main() -> Result<(), sqlx::Error> {
     .execute(&db)
     .await;
 
-    // let mut counters = Arc::new(Mutex::new(Counters::new()));
-
-    // gi.par_bridge().for_each(|_| {});
-
     let gi = GengIterator::new(6);
 
-    // 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();
+    // 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);
-            }
+            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
     //     .par_bridge()
@@ -80,35 +50,5 @@ async fn main() -> Result<(), sqlx::Error> {
     // println!("len = {}", res.len());
     // println!("Time elapsed: {}s", time as f64 / 1e9);
 
-    /*
-    println!("Total count of graphs: {}", counters.graphs);
-    println!("Count of 1-tough graphs: {}", counters.tough_1);
-    println!("Count of 2-tough graphs: {}", counters.tough_2);
-    println!(
-        "Count of Dirac's Hamiltonian graphs: {}",
-        counters.dirac_hamiltonian
-    );
-    println!(
-        "Count of Ore's Hamiltonian graphs: {}",
-        counters.ore_hamiltonian
-    );
-    println!(
-        "Count of Posa's Hamiltonian graphs: {}",
-        counters.posa_hamiltonian
-    );
-    println!(
-        "Count of Bondy-Chvatal Hamiltonian graphs: {}",
-        counters.bch_hamiltonian
-    );
-    println!(
-        "Count of Theorem 15 Hamiltonian graphs: {}",
-        counters.t15_hamiltonian
-    );
-    println!(
-        "Count of Theorem 25 Hamiltonian graphs: {}",
-        counters.t25_hamiltonian
-    );
-    */
-
     Ok(())
 }