Checking if a graph is fully connected

Question

After reading the rust book for some time I decided to create my first program which implements a graph.

There are a few things I was wondering about, such as if the file structure is appropriate (the graph.rs just containing a few mod statements feels weird).

Also to store pointers to the edges I had to use Rc and I am not sure if that is the correct choice?

And finally I'm also wondering if there is a more idiomatic rust way to write certain code ?

Other comments are welcome as well of course.

main.rs:

use crate::graph::edge::Edge;
use crate::graph::graph::Graph;
use crate::graph::node::Node;
use std::collections::HashMap;
use std::rc::Rc;

pub mod graph;

fn main() {
    let g = create_graph();
    println!("graph connected: {}", g.is_fully_connected());
}

fn create_graph() -> Graph {
    let n: Vec<Node> = vec![Node::new(), Node::new(), Node::new()];

    let edge1 = &Rc::new(Edge::new(0, 1));
    let edge2 = &Rc::new(Edge::new(0, 2));
    let edge3 = &Rc::new(Edge::new(1, 2));

    let mut neighbors = HashMap::new();

    let neighbors0 = vec![Rc::clone(edge1), Rc::clone(edge2)];
    let neighbors1 = vec![Rc::clone(edge1), Rc::clone(edge3)];
    let neighbors2 = vec![Rc::clone(edge2), Rc::clone(edge3)];
    neighbors.insert(0, neighbors0);
    neighbors.insert(1, neighbors1);
    neighbors.insert(2, neighbors2);

    Graph::new(n, neighbors)
}

graph.rs:

pub mod graph;
pub mod edge;
pub mod node;

graph/node.rs:

pub struct Node {
    //TODO coordinates
}

impl Node {
    #[inline]
    pub fn new() -> Self {
        Node {}
    }
}

graph/edge.rs

pub struct Edge {
    node_a: i32,
    node_b: i32,
}

impl Edge {
    #[inline]
    pub fn new(node_a: i32, node_b: i32) -> Self {
        Edge {
            node_a: node_a,
            node_b: node_b,
        }
    }

    //if base_node is neither of the edge nodes then the result is considered random
    pub fn get_adj_node(&self, base_node: i32) -> i32 {
        if base_node == self.node_a {
            self.node_b
        } else {
            self.node_a
        }
    }
}

graph/graph.rs:

use super::edge::Edge;
use super::node::Node;
use std::collections::HashMap;
use std::collections::HashSet;
use std::rc::Rc;

pub struct Graph {
    nodes: Vec<Node>,
    neighbors: HashMap<i32, Vec<Rc<Edge>>>, //node index to coinciding edges
}

impl Graph {
    pub fn new(nodes: Vec<Node>, neighbors: HashMap<i32, Vec<Rc<Edge>>>) -> Self {
        Graph {
            nodes: nodes,
            neighbors: neighbors,
        }
    }

    pub fn is_fully_connected(&self) -> bool {
        let mut index = 0;

        let mut stack = vec![index];
        let mut used = HashSet::from([index]);

        while !stack.is_empty() {
            index = stack.pop().unwrap();

            let neighbors = match self.neighbors.get(&index) {
                None => continue,
                Some(n) => n,
            };
    
            for edge in neighbors {
                let adj_node = edge.get_adj_node(index);
                if !used.contains(&adj_node) {
                    used.insert(adj_node);
                    stack.push(adj_node);
                }
            }
        }

        used.len() == self.nodes.len()
    }
}

Answer 1

Very nice! The use of Rc to store the edges is a good choice. Technically, it's probably not necessary here where your edges are only ordered pairs of ints (a primitive copyable type) -- but would become a crucial feature if you want to extend Edge with additional information, such as an edge label that can be modified or replaced.

The biggest thing I see for improvement is that your Graph::new interface is rather awkward. It requires clients of your graph to pay attention to low-level, irrelevant details, constructing a HashMap and compiling edges into a Vec of Rc pointers. It would be much nicer to use a builder pattern here: your graph starts empty, and you can add vertices and edges one at a time. That is:

impl Graph {
    pub fn new() -> Self { ... }
    pub fn add_node(&mut self, i: i32) { ... }
    pub fn add_edge(&mut self, i1: i32, i2: i32) { ... }
}

If done correctly, this way, the Rc stuff should only be a local implementation detail inside Graph. I.e., your graph would construct Rc internally when adding edges and would not expose that detail to the user.

Secondly, always try running cargo clippy! It's super helpful and generally gives correct suggestions for how to make Rust code more idiomatic. You have generally done well; the main thing it catches is when constructing a struct object, you can omit names that are the same as the field name like nodes: nodes and just write nodes. It also suggests implementing Default for objects that have a default (empty) object, which in your case would be Node and Graph (though I suspect Node may later change to a different interface without a default implementation).

For most structs -- in your case, Edge, Node, and Graph -- you should always #[derive(Debug, Clone)] unless there is a good reason not to. Debug makes it possible to print out your graph and edges if you need to for debugging purposes, and Clone means that clients can make a deepcopy of edges and graphs if needed. Like this:

#[derive(Debug, Clone)]
pub struct Edge {
    node_a: i32,
    node_b: i32,
}

The file you named graph.rs is more commonly put in graph/mod.rs. It's not unusual that mod.rs only includes a short list of imports.

Putting the main modules in main.rs is fine for a command-line tool or binary. If you want to build a library (data structure) that others will use, you would put the public module declarations in a file called lib.rs, and import them from main instead.

Lastly, consider adding some unit tests! To add one, simply write a function like

#[test]
fn test_add_edge() {
    ...
}

which uses assert!(...) and assert_eq!(..., ...) to check behavior. You can then run the unit tests with cargo test.