latest version

5 files changed, 195 insertions, 133 deletions

diff --git a/graph-checker/src/geng.rs b/graph-checker/src/geng.rs
new file mode 100644
index 0000000..a998b28
--- /dev/null
+++ b/graph-checker/src/geng.rs
@@ -0,0 +1,65 @@
+use std::iter::Iterator;
+use std::ptr;
+
+#[allow(non_camel_case_types)]
+enum geng_iterator {}
+
+extern "C" {
+    fn geng_iterator_create(
+        iter: *const *mut geng_iterator,
+        graph_size: usize,
+        batch_size: usize,
+    );
+    fn geng_iterator_next(iter: *const geng_iterator, g: *mut u32) -> bool;
+    fn geng_iterator_destroy(iter: *const geng_iterator);
+    fn printgraph(g: *const u32, n: usize);
+}
+
+fn print_graph(g: Vec<u32>, n: usize) {
+    unsafe {
+        printgraph(g.as_ptr(), n);
+    }
+}
+
+pub struct GengIterator {
+    pub size: usize,
+    iter: Box<geng_iterator>,
+}
+
+impl GengIterator {
+    fn new(n: usize) -> GengIterator {
+        let iter = unsafe {
+            let iter: *mut geng_iterator = ptr::null_mut();
+            geng_iterator_create(&iter, n, 10000);
+            Box::from_raw(iter)
+        };
+        GengIterator { size: n, iter }
+    }
+}
+
+impl Iterator for &GengIterator {
+    type Item = Vec<u32>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let mut g = vec![0; self.size];
+        let res;
+        unsafe {
+            let ptr: *const geng_iterator = &*self.iter;
+            res = geng_iterator_next(ptr, g.as_mut_ptr())
+        }
+        if res {
+            Some(g)
+        } else {
+            None
+        }
+    }
+}
+
+impl Drop for GengIterator {
+    fn drop(&mut self) {
+        unsafe {
+            let ptr: *const geng_iterator = &*self.iter;
+            geng_iterator_destroy(ptr);
+        }
+    }
+}
diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
index 581c522..dd8a6f4 100644
--- a/graph-checker/src/graph.rs
+++ b/graph-checker/src/graph.rs
@@ -1,7 +1,6 @@
 use std::collections::HashSet;
 use std::fmt;
 
-// TODO: manual Debug impl
 #[derive(Clone, PartialEq, Eq)]
 pub struct Graph {
     pub size: usize,
@@ -32,7 +31,6 @@ impl fmt::Display for Graph {
     }
 }
 
-// TODO: manual Debug impl
 impl fmt::Debug for Graph {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "\n")?;
@@ -51,7 +49,6 @@ impl fmt::Debug for Graph {
     }
 }
 
