1

I'd like to create a small graph module for my project. I do need both directed and undirected graphs.

If it was C++ or Java, I'd make an abstract class Graph implementing depth first search, breadth first search and 2 children classes Directed and Undirected for specific implementations or specific methods.

I did read the OOP part of the book; however, how would I represent this behaviour with trait ?

Ideally, I could be able to use my mod like this :

use graph::{UndirectedGraph, DirectedGraph, Graph};


pub fn main() {
    let g1 = Undirectedgraph::new(); // implementing Graph trait
    let g2 = DirectedGraph::new(); // implementing Graph trait
    g1.dfs(); // from Graph
    g2.dfs(); // from Graph
    g1.bfs(); // from Graph
    g2.bfs(); // from Graph

    let _ = g1.has_loop(); // from UndirectedGraph implementation only
    let _ = g2.has_loop() // from DirectedGraph implementation only
}

So I ended up with something like this ; as you can see

there is still a lot of redundancy with attributes and getters :

#[derive(Debug)]
pub struct Node {
    value: i32,
}

pub trait Graph {
    fn get_vertices(&self) -> &Vec<Node>;

    fn print_nodes(&self) {
        self.get_vertices()
            .iter()
            .for_each(|x| println!("{:#?}", x));
    }

    fn bfs(&self) {
        println!("Common implementation");
    }

    fn dfs(&self) {
        println!("Common implementation");
    }

    fn has_loop(&self) -> bool; // should be implemented
}

pub struct DirectedGraph {
    vertices: Vec<Node>,
}

impl Graph for DirectedGraph {
    fn get_vertices(&self) -> &Vec<Node> {
        &(self.vertices)
    }

    fn has_loop(&self) -> bool {
        //some weird stuff
        // specific to DirectedGraph
        true
    }
}

pub struct UndirectedGraph {
    vertices: Vec<Node>,
}

impl Graph for UndirectedGraph {
    fn get_vertices(&self) -> &Vec<Node> {
        &(self.vertices)
    }

    fn has_loop(&self) -> bool {
        //some weird stuff
        // specific to UndirectedGraph
        true
    }
}
6
  • 1
    petgraph has a Graph struct generic over Ty which can be either Directed or Undirected (marker types that contain no data). Perhaps you could do something like that?
    – trent
    Jul 20, 2019 at 0:26
  • 1
    Would creating a trait with default implementations for the dfs and bfs methods work?
    – solartic
    Jul 20, 2019 at 1:55
  • 3
    I agree with the above. Use a trait and define getters and setters that shared between them.
    – kyle
    Jul 20, 2019 at 3:08
  • You might want to define a Node trait with a directed edges impl and an undirect edges impl, providing a common iterator method. Then you can have a struct Graph<N: Node>(typed_arena::Arena<N>)
    – SOFe
    Jul 20, 2019 at 5:56
  • By the way, if traits really don't work, you might want to use macros. Macros are widely used in, say, serialization libraries that generate a separate impl for each [iuf](16|32|64).
    – SOFe
    Jul 20, 2019 at 7:35

2 Answers 2

1

You can't access the data's attributes directly from a trait (see Jimmy Cuadra answer). However we can use shared getters and setters as kyle commented.

Something akin to the code below should work.

trait Graph {
    fn adjacent_edges(&self, v: &Vertex) -> SomeOutput;

    fn dfs(&self, v: &Vertex) -> SomeOutput {
        let adjacent_edges = self.adjacent_edges(v);
        // ...
    }

    fn bfs(&self, v: &Vertex) -> SomeOutput {
        let adjacent_edges = self.adjacent_edges(v);
        // ...
    }
}


struct UndirectedGraph { ... }

impl Graph for UndirectedGraph {
    fn adjacent_edges(&self, v: &Vertex) -> SomeOutput {
        // ...
    }
}


struct DirectedGraph { ... }

impl Graph for DirectedGraph {
    fn adjacent_edges(&self, v: &Vertex) -> SomeOutput {
        // ...
    }
}
2
  • Well, I did figure it out by myself this trick without seeing your answer, you can check my edit. Your solution is still better than mine who got some redundancy you don't have in your code.
    – politinsa
    Jul 20, 2019 at 22:27
  • @politinsa Awesome, I'm glad you figured it out. I'm not sure if my solution is better than yours at this point since I didn't do a full implementation. Plus the core idea is the same.
    – solartic
    Jul 20, 2019 at 22:43
1

Traits cannot implicitly access the data of implementing types in default method implementations. That is to say, you can't provide a single trait method implementation that accesses specific fields of the Self type because it cannot be assumed that Self has any particular field. It's possible a nicer construct for traits accessing fields may be allowed in a future extension to the language. See RFC 1546 for one such proposal and discussion about it. But that is still only for direct field access. If you need to manipulate a field in any way before returning it, even that wouldn't help.

For now, you'll either need to write the implementations of Graph for the two types manually, or if the implementations are indeed trivially similar, you could use a macro that has the contents of the implementation and invoke it once for each type. Whether or not the amount of duplication necessary for two manual implementations

2
  • 1
    I was not thinking about this initially, but as @Kyle points out we can use getters and setters to access and manipulate the shared fields. We can then use these in the default implementations for for the search methods.
    – solartic
    Jul 20, 2019 at 15:24
  • I end up using getters. Hope this RFC will soon be available
    – politinsa
    Jul 20, 2019 at 22:28

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.