Restructured project into multiple files

1 files changed, 143 insertions, 0 deletions

diff --git a/graph-checker/src/theorems/basic.rs b/graph-checker/src/theorems/basic.rs
new file mode 100644
index 0000000..41d5221
--- /dev/null
+++ b/graph-checker/src/theorems/basic.rs
@@ -0,0 +1,143 @@
+use crate::Graph;
+
+pub fn dirac_theorem(g: &Graph) -> bool {
+    for vertex in 0..g.size {
+        if (g.degree(vertex) as f64) < g.size as f64 / 2.0 {
+            return false;
+        }
+    }
+    return true;
+}
+
+pub fn ore_theorem(g: &Graph) -> bool {
+    for v1 in 0..g.size {
+        for v2 in 0..g.size {
+            if v1 == v2 || g.matrix[v1][v2] != 0 {
+                continue;
+            }
+            let d1 = g.degree(v1);
+            let d2 = g.degree(v2);
+            if d1 + d2 < g.size {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
+pub fn posa_theorem(g: &Graph) -> bool {
+    let mut degrees = Vec::new();
+    for v in 0..g.size {
+        degrees.push(g.degree(v));
+    }
+
+    let end = if g.size % 2 == 0 {
+        g.size / 2
+    } else {
+        (g.size - 1) / 2
+    };
+
+    for k in 1..end {
+        let mut cnt = 0;
+        for d in &degrees {
+            if *d <= k {
+                cnt += 1;
+            }
+        }
+        if cnt >= k {
+            return false;
+        }
+    }
+    if g.size % 2 != 0 {
+        let mut cnt = 0;
+        for d in &degrees {
+            if *d <= end {
+                cnt += 1;
+            }
+        }
+        if cnt > end {
+            return false;
+        }
+    }
+    return true;
+}
+
+pub fn bondy_chvatal_hamiltonian_cycle(graph: &Graph) -> Vec<usize> {
+    let closure = graph.get_closure_traced(true);
+
+    let mut cycle = Vec::new();
+    for i in 0..graph.size - 1 {
+        cycle.push(i + 1);
+    }
+    cycle.push(0);
+
+    loop {
+        let mut start = 0;
+        let mut m = 0;
+
+        let mut end = start;
+        let mut new_start = start;
+        let mut current = start;
+        loop {
+            let next = cycle[current];
+            let val = closure.matrix[current][next];
+            // println!("{current} -> {next} = {val}");
+            if val > m {
+                m = val;
+                end = current;
+                new_start = next;
+            }
+            current = next;
+            if current == start {
+                break;
+            }
+        }
+        if m == 1 {
+            break;
+        }
+        // println!("New start: {new_start}, end: {end}, m = {m}");
+        start = new_start;
+
+        let mut s = start;
+        let mut current = cycle[start];
+        while current != end {
+            let next = cycle[current];
+            let u1 = closure.matrix[start][next];
+            let u2 = closure.matrix[end][current];
+            if u1 < m && u2 < m {
+                s = current;
+                break;
+            }
+            current = next;
+        }
+        // println!("s = {s}");
+
+        let mut new_cycle = Vec::new();
+        new_cycle.push(start);
+        let mut current = cycle[s];
+        while current != end {
+            new_cycle.push(current);
+            current = cycle[current];
+        }
+        new_cycle.push(end);
+        {
+            let mut tmp = Vec::new();
+            let mut current = cycle[start];
+            while current != s {
+                tmp.push(current);
+                current = cycle[current];
+            }
+            tmp.push(s);
+            tmp.reverse();
+            for i in tmp {
+                new_cycle.push(i);
+            }
+        }
+        for i in 0..graph.size - 1 {
+            cycle[new_cycle[i]] = new_cycle[i + 1];
+        }
+        cycle[new_cycle[graph.size - 1]] = new_cycle[0];
+    }
+
+    return cycle;
+}