summaryrefslogtreecommitdiff
path: root/graph-checker
diff options
context:
space:
mode:
Diffstat (limited to 'graph-checker')
-rw-r--r--graph-checker/src/compute.rs13
-rw-r--r--graph-checker/src/graph.rs93
-rw-r--r--graph-checker/src/main.rs1
3 files changed, 51 insertions, 56 deletions
diff --git a/graph-checker/src/compute.rs b/graph-checker/src/compute.rs
index 0beaad9..c3ee046 100644
--- a/graph-checker/src/compute.rs
+++ b/graph-checker/src/compute.rs
@@ -60,14 +60,12 @@ pub async fn dominating_numbers(
if geodesic_sets.len() == 1 {
fg = Some(0)
} else {
- for i in 0..geodesic_sets.len() {
- let check = &geodesic_sets[i];
+ for (i, check) in geodesic_sets.iter().enumerate() {
let mut verts = check.clone();
- for j in 0..geodesic_sets.len() {
+ for (j, set) in geodesic_sets.iter().enumerate() {
if i == j {
continue;
}
- let set = &geodesic_sets[j];
for v in 0..g.size {
if check[v] == set[v] {
verts[v] = 0;
@@ -75,11 +73,10 @@ pub async fn dominating_numbers(
}
}
let new_fg = verts.iter().sum::<u32>();
- if new_fg > 0 {
- if new_fg < fg.unwrap_or(g.size as u32) {
- fg = Some(new_fg);
- }
+ if new_fg > 0 && new_fg < fg.unwrap_or(g.size as u32) {
+ fg = Some(new_fg);
}
+
if let Some(fg) = fg {
if fg == 1 {
break;
diff --git a/graph-checker/src/graph.rs b/graph-checker/src/graph.rs
index cf3dbc0..bc2bc7e 100644
--- a/graph-checker/src/graph.rs
+++ b/graph-checker/src/graph.rs
@@ -43,16 +43,17 @@ impl fmt::Display for Graph {
}
}
if row < self.size - 1 {
- write!(f, "\n")?;
+ writeln!(f)?;
}
}
- return Ok(());
+
+ Ok(())
}
}
impl fmt::Debug for Graph {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- write!(f, "\n")?;
+ writeln!(f)?;
for row in 0..self.size {
for col in 0..self.size {
write!(f, "{}", self.matrix[row][col])?;
@@ -61,10 +62,11 @@ impl fmt::Debug for Graph {
}
}
if row < self.size - 1 {
- write!(f, "\n")?;
+ writeln!(f)?;
}
}
- return Ok(());
+
+ Ok(())
}
}
@@ -86,10 +88,11 @@ fn trim_cutset(cutset: &Cutset) -> Graph {
}
i += 1;
}
- return Graph {
+
+ Graph {
size: cutset.cardinality,
matrix: mat,
- };
+ }
}
fn iterate(n: usize) -> Vec<Vec<u32>> {
@@ -107,9 +110,9 @@ fn iterate(n: usize) -> Vec<Vec<u32>> {
}
let mut k = 0;
- for i in 0..v.len() {
- if v[i] == 1 {
- v[i] = 0;
+ for (i, vert) in v.iter_mut().enumerate() {
+ if *vert == 1 {
+ *vert = 0;
} else {
k = i;
break;
@@ -119,7 +122,7 @@ fn iterate(n: usize) -> Vec<Vec<u32>> {
components.push(v.clone());
}
- return components;
+ components
}
impl Cutset {
@@ -138,11 +141,12 @@ impl Cutset {
}
return false;
}
- return true;
+ true
}
}
impl Graph {
+ #[allow(clippy::needless_range_loop)]
pub fn to_g6(&self) -> String {
let mut g = vec![0; self.size];
for i in 0..self.size {
@@ -156,7 +160,7 @@ impl Graph {
crate::geng::get_g6(g, self.size)
}
- pub fn from_g6(line: &String) -> Graph {
+ pub fn from_g6(line: &str) -> Graph {
let mut chars: Vec<u8> = Vec::new();
for character in line.chars() {
chars.push((character as i32 - 63) as u8);
@@ -174,7 +178,8 @@ impl Graph {
i += 1;
}
}
- return Graph { size, matrix };
+
+ Graph { size, matrix }
}
pub fn degree(&self, vertex: usize) -> usize {
@@ -182,7 +187,7 @@ impl Graph {
for i in &self.matrix[vertex] {
sum += if *i == 0 { 0 } else { 1 } as usize;
}
- return sum;
+ sum
}
pub fn min_degree(&self) -> usize {
@@ -193,7 +198,7 @@ impl Graph {
min = d;
}
}
- return min;
+ min
}
pub fn degree_vector(&self) -> Vec<usize> {
@@ -202,9 +207,9 @@ impl Graph {
let d = self.degree(i);
set.insert(d);
}
- let mut vec = Vec::from_iter(set.into_iter());
+ let mut vec = Vec::from_iter(set);
vec.sort_by(|a, b| b.cmp(a));
- return vec;
+ vec
}
pub fn get_closure_traced(&self, trace_steps: bool) -> Graph {
@@ -232,9 +237,10 @@ impl Graph {
break;
}
}
- return closure;
+ closure
}
+ #[allow(clippy::needless_range_loop)]
pub fn cutsets(&self) -> Vec<Cutset> {
let mut cs = Vec::new();
for vertices in iterate(self.size) {
@@ -242,8 +248,8 @@ impl Graph {
for vertex in 0..g.size {
for i in 0..g.size {
if vertices[vertex] == 0 {
- g.matrix[vertex as usize][i as usize] = 0;
- g.matrix[i as usize][vertex as usize] = 0;
+ g.matrix[vertex][i] = 0;
+ g.matrix[i][vertex] = 0;
}
}
}
@@ -254,7 +260,7 @@ impl Graph {
graph: g,
});
}
- return cs;
+ cs
}
pub fn max_independent_cutset(&self) -> Cutset {
@@ -271,7 +277,7 @@ impl Graph {
};
}
}
- return max_cutset.unwrap();
+ max_cutset.unwrap()
}
pub fn dfs(&self, vertex: usize, visited: &mut Vec<usize>) {
@@ -297,7 +303,6 @@ impl Graph {
return;
}
visited[next] = 1;
- // println!("{next} {to} {path:?}");
for i in 0..g.size {
if visited[i] != 1 && g.matrix[next][i] != 0 {
let mut p = path.clone();
@@ -316,7 +321,7 @@ impl Graph {
}
}
- fn count_components_partial(&self, included_vertices: &Vec<u32>) -> usize {
+ fn count_components_partial(&self, included_vertices: &[u32]) -> usize {
let mut visited = vec![0; self.size];
for i in 0..included_vertices.len() {
if included_vertices[i] == 0 {
@@ -325,17 +330,11 @@ impl Graph {
}
let mut count = 0;
while visited.iter().sum::<usize>() != visited.len() {
- let mut next = 0;
- for i in 0..self.size {
- if visited[i] == 0 {
- next = i;
- break;
- }
- }
+ let next = visited.iter().position(|&v| v == 0).unwrap();
self.dfs(next, &mut visited);
count += 1;
}
- return count;
+ count
}
pub fn count_components(&self) -> usize {
@@ -357,7 +356,7 @@ impl Graph {
return false;
}
}
- return true;
+ true
}
pub fn is_3_connected(&self) -> bool {
@@ -378,7 +377,7 @@ impl Graph {
}
}
}
- return true;
+ true
}
pub fn is_4_connected(&self) -> bool {
@@ -403,7 +402,7 @@ impl Graph {
}
}
}
- return true;
+ true
}
pub fn neighbors(&self, vert: i32) -> Vec<i32> {
@@ -415,7 +414,7 @@ impl Graph {
}
}
- return res;
+ res
}
pub fn is_locally_connected(&self) -> bool {
@@ -429,7 +428,7 @@ impl Graph {
return false;
}
}
- return true;
+ true
}
pub fn get_closure(&self) -> Graph {
@@ -446,7 +445,7 @@ impl Graph {
return false;
}
}
- return true;
+ true
}
pub fn get_toughness(&self) -> f64 {
@@ -457,14 +456,14 @@ impl Graph {
while (right - left).abs() > eps {
let mid = (left + right) / 2.0;
- if self.check_toughness(mid) == false {
- right = mid;
- } else {
+ if self.check_toughness(mid) {
left = mid;
+ } else {
+ right = mid;
}
}
- return (left * 1e7).round() / 1e7;
+ (left * 1e7).round() / 1e7
}
pub fn is_complete(&self) -> bool {
@@ -475,7 +474,7 @@ impl Graph {
}
}
}
- return true;
+ true
}
pub fn is_independent(&self) -> bool {
@@ -486,7 +485,7 @@ impl Graph {
}
}
}
- return true;
+ true
}
fn swap_vertices(&mut self, a: usize, b: usize) {
@@ -543,7 +542,7 @@ impl Graph {
i += 1;
}
}
- return false;
+ false
}
pub fn is_free_of(&self, graphs: &Vec<Graph>) -> bool {
@@ -558,6 +557,6 @@ impl Graph {
}
}
}
- return true;
+ true
}
}
diff --git a/graph-checker/src/main.rs b/graph-checker/src/main.rs
index 25a7768..231221e 100644
--- a/graph-checker/src/main.rs
+++ b/graph-checker/src/main.rs
@@ -1,6 +1,5 @@
use sqlx::{migrate::MigrateDatabase, QueryBuilder, Sqlite};
use std::time::Instant;
-use tokio;
mod graph;
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 11:06:42 +0000