summaryrefslogtreecommitdiff
path: root/graph-checker
diff options
context:
space:
mode:
Diffstat (limited to 'graph-checker')
-rw-r--r--graph-checker/src/graph.rs120
-rw-r--r--graph-checker/src/main.rs159
-rw-r--r--graph-checker/src/theorems/forbidden.rs201
3 files changed, 391 insertions, 89 deletions
diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
index 25d7f72..581c522 100644
--- a/graph-checker/src/graph.rs
+++ b/graph-checker/src/graph.rs
@@ -51,6 +51,31 @@ impl fmt::Debug for Graph {
}
}
+// TODO: impl Cutset
+fn trim_cutset(cutset: &Cutset) -> Graph {
+ let mut mat = vec![vec![0; cutset.cardinality]; cutset.cardinality];
+
+ let mut i = 0;
+ for vi in 0..cutset.graph.size {
+ if cutset.vertices[vi] == 0 {
+ continue;
+ }
+ let mut j = 0;
+ for vj in 0..cutset.graph.size {
+ if cutset.vertices[vj] == 0 {
+ continue;
+ }
+ mat[i][j] = cutset.graph.matrix[vi][vj];
+ j += 1;
+ }
+ i += 1;
+ }
+ return Graph {
+ size: cutset.cardinality,
+ matrix: mat,
+ };
+}
+
fn iterate(n: usize) -> Vec<Vec<i32>> {
let mut components = Vec::new();
@@ -236,10 +261,29 @@ impl Graph {
self.count_components_partial(&vec![1; self.size])
}
+ pub fn is_connected(&self) -> bool {
+ 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 {
+ vertices[i] = 0;
+ let c = self.count_components_partial(&vertices);
+ vertices[i] = 1;
+
+ if c != 1 {
+ return false;
+ }
+ }
+ 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 {
for j in 0..self.size {
if i == j {
continue;
@@ -258,11 +302,63 @@ 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 {
+ for j in 0..self.size {
+ for k in 0..self.size {
+ if i == j || j == k || i == k {
+ continue;
+ }
+ vertices[i] = 0;
+ vertices[j] = 0;
+ vertices[k] = 0;
+ let c = self.count_components_partial(&vertices);
+ vertices[i] = 1;
+ vertices[j] = 1;
+ vertices[k] = 1;
+
+ if c != 1 {
+ return false;
+ }
+ }
+ }
+ }
+ 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();
+
+ for i in 0..self.size as i32 {
+ if i != vert && self.matrix[i as usize][vert as usize] != 0 {
+ res.push(i);
+ }
+ }
+
+ return res;
+ }
+
+ pub fn is_locally_connected(&self) -> bool {
+ for i in 0..self.size {
+ let neighbors = self.neighbors(i as i32);
+ let mut part = vec![0; self.size];
+ for neighbor in &neighbors {
+ part[*neighbor as usize] = 1;
+ }
+ if self.count_components_partial(&part) != 1 {
+ return false;
+ }
+ }
+ return true;
+ }
+
pub fn get_closure(&self) -> Graph {
self.get_closure_traced(false)
}
@@ -378,30 +474,6 @@ impl Graph {
}
pub fn is_free_of(&self, graphs: &Vec<Graph>) -> bool {
- fn trim_cutset(cutset: &Cutset) -> Graph {
- let mut mat = vec![vec![0; cutset.cardinality]; cutset.cardinality];
-
- let mut i = 0;
- for vi in 0..cutset.graph.size {
- if cutset.vertices[vi] == 0 {
- continue;
- }
- let mut j = 0;
- for vj in 0..cutset.graph.size {
- if cutset.vertices[vj] == 0 {
- continue;
- }
- mat[i][j] = cutset.graph.matrix[vi][vj];
- j += 1;
- }
- i += 1;
- }
- return Graph {
- size: cutset.cardinality,
- matrix: mat,
- };
- }
-
for cutset in self.cutsets() {
let subg = trim_cutset(&cutset);
for g in graphs {
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index b3d8602..351fe42 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -55,83 +55,112 @@ fn main() {
let closure = g.get_closure();
let is_complete = closure.is_complete();
- let toughness = if g.is_complete() {
- f64::MAX
- } else {
- g.get_toughness()
- };
+ // 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;
- }
+ // if toughness >= 1.0 {
+ // counters.tough_1 += 1;
+ // }
+ // if toughness >= 2.0 {
+ // counters.tough_2 += 1;
+ // }
- let min_degree = g.min_degree() as f64;
+ // let min_degree = g.min_degree() as f64;
// TODO: add counter
- if forbidden::theorem3_1(&g) {
- println!("g6:t3_1:{}", line);
- }
+ // if forbidden::theorem3_1(&g) {
+ // println!("g6:t3_1:{}", line);
+ // }
- if theorem15(&g, toughness, min_degree) {
- counters.t15_hamiltonian += 1;
- println!("g6:bigalke-jung:{}", line);
- }
+ // TODO: add counter
+ // if forbidden::theorem3_2(&g) {
+ // println!("g6:t3_2:{}", line);
+ // }
- if theorem25(&g, toughness, min_degree) {
- counters.t25_hamiltonian += 1;
- println!("g6:bauer:{}", 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 theorem15(&g, toughness, min_degree) {
+ // counters.t15_hamiltonian += 1;
+ // println!("g6:bigalke-jung:{}", line);
+ // }
+
+ // if theorem25(&g, toughness, min_degree) {
+ // counters.t25_hamiltonian += 1;
+ // println!("g6:bauer:{}", line);
+ // }
if dirac_theorem(&g) {
counters.dirac_hamiltonian += 1;
println!("g6:dirac:{}", line);
}
- if ore_theorem(&g) {
- counters.ore_hamiltonian += 1;
- println!("g6:ore:{}", line);
- }
-
- if 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 = 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;
- }
- }
- }
+ // if ore_theorem(&g) {
+ // counters.ore_hamiltonian += 1;
+ // println!("g6:ore:{}", line);
+ // }
+
+ // if 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 = 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/forbidden.rs b/graph-checker/src/theorems/forbidden.rs
index 615cdb1..8c70916 100644
--- a/graph-checker/src/theorems/forbidden.rs
+++ b/graph-checker/src/theorems/forbidden.rs
@@ -25,3 +25,204 @@ pub fn theorem3_1(g: &Graph) -> bool {
return g.is_2_connected() && g.is_free_of(&forbidden);
}
+
+pub fn theorem3_2(g: &Graph) -> bool {
+ let claw = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 1, 1],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ ],
+ };
+
+ let forbidden = vec![claw];
+ return g.size >= 3
+ && g.is_connected()
+ && g.is_locally_connected()
+ && g.is_free_of(&forbidden);
+}
+
+pub fn corollary3_5(g: &Graph) -> bool {
+ let claw = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 1, 1],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ ],
+ };
+
+ let ig = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 0, 0],
+ vec![1, 0, 1, 0],
+ vec![0, 1, 0, 1],
+ vec![0, 0, 1, 0],
+ ],
+ };
+
+ let ag = Graph {
+ size: 5,
+ matrix: vec![
+ vec![0, 1, 1, 0, 0],
+ vec![1, 0, 0, 1, 0],
+ vec![1, 0, 0, 0, 1],
+ vec![0, 1, 0, 0, 0],
+ vec![0, 0, 1, 0, 0],
+ ],
+ };
+
+ let is_2 = g.is_2_connected();
+ let claw_free = g.is_free_of(&vec![claw]);
+ return (is_2 && claw_free && g.is_free_of(&vec![ig]))
+ || (is_2 && claw_free && g.is_free_of(&vec![ag]));
+}
+
+// 2003 Gould
+
+pub fn theorem85(g: &Graph) -> bool {
+ let claw = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 1, 1],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ ],
+ };
+
+ let ng = Graph {
+ size: 6,
+ matrix: vec![
+ vec![0, 1, 1, 1, 0, 0],
+ vec![1, 0, 1, 0, 0, 1],
+ vec![1, 1, 0, 0, 1, 0],
+ vec![1, 0, 0, 0, 0, 0],
+ vec![0, 0, 1, 0, 0, 0],
+ vec![0, 1, 0, 0, 0, 0],
+ ],
+ };
+
+ return g.is_2_connected() && g.is_free_of(&vec![claw, ng]);
+}
+
+pub fn theorem86(g: &Graph) -> bool {
+ let claw = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 1, 1],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ ],
+ };
+
+ let p6 = Graph {
+ size: 6,
+ matrix: vec![
+ vec![0, 1, 0, 0, 0, 0],
+ vec![1, 0, 1, 0, 0, 0],
+ vec![0, 1, 0, 1, 0, 0],
+ vec![0, 0, 1, 0, 1, 0],
+ vec![0, 0, 0, 1, 0, 1],
+ vec![0, 0, 0, 0, 1, 0],
+ ],
+ };
+
+ return g.is_2_connected() && g.is_free_of(&vec![claw, p6]);
+}
+
+pub fn theorem87(g: &Graph) -> bool {
+ let claw = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 1, 1],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ ],
+ };
+
+ let z2 = Graph {
+ size: 5,
+ matrix: vec![
+ vec![0, 1, 0, 0, 0],
+ vec![1, 0, 1, 0, 0],
+ vec![0, 1, 0, 1, 1],
+ vec![0, 0, 1, 0, 1],
+ vec![0, 0, 1, 1, 1],
+ ],
+ };
+
+ return g.is_2_connected() && g.is_free_of(&vec![claw, z2]);
+}
+
+pub fn theorem88(g: &Graph) -> bool {
+ let claw = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 1, 1],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ ],
+ };
+
+ let wg = Graph {
+ size: 6,
+ matrix: vec![
+ vec![0, 1, 1, 0, 0, 0],
+ vec![1, 0, 1, 0, 1, 0],
+ vec![1, 1, 0, 1, 0, 0],
+ vec![0, 0, 1, 0, 0, 0],
+ vec![0, 1, 0, 0, 0, 1],
+ vec![0, 0, 0, 0, 1, 0],
+ ],
+ };
+
+ return g.is_2_connected() && g.is_free_of(&vec![claw, wg]);
+}
+
+pub fn theorem96(g: &Graph) -> bool {
+ let claw = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 1, 1],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ ],
+ };
+
+ let ng = Graph {
+ size: 6,
+ matrix: vec![
+ vec![0, 1, 1, 1, 0, 0],
+ vec![1, 0, 1, 0, 0, 1],
+ vec![1, 1, 0, 0, 1, 0],
+ vec![1, 0, 0, 0, 0, 0],
+ vec![0, 0, 1, 0, 0, 0],
+ vec![0, 1, 0, 0, 0, 0],
+ ],
+ };
+
+ return g.is_3_connected() && g.is_free_of(&vec![claw, ng]);
+}
+
+pub fn conjecture17(g: &Graph) -> bool {
+ let claw = Graph {
+ size: 4,
+ matrix: vec![
+ vec![0, 1, 1, 1],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ vec![1, 0, 0, 0],
+ ],
+ };
+
+ return g.is_4_connected() && g.is_free_of(&vec![claw]);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 14:57:37 +0000