Logo

Programming-Idioms

History of Idiom 130 > diff from v7 to v8

Edit summary for version 8 by freecoder:
New Rust implementation by user [freecoder]

Version 7

2018-04-08, 19:18:25

Version 8

2019-01-05, 11:46:15

Idiom #130 Depth-first traversing in a graph

Call a function f on every vertex accessible for vertex v, in depth-first prefix order

Illustration

Idiom #130 Depth-first traversing in a graph

Call a function f on every vertex accessible for vertex v, in depth-first prefix order

Illustration
Extra Keywords
dfs
Extra Keywords
dfs
Imports
use std::rc::{Rc, Weak};
use std::cell::RefCell;
Code
struct Vertex<V> {
	value: V,
	neighbours: Vec<Weak<RefCell<Vertex<V>>>>,
}

// ...

fn dft_helper(start: Rc<RefCell<Vertex<V>>>, f: &impl Fn(&V), s: &mut Vec<*const Vertex<V>>) {
	s.push(start.as_ptr());
	(f)(&start.borrow().value);
	for n in &start.borrow().neighbours {
		let n = n.upgrade().expect("Invalid neighbor");
		if s.iter().all(|&p| p != n.as_ptr()) {
			Self::dft_helper(n, f, s);
		}
	}
}
Comments bubble
See demo for full example.
Demo URL
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=f854e8f7377e3343e182caa0cdff84c3