I am trying to improve my Rust coding skills. One thing which I find hard to tackle is how to shift from a polymorphism you can observe in e.g. Python to sth. similar in Rust?
Let me give you a specific example. I would like to implement a very simple Graph (undirected graph) and DiGraph (directed graph) structures in Rust that mimic their Python equivalents in networkx library. Within a graph, I want to keep the data as an adjacency map. So the struct is roughly:
pub struct Graph<T>
where
T: Clone + Hash + Eq + Debug
{
adj: HashMap<T, HashSet<T>>,
}
pub struct DiGraph<T>
where
T: Clone + Hash + Eq + Debug
{
adj: HashMap<T, HashSet<T>>,
pred: HashMap<T, HashSet<T>>,
}
For a simple undirected graph like 1 <--> 2 <--> 3 this would yield: adj = {1: {2}, 2: {1, 3}, 3: {2}}. Similarly, in a directed case 1 --> 2 --> 3 a struct would hold: adj = {1: {2}, 2: {3}, 3: {}} and pred: {1: {}, 2: {1}, 3: {2}}.
At the bottom I attach my implementation of few methods for the Graph struct, you can also run it in Rust Playground.
Do you have any comments on the code so far? What would you suggest to extend this code to also cover the DiGraph implementation but would not require code duplication?
If I were to use traits, e.g. CommonGraph I can't see how this could help. For each class I would need to implement the same set of methods - often with exactly the same implementation.
Other approach I've seen when googling is to include Graph object as a member of DiGraph. But even then, some methods of DiGraph would do just a call to the underlying method of a Graph member which seems very redundant.
What is the preferred idiomatic approach?
use std::collections::{HashMap, HashSet};
use std::collections::hash_map::Entry;
use std::collections::hash_map::Keys;
use std::fmt::Debug;
use std::hash::Hash;
#[derive(Debug)]
pub struct Graph<T>
where
T: Clone + Hash + Eq + Debug
{
adj: HashMap<T, HashSet<T>>,
}
impl<T> Graph<T>
where
T: Clone + Hash + Eq + Debug
{
/// Create an empty graph.
pub fn new() -> Self {
Graph { adj: HashMap::new() }
}
/// Iterate over a graph, i.e. over its keys.
pub fn iter(&self) -> Keys<T, HashSet<T>> {
self.adj.keys()
}
/// Add a node. Do nothing if it already exists.
pub fn add_node(&mut self, u: T) {
self.adj.entry(u).or_insert(HashSet::new());
}
/// Get all nodes from a graph.
pub fn nodes(&self) -> HashSet<T> {
return self.adj.keys().cloned().collect();
}
/// Adds a directed edge from u to v (u->v).
fn add_directed_edge(&mut self, u: T, v: T) {
match self.adj.entry(u) {
Entry::Occupied(succ) => { succ.into_mut().insert(v); },
Entry::Vacant(succ) => { succ.insert(HashSet::from([v])); },
}
}
/// Adds an edge in a graph (u<->v).
pub fn add_edge(&mut self, u: T, v: T) {
self.add_directed_edge(u.clone(), v.clone());
self.add_directed_edge(v, u);
}
/// Get adjacent elements in a graph.
pub fn adj(&self, u: &T) -> Option<&HashSet<T>> {
return self.adj.get(u)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn empty_graph() {
let g: Graph<i8> = Graph::new();
assert_eq!(g.nodes(), HashSet::new());
}
#[test]
fn add_nodes() {
let mut g: Graph<i8> = Graph::new();
g.add_node(1);
g.add_node(2);
g.add_node(3);
assert_eq!(g.nodes(), HashSet::from([1, 2, 3]));
}
#[test]
fn add_edges() {
let mut g: Graph<i8> = Graph::new();
g.add_edge(1, 2);
assert_eq!(g.nodes(), HashSet::from([1, 2]));
assert_eq!(*g.adj(&1).unwrap(), HashSet::from([2]));
assert_eq!(*g.adj(&2).unwrap(), HashSet::from([1]));
}
#[test]
fn no_adj() {
let g: Graph<i8> = Graph::new();
assert!(g.adj(&2).is_none());
}
}
