summaryrefslogtreecommitdiff
path: root/graph-checker
diff options
context:
space:
mode:
Diffstat (limited to 'graph-checker')
-rw-r--r--graph-checker/src/compute.rs252
-rw-r--r--graph-checker/src/graph.rs20
-rw-r--r--graph-checker/src/main.rs174
3 files changed, 295 insertions, 151 deletions
diff --git a/graph-checker/src/compute.rs b/graph-checker/src/compute.rs
new file mode 100644
index 0000000..b43d64c
--- /dev/null
+++ b/graph-checker/src/compute.rs
@@ -0,0 +1,252 @@
+use crate::graph::{Graph, GraphProfile};
+use crate::theorems::{basic, forbidden, toughness};
+
+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
+ } 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 _ = 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 _ =
+ // sqlx::query!("INSERT INTO graphs (g6) VALUES (?);", line)
+ // .execute(&db)
+ // .await;
+
+ profile
+}
diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
index 67dbb59..a4390d4 100644
--- a/graph-checker/src/graph.rs
+++ b/graph-checker/src/graph.rs
@@ -1,4 +1,4 @@
-use std::collections::HashSet;
+use std::collections::{HashMap, HashSet};
use std::fmt;
#[derive(Clone, PartialEq, Eq)]
@@ -7,6 +7,24 @@ pub struct Graph {
pub matrix: Vec<Vec<u32>>,
}
+pub struct GraphProfile {
+ g6: String,
+ stats: HashMap<String, bool>,
+}
+
+impl GraphProfile {
+ pub fn new(g6: &String) -> Self {
+ Self {
+ g6: g6.clone(),
+ stats: HashMap::new(),
+ }
+ }
+
+ pub fn insert(&mut self, key: String, value: bool) {
+ self.stats.insert(key, value);
+ }
+}
+
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Cutset {
pub cardinality: usize,
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index 713823f..a62143c 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -1,7 +1,6 @@
// use std::io::{self, BufRead};
use rayon::prelude::*;
use sqlx::migrate::MigrateDatabase;
-use std::collections::HashMap;
// use std::sync::{Arc, Mutex};
use std::time::Instant;
use tokio;
@@ -10,28 +9,12 @@ mod graph;
use crate::graph::Graph;
mod theorems;
-use crate::theorems::{basic, forbidden, toughness};
+// use crate::theorems::{basic, forbidden, toughness};
mod geng;
use crate::geng::GengIterator;
-struct GraphProfile {
- g6: String,
- stats: HashMap<String, bool>,
-}
-
-impl GraphProfile {
- pub fn new(g6: &String) -> Self {
- Self {
- g6: g6.clone(),
- stats: HashMap::new(),
- }
- }
-
- pub fn insert(&mut self, key: String, value: bool) {
- self.stats.insert(key, value);
- }
-}
+mod compute;
#[tokio::main]
async fn main() -> Result<(), sqlx::Error> {
@@ -48,145 +31,37 @@ async fn main() -> Result<(), sqlx::Error> {
.execute(&db)
.await;
- let gi = GengIterator::new(5);
-
- // let mut time = 0;
// let mut counters = Arc::new(Mutex::new(Counters::new()));
// gi.par_bridge().for_each(|_| {});
+ let gi = GengIterator::new(9);
+
+ let start = Instant::now();
let tasks: Vec<_> = gi
.map(|g| {
- let db = db.clone();
- tokio::spawn(async move {
- // counters.graphs += 1;
- let line = g.to_g6();
- let mut profile = GraphProfile::new(&line);
-
- // let start = Instant::now();
- 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 _ =
- sqlx::query!("INSERT INTO graphs (g6) VALUES (?);", line)
- .execute(&db)
- .await;
- })
- // let elapsed = start.elapsed();
- // time += elapsed.as_nanos();
+ // let db = db.clone();
+ tokio::spawn(compute::async_theorems1(g))
})
.collect();
- futures::future::join_all(tasks).await;
+ let res = futures::future::join_all(tasks).await;
+ let elapsed = start.elapsed();
+ let time = elapsed.as_nanos();
+ let res = res.iter().map(|e| e.as_ref().unwrap()).collect::<Vec<_>>();
+ println!("len = {}", res.len());
+ println!("Time elapsed: {}s", time as f64 / 1e9);
+
+ // let start = Instant::now();
+ // let res = gi
+ // .par_bridge()
+ // .map(compute::apply_theorems)
+ // .collect::<Vec<_>>();
+ //
+ // let elapsed = start.elapsed();
+ // let time = elapsed.as_nanos();
+ // println!("len = {}", res.len());
+ // println!("Time elapsed: {}s", time as f64 / 1e9);
/*
println!("Total count of graphs: {}", counters.graphs);
@@ -216,7 +91,6 @@ async fn main() -> Result<(), sqlx::Error> {
"Count of Theorem 25 Hamiltonian graphs: {}",
counters.t25_hamiltonian
);
- println!("Time elapsed: {}s", time as f64 / 1e9);
*/
Ok(())
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 11:24:48 +0000