Let me give some feedback that's not Rc or RefCell specific.
Cleaning up all_paths_source_target
You can clean up your code a little bit by matching the i32 type in your Node (poor fit for indices though it may be), and by making a constructor for Node. We can also utilize iterators a bit more.
#[derive(Default, Debug)]
struct Node {
data: i32,
links: Links,
visited: bool,
paths: Vec<Vec<i32>>,
}
impl Node {
fn new(data: i32) -> Self {
Node {
data, ..<_>::default()
}
}
fn new_rc(data: i32) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Self::new(data)))
}
}
(We've potentially lost some small optimization by not pre-allocating the links vector, but let's just accept that for now.)
Then in all_paths_source_target:
let nodes: Vec<_> = (0..n).map(|i| Node::new_rc(i as i32)).collect();
// ...
// You had a `&mut nodes` here, but don't need the `mut`
Solution::make_links(&graph, &nodes);
You then index using n-1 a couple times, but never check to see if n is 0. So if someone passes in an empty Vec, you panic. Instead, you can detect this case and just return an empty Vec yourself.
let last = match nodes.last() {
None => return Vec::new(),
Some(thing) => thing,
};
// Uses last now
last.borrow_mut().visited = true;
last.borrow_mut().paths = vec![vec![(n - 1).try_into().unwrap()]];
Solution::make_links(&graph, &nodes);
Solution::find_path(&nodes[0], last); // <-- and here
After that, there's no reason for n to be a usize anymore, and we can clean up just a little more.
let n = graph.len() as i32;
let nodes: Vec<_> = (0..n).map(Node::new_rc).collect();
// ...
last.borrow_mut().paths.push(vec![n - 1]);
Finally, as I understand the algorithm, the paths you build up to return is the almost always the same as the paths that get built up in nodes[0] within the find_path function. It would be possible but verbose to deconstruct your data structure and get it back out. However, we can just clone it and it will probably still be an improvement over rebuilding it entirely.
let paths = nodes[0].as_ref().borrow().paths.clone();
paths
Note that this does give a different result when passed in a DAG with a single node. Your version says there is no path, this version says there's one path (vec![vec![0]]). I believe this is the only difference, but didn't thoroughly test things. If I'm wrong, don't worry for now -- I'll revisit how to rectify things at the end of this post.
Here's what we have after those changes.
Altering make_links
Looping over indices and immediately using them to index into a collection is usually a sign that you should iterate over the collection instead. Let's try that here:
for (i, links) in graph.iter().enumerate() {
for j in links {
nodes[i] /* ... */
}
}
If we iterate over nodes at the same time, we won't need i at all:
for (links, node) in graph.iter().zip(nodes.iter()) {
for j in links {
node /* ... */
}
}
On the inside of the inner loop, you're repeatedly borrowing node and pushing into node.links. Instead, you can just build up the entire vector in one go (since we know links is empty to start):
for (links, node) in graph.iter().zip(nodes.iter()) {
node.borrow_mut().links = links
.iter()
.map(|&j| Rc::clone(&nodes[j as usize]))
.collect();
}
And with that, we've regained the small optimization of pre-allocating links that we took away earlier.
Playground.
Cleaning up find_path
You check the length of paths before iterating. However, creating an empty iterator is cheap in this case -- potentially cheaper than performing the extra check and branch. Additionally, references to Vec (or to slices) implement IntoIterator in the same way that calling .iter() gets you. Putting those together:
// No surrounding `if`
for path in &link.as_ref().borrow().paths { /* ... */ }
Just above this, you check if link has been visited, and then make a recursive call if it has not, with link as the first parameter. But the entire function is wrapped in an if checking if the first parameter has been visited or not. So you're checking twice every time.
The if inside the loop can be removed. Additionally, the setting of visited to true can be performed on from just before returning, instead of inside the loop on link after each call.
Playground with these changes.
Another approach would have been to remove the outer if, and to make sure you never call the function when from.visited is true everywhere, not just in this loop. The only other place you call the function is with node[0] as from, and the only time that can have visited == true is when you have a DAG of size 1 (when node[0] is the last node).
It made more sense to me to remove the inner if and avoid a condition that all callers have to maintain. But if you needed to special-case the size 1 DAG anyway -- e.g. you need to special case the return for a DAG of size 1 -- this may be an option. However, see also the "one last note" below.
Refactoring find_path
Moving on, at this point I'd probably factor the building of set into it's own function.
// n.b. doesn't do any mutation to the parameters
fn build_paths(from_ref: &Node, to: &Rc<RefCell<Node>>) -> Vec<Vec<i32>> {
let mut set: Vec<Vec<i32>> = Vec::new();
for link in from_ref.links.iter() { /* ... */ }
set
}
fn find_path(from: &Rc<RefCell<Node>>, to: &Rc<RefCell<Node>>) {
if !from.as_ref().borrow().visited {
let set = Self::build_paths(&from.as_ref().borrow(), to);
from.borrow_mut().paths.extend(set);
from.borrow_mut().visited = true;
}
}
Here's the one place where the change is sensitive to RefCell. You had an extra lexical block here originally, as you had to make the borrow of the RefCell shorter by making from_ref drop before you called from.borrow_mut() to avoid a run-time panic. Here, I've hidden that necessity in the function boundaries -- the borrow that needs to be limited is now a temporary created in the call to build_paths.
Final playground for this post.
And one last note: with build_paths factored out, if you need the "rebuild and return" behavior that I replaced with a clone, you can get it back like so:
// let paths = nodes[0].as_ref().borrow().paths.clone();
let paths = Self::build_paths(&nodes[0].as_ref().borrow(), &nodes[0]);
nodes[0] has definitely been visited at this point, so the execution will be the same as your original rebuild loop, albeit slightly less efficient.