diff options
| -rw-r--r-- | graph-checker/Cargo.toml | 2 | ||||
| -rw-r--r-- | graph-checker/nauty/geng-iter.c | 6 | ||||
| -rw-r--r-- | graph-checker/src/geng.rs | 43 | ||||
| -rw-r--r-- | graph-checker/src/graph.rs | 29 | ||||
| -rw-r--r-- | graph-checker/src/main.rs | 13 |
5 files changed, 63 insertions, 30 deletions
diff --git a/graph-checker/Cargo.toml b/graph-checker/Cargo.toml index e2e9bfc..3b07487 100644 --- a/graph-checker/Cargo.toml +++ b/graph-checker/Cargo.toml @@ -2,6 +2,8 @@ name = "graph-checker" version = "0.1.0" edition = "2021" +links = "nauty" +build = "build.rs" [dependencies] rayon = "1.10.0" diff --git a/graph-checker/nauty/geng-iter.c b/graph-checker/nauty/geng-iter.c index e812f49..4a3ddd9 100644 --- a/graph-checker/nauty/geng-iter.c +++ b/graph-checker/nauty/geng-iter.c @@ -11,7 +11,7 @@ #pragma GCC diagnostic ignored "-Wdeprecated-declarations" void -printgraph(graph *g, int n) +fill_matrix(graph *g, int n, int **mat) { set *gi; for (int i = 0; i < n; ++i) @@ -20,11 +20,9 @@ printgraph(graph *g, int n) for (int j = 0; j < n; ++j) { int q = ISELEMENT(gi, j); - printf("%i ", q); + mat[i][j] = q; } - printf("\n"); } - printf("\n"); } // TODO: probably don't need to name this function with macro diff --git a/graph-checker/src/geng.rs b/graph-checker/src/geng.rs index a998b28..872c6ec 100644 --- a/graph-checker/src/geng.rs +++ b/graph-checker/src/geng.rs @@ -1,6 +1,9 @@ +use std::ffi::{c_char, CStr}; use std::iter::Iterator; use std::ptr; +use crate::graph::Graph; + #[allow(non_camel_case_types)] enum geng_iterator {} @@ -12,13 +15,15 @@ extern "C" { ); 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 fill_matrix(g: *const u32, n: usize, mat: *mut *mut u32); + fn ntog6(g: *const u32, m: usize, n: usize) -> *const c_char; } -fn print_graph(g: Vec<u32>, n: usize) { - unsafe { - printgraph(g.as_ptr(), n); - } +pub fn get_g6(g: Vec<u32>, n: usize) -> String { + let s = unsafe { ntog6(g.as_ptr(), 1, n) }; + // TODO: free allocated s? ^ + let s = unsafe { CStr::from_ptr(s) }; + s.to_str().unwrap().trim().to_string() } pub struct GengIterator { @@ -27,7 +32,7 @@ pub struct GengIterator { } impl GengIterator { - fn new(n: usize) -> GengIterator { + pub fn new(n: usize) -> GengIterator { let iter = unsafe { let iter: *mut geng_iterator = ptr::null_mut(); geng_iterator_create(&iter, n, 10000); @@ -38,17 +43,31 @@ impl GengIterator { } impl Iterator for &GengIterator { - type Item = Vec<u32>; + type Item = Graph; fn next(&mut self) -> Option<Self::Item> { let mut g = vec![0; self.size]; - let res; - unsafe { + let res = unsafe { let ptr: *const geng_iterator = &*self.iter; - res = geng_iterator_next(ptr, g.as_mut_ptr()) - } + geng_iterator_next(ptr, g.as_mut_ptr()) + }; if res { - Some(g) + let mut mat = vec![vec![0; self.size]; self.size]; + unsafe { + fill_matrix( + g.as_ptr(), + self.size, + mat.iter_mut() + .map(Vec::as_mut_ptr) + .collect::<Vec<*mut u32>>() + .as_mut_ptr(), + ); + } + + Some(Graph { + size: self.size, + matrix: mat, + }) } else { None } diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs index dd8a6f4..67dbb59 100644 --- a/graph-checker/src/graph.rs +++ b/graph-checker/src/graph.rs @@ -4,13 +4,13 @@ use std::fmt; #[derive(Clone, PartialEq, Eq)] pub struct Graph { pub size: usize, - pub matrix: Vec<Vec<i32>>, + pub matrix: Vec<Vec<u32>>, } #[derive(Clone, PartialEq, Eq, Debug)] pub struct Cutset { pub cardinality: usize, - pub vertices: Vec<i32>, + pub vertices: Vec<u32>, pub graph: Graph, } @@ -73,10 +73,10 @@ fn trim_cutset(cutset: &Cutset) -> Graph { }; } -fn iterate(n: usize) -> Vec<Vec<i32>> { +fn iterate(n: usize) -> Vec<Vec<u32>> { let mut components = Vec::new(); - let mut v: Vec<i32> = vec![0; n]; + let mut v: Vec<u32> = vec![0; n]; loop { let mut sum: usize = 0; for i in &v { @@ -104,6 +104,19 @@ fn iterate(n: usize) -> Vec<Vec<i32>> { } impl Graph { + pub fn to_g6(&self) -> String { + let mut g = vec![0; self.size]; + for i in 0..self.size { + let mut row: u32 = 0; + for j in 0..self.size { + row |= self.matrix[i][j] << (31 - j); + } + g[i] = row; + } + + crate::geng::get_g6(g, self.size) + } + pub fn from_g6(line: &String) -> Graph { let mut chars: Vec<u8> = Vec::new(); for character in line.chars() { @@ -112,11 +125,11 @@ impl Graph { let size = chars[0] as usize; let bytes = &chars[1..]; - let mut matrix: Vec<Vec<i32>> = vec![vec![0; size]; size]; + let mut matrix: Vec<Vec<u32>> = vec![vec![0; size]; size]; let mut i = 0; for col in 1..size { for row in 0..col { - let bit: i32 = (bytes[i / 6] >> (5 - i % 6) & 1) as i32; + let bit: u32 = (bytes[i / 6] >> (5 - i % 6) & 1) as u32; matrix[row][col] = bit; matrix[col][row] = bit; i += 1; @@ -195,7 +208,7 @@ impl Graph { } } } - let cardinality = vertices.iter().sum::<i32>() as usize; + let cardinality = vertices.iter().sum::<u32>() as usize; cs.push(Cutset { cardinality, vertices: vertices.clone(), @@ -231,7 +244,7 @@ impl Graph { } } - fn count_components_partial(&self, included_vertices: &Vec<i32>) -> usize { + fn count_components_partial(&self, included_vertices: &Vec<u32>) -> usize { let mut visited = vec![0; self.size]; for i in 0..included_vertices.len() { if included_vertices[i] == 0 { diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs index 628ce92..646cca0 100644 --- a/graph-checker/src/main.rs +++ b/graph-checker/src/main.rs @@ -1,4 +1,4 @@ -use std::io::{self, BufRead}; +// use std::io::{self, BufRead}; use std::time::Instant; mod graph; @@ -7,6 +7,9 @@ use crate::graph::Graph; mod theorems; use crate::theorems::{basic, forbidden, toughness}; +mod geng; +use crate::geng::GengIterator; + struct Counters { graphs: i32, tough_1: i32, @@ -56,16 +59,14 @@ impl Counters { } fn main() { - let stdin = io::stdin(); + let gi = GengIterator::new(4); let mut time = 0; let mut counters = Counters::new(); - for line in stdin.lock().lines() { - let line = line.unwrap(); - - let g = Graph::from_g6(&line); + for g in &gi { counters.graphs += 1; + let line = g.to_g6(); let start = Instant::now(); let closure = g.get_closure(); |