1 files changed, 69 insertions, 0 deletions
diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
index 6a49624..7ba6cb4 100644
--- a/graph-checker/src/graph.rs
+++ b/graph-checker/src/graph.rs
@@ -1,3 +1,4 @@
+use std::collections::HashSet;
 use std::fmt;
 
 #[derive(Clone, PartialEq, Eq)]
@@ -102,6 +103,17 @@ impl Graph {
         return min;
     }
 
+    pub fn degree_vector(&self) -> Vec<usize> {
+        let mut set = HashSet::new();
+        for i in 0..self.size {
+            let d = self.degree(i);
+            set.insert(d);
+        }
+        let mut vec = Vec::from_iter(set.into_iter());
+        vec.sort_by(|a, b| b.cmp(a));
+        return vec;
+    }
+
     pub fn get_closure_traced(&self, trace_steps: bool) -> Graph {
         let mut step = if trace_steps { 2 } else { 1 };
 
@@ -260,4 +272,61 @@ impl Graph {
         }
         return true;
     }
+
+    fn swap_vertices(&mut self, a: usize, b: usize) {
+        let n = self.size;
+        let ab = self.matrix[a][b];
+        for i in 0..n {
+            let ai = self.matrix[a][i];
+            let bi = self.matrix[b][i];
+            self.matrix[a][i] = bi;
+            self.matrix[i][a] = bi;
+            self.matrix[b][i] = ai;
+            self.matrix[i][b] = ai;
+        }
+        self.matrix[b][b] = 0;
+        self.matrix[a][a] = 0;
+        self.matrix[a][b] = ab;
+        self.matrix[b][a] = ab;
+    }
+
+    pub fn is_isomorphic(&self, other: &Graph) -> bool {
+        if self.size != other.size {
+            return false;
+        }
+
+        let mut g2 = other.clone();
+        if self == &g2 {
+            return true;
+        }
+
+        if self.degree_vector() != other.degree_vector() {
+            return false;
+        }
+
+        let n = self.size;
+        let mut c = vec![0; n];
+
+        let mut i = 0;
+        while i < n {
+            if c[i] < i {
+                if i % 2 == 0 {
+                    g2.swap_vertices(0, i);
+                } else {
+                    g2.swap_vertices(c[i], i);
+                }
+
+                if self == &g2 {
+                    return true;
+                }
+
+                c[i] += 1;
+                i = 1;
+            } else {
+                c[i] = 0;
+                i += 1;
+            }
+        }
+        return false;
+    }
 }