summaryrefslogtreecommitdiff
path: root/graph-checker/src
diff options
context:
space:
mode:
Diffstat (limited to 'graph-checker/src')
-rw-r--r--graph-checker/src/geng.rs65
-rw-r--r--graph-checker/src/graph.rs14
-rw-r--r--graph-checker/src/main.rs244
-rw-r--r--graph-checker/src/theorems/basic.rs3
-rw-r--r--graph-checker/src/theorems/forbidden.rs2
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,
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 11:02:01 +0000