diff options
Diffstat (limited to 'graph-checker/src/main.rs')
| -rw-r--r-- | graph-checker/src/main.rs | 244 |
1 files changed, 129 insertions, 115 deletions
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(); |