feat(guests): Add graph_coloring program

2 files changed, 35 insertions, 0 deletions

diff --git a/guests/graph_coloring/Cargo.toml b/guests/graph_coloring/Cargo.toml
new file mode 100644
index 0000000..180ec35
--- /dev/null
+++ b/guests/graph_coloring/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "zkp"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+guests_macro = { version = "0.1.0", path = "../../guests_macro" }
diff --git a/guests/graph_coloring/src/lib.rs b/guests/graph_coloring/src/lib.rs
new file mode 100644
index 0000000..2feef7f
--- /dev/null
+++ b/guests/graph_coloring/src/lib.rs
@@ -0,0 +1,28 @@
+const VERTICES: usize = 010;
+
+#[guests_macro::proving_entrypoint]
+pub fn start(
+    graph: Vec<Vec<bool>>,
+    colors: u32,
+    coloring: Vec<Vec<u32>>,
+) -> bool {
+    // Does it use the correct amount of colors?
+    let mut max_color = coloring[0][1];
+    for nc in &coloring {
+        if nc[1] > max_color {
+            max_color = nc[1];
+        }
+    }
+
+    let mut ret = max_color + 1 == colors;
+
+    // Is coloring correct?
+    for i in 0..VERTICES {
+        for j in 0..VERTICES {
+            // graph[i][j] -> coloring[i] != coloring[j]
+            ret = ret & (! graph[i][j] | (coloring[i][1] != coloring[j][1]));
+        }
+    }
+
+    ret
+}