-// TODO: impl Cutset
 fn trim_cutset(cutset: &Cutset) -> Graph {
     let mut mat = vec![vec![0; cutset.cardinality]; cutset.cardinality];
 
@@ -112,7 +109,6 @@ impl Graph {
         for character in line.chars() {
             chars.push((character as i32 - 63) as u8);
         }
-        // TODO: spec allows multi-byte vector size
         let size = chars[0] as usize;
         let bytes = &chars[1..];
 
@@ -265,7 +261,6 @@ impl Graph {
         self.count_components() == 1
     }
 
-    // TODO: replace with is_n_connected
     pub fn is_2_connected(&self) -> bool {
         let mut vertices = vec![1; self.size];
         for i in 0..self.size {
@@ -280,7 +275,6 @@ impl Graph {
         return true;
     }
 
-    // TODO: replace with is_n_connected
     pub fn is_3_connected(&self) -> bool {
         let mut vertices = vec![1; self.size];
         for i in 0..self.size {
@@ -302,7 +296,6 @@ impl Graph {
         return true;
     }
 
-    // TODO: replace with is_n_connected
     pub fn is_4_connected(&self) -> bool {
         let mut vertices = vec![1; self.size];
         for i in 0..self.size {
@@ -328,11 +321,6 @@ impl Graph {
         return true;
     }
 
-    pub fn is_n_connected(&self, n: usize) -> bool {
-        // TODO: implement
-        todo!();
-    }
-
     pub fn neighbors(&self, vert: i32) -> Vec<i32> {
         let mut res = Vec::new();
 
@@ -378,7 +366,7 @@ impl Graph {
 
     pub fn get_toughness(&self) -> f64 {
         let mut left: f64 = 0.0;
-        let mut right: f64 = 1024.0; // Reasonable limit
+        let mut right: f64 = 1024.0;
         let eps: f64 = 1e-9;
 
         while (right - left).abs() > eps {
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index 58b6a1c..628ce92 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -17,6 +17,16 @@ struct Counters {
     dirac_hamiltonian: i32,
     ore_hamiltonian: i32,
     posa_hamiltonian: i32,
+    t3_1: i32,
+    t3_2: i32,
+    c3_5: i32,
+    t85: i32,
+    t86: i32,
+    t87: i32,
+    t88: i32,
+    t96: i32,
+    conj17: i32,
+    all_2c: i32,
 }
 
 impl Counters {
@@ -31,6 +41,16 @@ impl Counters {
             dirac_hamiltonian: 0,
             ore_hamiltonian: 0,
             posa_hamiltonian: 0,
+            t3_1: 0,
+            t3_2: 0,
+            c3_5: 0,
+            t85: 0,
+            t86: 0,
+            t87: 0,
+            t88: 0,
+            t96: 0,
+            conj17: 0,
+            all_2c: 0,
         };
     }
 }
@@ -50,121 +70,115 @@ fn main() {
         let start = Instant::now();
         let closure = g.get_closure();
         let is_complete = closure.is_complete();
-        println!("Graph:\n{g}");
-        println!("Closure:\n{closure}");
-        println!("{is_complete}");
-
-        // let toughness = if g.is_complete() {
-        //     f64::MAX
-        // } else {
-        //     g.get_toughness()
-        // };
-        // println!("{toughness}");
-
-        // if toughness >= 1.0 {
-        //     counters.tough_1 += 1;
-        // }
-        // if toughness >= 2.0 {
-        //     counters.tough_2 += 1;
-        // }
-
-        // let min_degree = g.min_degree() as f64;
-        // println!("{min_degree}");
-
-        // TODO: add counter
-        // if forbidden::theorem3_1(&g) {
-        //     println!("g6:t3_1:{}", line);
-        // }
-
-        // TODO: add counter
-        // if forbidden::theorem3_2(&g) {
-        //     println!("g6:t3_2:{}", line);
-        // }
-
-        // TODO: add counter
-        // if forbidden::corollary3_5(&g) {
-        //     println!("g6:c3_5:{}", line);
-        // }
-
-        // if forbidden::theorem85(&g) {
-        //     println!("g6:t85:{}", line);
-        // }
-        // if forbidden::theorem86(&g) {
-        //     println!("g6:t86:{}", line);
-        // }
-        // if forbidden::theorem87(&g) {
-        //     println!("g6:t87:{}", line);
-        // }
-        // if forbidden::theorem88(&g) {
-        //     println!("g6:t88:{}", line);
-        // }
-        // if forbidden::theorem96(&g) {
-        //     println!("g6:t96:{}", line);
-        // }
-        // if forbidden::conjecture17(&g) {
-        //     println!("g6:conj17:{}", line);
-        // }
-        // if forbidden::theorem_all_2con(&g) {
-        //     println!("g6:all_2c:{}", line);
-        // }
-
-        // if toughness::theorem15(&g, toughness, min_degree) {
-        //     counters.t15_hamiltonian += 1;
-        //     println!("g6:bigalke-jung:{}", line);
-        // }
-
-        // if toughness::theorem25(&g, toughness, min_degree) {
-        //     counters.t25_hamiltonian += 1;
-        //     println!("g6:bauer:{}", line);
-        // }
-
-        // if basic::dirac_theorem(&g) {
-        //     counters.dirac_hamiltonian += 1;
-        //     println!("g6:dirac:{}", line);
-        // }
-
-        // if basic::ore_theorem(&g) {
-        //     counters.ore_hamiltonian += 1;
-        //     println!("g6:ore:{}", line);
-        // }
-
-        // if basic::posa_theorem(&g) {
-        //     counters.posa_hamiltonian += 1;
-        //     println!("g6:posa:{}", line);
-        // }
-
-        // if is_complete {
-        //     counters.bch_hamiltonian += 1;
-        //     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 toughness = if g.is_complete() {
+            f64::MAX
+        } else {
+            g.get_toughness()
+        };
+
+        if toughness >= 1.0 {
+            counters.tough_1 += 1;
+        }
+        if toughness >= 2.0 {
+            counters.tough_2 += 1;
+        }
+        let min_degree = g.min_degree() as f64;
+
+        if forbidden::theorem3_1(&g) {
+            counters.t3_1 += 1;
+            println!("g6:t3_1:{}", line);
+        }
+
+        if forbidden::theorem3_2(&g) {
+            counters.t3_2 += 1;
+            println!("g6:t3_2:{}", line);
+        }
+
+        if forbidden::corollary3_5(&g) {
+            counters.c3_5 += 1;
+            println!("g6:c3_5:{}", line);
+        }
+        if forbidden::theorem85(&g) {
+            counters.t85 += 1;
+            println!("g6:t85:{}", line);
+        }
+        if forbidden::theorem86(&g) {
+            counters.t86 += 1;
+            println!("g6:t86:{}", line);
+        }
+        if forbidden::theorem87(&g) {
+            counters.t87 += 1;
+            println!("g6:t87:{}", line);
+        }
+        if forbidden::theorem88(&g) {
+            counters.t88 += 1;
+            println!("g6:t88:{}", line);
+        }
+        if forbidden::theorem96(&g) {
+            counters.t96 += 1;
+            println!("g6:t96:{}", line);
+        }
+        if forbidden::conjecture17(&g) {
+            counters.conj17 += 1;
+            println!("g6:conj17:{}", line);
+        }
+        if forbidden::theorem_all_2con(&g) {
+            counters.all_2c += 1;
+            println!("g6:all_2c:{}", line);
+        }
+        if toughness::theorem15(&g, toughness, min_degree) {
+            counters.t15_hamiltonian += 1;
+            println!("g6:bigalke-jung:{}", line);
+        }
+        if toughness::theorem25(&g, toughness, min_degree) {
+            counters.t25_hamiltonian += 1;
+            println!("g6:bauer:{}", line);
+        }
+        if basic::dirac_theorem(&g) {
+            counters.dirac_hamiltonian += 1;
+            println!("g6:dirac:{}", line);
+        }
+        if basic::ore_theorem(&g) {
+            counters.ore_hamiltonian += 1;
+            println!("g6:ore:{}", line);
+        }
+        if basic::posa_theorem(&g) {
+            counters.posa_hamiltonian += 1;
+            println!("g6:posa:{}", line);
+        }
+        if is_complete {
+            counters.bch_hamiltonian += 1;
+            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 elapsed = start.elapsed();
         time += elapsed.as_nanos();
diff --git a/graph-checker/src/theorems/basic.rs b/graph-checker/src/theorems/basic.rs
index 41d5221..94c1f16 100644
--- a/graph-checker/src/theorems/basic.rs
+++ b/graph-checker/src/theorems/basic.rs
@@ -81,7 +81,6 @@ pub fn bondy_chvatal_hamiltonian_cycle(graph: &Graph) -> Vec<usize> {
         loop {
             let next = cycle[current];
             let val = closure.matrix[current][next];
-            // println!("{current} -> {next} = {val}");
             if val > m {
                 m = val;
                 end = current;
@@ -95,7 +94,6 @@ pub fn bondy_chvatal_hamiltonian_cycle(graph: &Graph) -> Vec<usize> {
         if m == 1 {
             break;
         }
-        // println!("New start: {new_start}, end: {end}, m = {m}");
         start = new_start;
 
         let mut s = start;
@@ -110,7 +108,6 @@ pub fn bondy_chvatal_hamiltonian_cycle(graph: &Graph) -> Vec<usize> {
             }
             current = next;
         }
-        // println!("s = {s}");
 
         let mut new_cycle = Vec::new();
         new_cycle.push(start);
diff --git a/graph-checker/src/theorems/forbidden.rs b/graph-checker/src/theorems/forbidden.rs
index 9450b07..925b6f1 100644
--- a/graph-checker/src/theorems/forbidden.rs
+++ b/graph-checker/src/theorems/forbidden.rs
@@ -82,8 +82,6 @@ pub fn corollary3_5(g: &Graph) -> bool {
         || (is_2 && claw_free && g.is_free_of(&vec![ag]));
 }
 
-// 2003 Gould
-
 pub fn theorem85(g: &Graph) -> bool {
     let claw = Graph {
         size: 4,