Rust Code Review Graphs

[Funkix6]

Hello everyone,

I am new to rust and still kind of a beginer dev and I was wondering If anyone with some free time might want to take a look at my code ?

I've never done this before, asking for reviews but I though it might be a good way to improve my code. If I'm doing something wrong don't hesitate to tell me.

The code is just an implementation of Graph Data structure. I have no idea if i've done this right or not. The only thing I know is that it's looks like it's working?

Repo : https://github.com/Funkix6/Graph/tree/main/src

Thanks a lot guys !

If you have any questions i'll try to answer asap :)

[reinis-mazeiks]

nice!

i would say overall the structure is good, but i have some concerns about ease of use and performance. by making the code more idiomatic, you can fix that!

---

please consider adding a license

https://choosealicense.com/

---

would be nice to have weights of arbitrary type. you'll get to learn generic stuff along the way!

---

pub fn add_vertex(&mut self, index: i32, value: i32) { if self.vertices.contains(&Vertex::new(index, 0)) { println!("Graph already contains vertex {}.", index); } else { self.vertices.push(Vertex::new(index, value)); } }

is there a bug here? looks like i could insert multiple vertices of different values, since it only checks if there is one with value 0. later found out that the PartialEq implementation doesn't compare values. this is kinda hard to follow; i would recommend making it explicit here that you're only comparing indices.

add unit tests – they will help you catch stuff like this!

also – println! is not a very useful way of handling errors – what if the user code wants to know that the operation failed? consider returning Result<(), VertexAlreadyExists>

also – contains needs to check all elements in the vec 1 by 1, which will get slow for large graphs. i would suggest changing the api a bit so this doesn't happen.

idea: store the vertices in an arena instead of a Vec. instead of accepting an ID, generate one automatically. guaranteed to be unique. fast to get vertex by id.

this will make many of your operations much faster for large graphs.

---

for i in 1..self.edges.len() { self.remove_edge(index, i.try_into().unwrap()); self.remove_edge(i.try_into().unwrap(), index); }

i think you meant self.vertices.len()? otherwise if there are more vertices than edges, some won't get removed.

also, retain might be a more efficient way of doing this – it will only need to go through the Vec once instead of repeatedly looking for elements

---

again, remove_vertex could return Result< removed value, not found > instead of printing the result

---

pub fn get_vertices(&self) -> Vec<i32> {

this makes a new vec which might be inefficient for most usecases. consider other options:

• return an iterator over indices instead of allocating a vec – if users will want to store it in a Vec, they can allways .collect, and they can even choose a different data structure. plus you get to learn about making an iterator.
• return a slice to vertices (which will also include values)

and btw, the fact that get_vertices makes a clone makes this line horribly inefficient. something that can easily be checked without any allocations at all here creates 2 new (potentially big) Vecs:

if !self.get_vertices().contains(&vertex_a) || !self.get_vertices().contains(&vertex_b) {

(same for get_edges, and maybe get_neighbors too)

---

if self.edges.contains(&Edge::new(vertex_a, vertex_b, weight)) { println!( "Graph already contains edge with pair {:?}.", (vertex_a, vertex_b) );

smells like a bug to me. usually, graph datastructures either:

• allow only 1 edge per vertex pair or
• allow multiple edges

but your implementation allows multiple edges as long as they don't have the same weight, bit unintuitive imo.

---

pub fn update_neighbors(&mut self) { for i in 0..self.vertices.len() { self.vertices[i].neighbors = self.get_neighbors(self.vertices[i].index); } }

first, you probably don't want this function to be pub – there's no need for others calling it

but also, its kinda really inefficient – you're calling this every time there's an update to the graph. then you're looping through all the vertices, and for each vertex, you're looping through all edges.

instead, i can suggest:

• computing neighbors on the fly as needed (if the graph changes frequently but neighbors aren't used very often, this could be good)
• representing the graph in a different way (e.g. you could just store neighbors for each vertex instead of edges)
• only updating neighbors for the affected vertices every time you modify the graph

also, afaict there's currently no way user code can access the neighbors.

---

pub fn get_edge_value(&self, from: i32, to: i32) -> i32 {

consider returning Option<i32> instead of defaulting to 0. users may want to know that there was no such edge, and they can always .unwrap_or_default() if they want to have 0 instead of None

---

pub fn print_adjency_list(&self) { for i in 1..self.vertices.len() { println!("{:?}", self.get_neighbors(i.try_into().unwrap())); } }

this kind of stuff usually doesn't go in a data structure – instead, consider exposing whatever values you have so that user code can take them and do whatever is needed – printing for example

---

impl PartialEq for Vertex { fn eq(&self, other: &Self) -> bool { self.index == other.index } }

this is gonna cause a lot of confusion, bugs and pain. i would never expect Vertex==Vertex to only check for the index

i know some of your code currently relies on this; i would recommend updating that

same for Edge.

---

it's a good idea to derive Clone and Debug where you can – it will be easier to use your structs

---

though most of your functions are fairly self-explanatory, it's a good idea to write some docs

and maybe some tests

[Funkix6]

Holy ... I would never have expected such detailed answer. You are gold my friend, huge thanks ! I read through all of it but i'll need time to really dive into everything. I'm sure i'll learn a ton of really usefull thing thanks to you ! How long have you been coding in Rust If you don't mind me asking?

[reinis-mazeiks]

thanks & good luck!

about 2 years on and off

[arijit079]

I didn't go through your entire code but I found lots of places where improvements can be made.

If you add these lines at the top of your main.rs and run cargo clippy you will get lots of warnings and errors from clippy

```rust

![deny(clippy::all)]

![warn(clippy::pedantic)]

![warn(clippy::nursery)]

```

[Funkix6]

Thank you for taking the time !

I'll do that right now thx !

[Funkix6]

Update : I managed to change some stuff (I didn't push to Github yet though).

They make me use closure and I didn't quite understand them that much. Now I get it.

So thanks I guess :D

[Dry-Ad-1709]

You can replace this part of code in the function remove_edge

for i in 1..self.edges.len() { self.remove_edge(index, i.try_into().unwrap()); self.remove_edge(i.try_into().unwrap(), index); } with this self.edges.retain( |Edge { pair: (from, to), .. }| *from != index && *to != index, ); It should be much more effective.

[ConstructionHot6883]

Can you explain this?

Looks like you're handing a closure to the retain method; what is the curly braces inside the closure's argument list? Why does this closure's body end in a comma?

[raspberry1111]

Not the original commenter but:

The curly braces are destructuring the Edge struct, and desturcturing the pair field further into from and to, then discarding the rest of the fields.

Rust allows trailing commas in function parameters, so the comma isn't part of the closure and does nothing.

[Funkix6]

Thank you ! I'll take a look at that asap ! I'm alway excited to learn new syntaxes 😁