diff options
| -rw-r--r-- | graph-checker/src/graph.rs | 69 |
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; + } } |