summaryrefslogtreecommitdiff
path: root/graph-checker/src/compute.rs
diff options
context:
space:
mode:
Diffstat (limited to 'graph-checker/src/compute.rs')
-rw-r--r--graph-checker/src/compute.rs322
1 files changed, 36 insertions, 286 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)
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 12:57:39 +0000