0

I followed the approach mentioned in https://ricardomartins.cc/2016/06/08/interior-mutability for creating a graph in Rust using Rc and RefCell.

type NodeRef<i32> = Rc<RefCell<_Node<i32>>>;

#[derive(Clone)]
// The private representation of a node.
struct _Node<i32> {
    inner_value: i32,
    adjacent: Vec<NodeRef<i32>>,
}
#[derive(Clone)]
// The public representation of a node, with some syntactic sugar.
struct Node<i32>(NodeRef<i32>);

impl<i32> Node<i32> {
    // Creates a new node with no edges.
    fn new(inner: i32) -> Node<i32> {
        let node = _Node { inner_value: inner, adjacent: vec![] };
        Node(Rc::new(RefCell::new(node)))
    }

    // Adds a directed edge from this node to other node.
    fn add_adjacent(&self, other: &Node<i32>) {
        (self.0.borrow_mut()).adjacent.push(other.0.clone());
    }
}
#[derive(Clone)]
struct Graph<i32> {
    nodes: Vec<Node<i32>>,
}

impl<i32> Graph<i32> {
    fn with_nodes(nodes: Vec<Node<i32>>) -> Self {
        Graph { nodes: nodes }
    }

}

I think this approach will lead to memory leaks in case of cyclic graphs. How can I fix that?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
user9097180
  • 1

1 Answers1

1

You don't have to read a blog post to find the answer, just read the documentation:

A cycle between Rc pointers will never be deallocated. For this reason, Weak is used to break cycles. For example, a tree could have strong Rc pointers from parent nodes to children, and Weak pointers from children back to their parents.

See also:

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
  • Well, so does that mean that for every edge you insert, you will look through the entire graph to check if this edge will create a cycle? I did read that you can use weak pointers in trees if you want children to point back to parents. But I am not sure how to translate that in case of graphs? What does it mean to have weak pointers in graphs? – user9097180 Dec 14 '17 at 22:44
  • 2
    @user9097180 you are about to embark on a journey of discovery around why exactly graphs are really hard concepts for memory management in both garbage-collected and non-GC languages. If you, the human, can't figure out a process to determine which links in a graph are strong and which are weak, how would the compiler / runtime? Maybe if your nodes have some ordering you could do strong references for "bigger" nodes and weak references for "smaller" nodes (I don't know if this will work). – Shepmaster Dec 14 '17 at 22:58
  • 2
    @user9097180: At this point, you may want to look up the `petgraph` crate. – Matthieu M. Dec 15 '17 at 13:51