2
\$\begingroup\$

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());
    }
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Improving your skills is very much welcome in the Rust community!

The preferred approach would be to just duplicate code. Please don't overdo the Don't Repeat Yourself rule.

If you really wish to know how not to duplicate code, there are two options:

  • write a data structure that works both as a Graph and a DiGraph at the same time, perhaps something with tagged unions as node refs and with code filtering these
  • for optimal performance, add two empty structs and implement a trait for both structs, maybe like this:
struct UnDiGraphMode<T>;
struct DiGraphMode<T>;
trait GraphMode<T> {
    type Pred;

    fn is_directed(&self) -> bool;

    /// ...
    /// ...
}

impl GraphMode<T> for UnDiGraph<T> {
    type Pred = ();
    fn is_directed(&self) -> bool { false }
    /// ...
    /// ...
}

impl GraphMode<T> for DiGraph<T> {
    type Pred = HashMap<T, HashSet<T>>;
    fn is_directed(&self) -> bool { true }
    /// ...
    /// ...
}

#[derive(Debug)]
pub struct Graph<T, Mode = UnDiGraphMode<T>>
where
    T: Clone + Hash + Eq + Debug,
    Mode: GraphMode<T>,
{
    pred: Mode::Pred,
    adj: HashMap<T, HashSet<T>>,
    mode: Mode,
}

pub type DiGraph<T> = Graph<T, DiGraphMode>;

A couple comments on the code:

Do you wish to expose this as a library? If so, please do not expose implementation details in public interfaces. You will get yourself into a pickle when changing implementation details and find yourself making breaking changes. Write this with impl Trait:

/// Iterate over a graph, i.e. over its keys.
pub fn iter(&self) -> impl Iterator<Item = &T> {
    self.adj.keys()
}

Also here. (Nitpick: unnecessary "return".)

/// Get all nodes from a graph.
pub fn nodes<B: FromIterator<T>>(&self) -> B {
    self.adj.keys().cloned().collect()
}

After the change above, the caller must specify a container to which nodes are collected -- either a vec or hashset or something else.

g.nodes::<HashSet<_>>()

Tests could be more readable: give expressions a name.

let actual = g.nodes::<HashSet<_>>();
let expected = HashSet::from([1, 2, 3]);
assert_eq!(actual, expected);

Simpler code:

/// Adds a directed edge from u to v (u->v).
fn add_directed_edge(&mut self, u: T, v: T) {
    // `HashSet::new()` should not allocate, so we do not need `or_insert_with(|| ...)` for preformance.
    self.adj.entry(u).or_insert(HashSet::new()).insert(v);
}

Good job commenting all methods! Could add doc examples.

Best,

-- Peter

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thank you for your reply! This gives me a good perspective on how to structure the code and what to improve. \$\endgroup\$
    – qoqosz
    Feb 10, 2023 at 19:48
  • 1
    \$\begingroup\$ @qoqosz By the way, here is my Directed Graph implementation: github.com/pczarn/panini/blob/… \$\endgroup\$ Feb 12, 2023 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.