Graphe
Un parcours de graphe avec un peu de borrow checker.
Un petit exo expérimental cette fois-ci sur le borrow checker. Je trouve assez difficile de faire des exos réalistes où l’on croise des problèmes de borrow et voici une petite tentative dans ce sens.
On considère un graphe très simple. Les sommets sont des usize de 0 à n-1. La classe Graphe dispose d’une méthode voisins permettant d’itérer sur tous les voisins directs d’un sommet donné.
Sur le graphe ci-dessus, voisins(5) par exemple itère sur 1 et 4 (dans un ordre quelconque).
On cherche à implémenter un itérateur sur tous les sommets accessibles à partir d’un point de départ donné. Un parcours de graphe tout ce qu’il y a de plus classique qui peut servir par exemple au calcul des différentes composantes connexes.
Il s’agit d’un parcours en profondeur qui nécessite donc une pile pour se rappeller des sommets restant à explorer. En plus de cela, afin d’éviter de passer deux fois au même endroit on utilise une table de hachage mémorisant les sommets que notre itérateur à déjà renvoyés.
On utilisera donc la structure suivante pour notre itérateur:
/// iterateur profondeur d'abord sur tous les sommets accessibles
struct Accessibles<'a> {
reste: Vec<usize>,
graphe: &'a Graphe,
vus: HashSet<usize>,
}
Dans notre exo le code de parcours est presque terminé:
impl<'a> Iterator for Accessibles<'a> {
type Item = usize;
fn next(&mut self) -> Option<Self::Item> {
let suivant = self.extraire_reste_non_vu().next();
suivant.map(|s| {
self.vus.insert(s);
// note: ca serait mieux de filtrer ici
// mais l'exo est fait comme ca.
// on ne changera donc pas ce code
self.reste.extend(self.graphe.voisins(s));
s
})
}
}
Le code récupère un itérateur extrayant un par un (par pop) tous les sommets du reste et itérant sur ceux qui ne sont pas encore vus. L’appel à next nous permet d’obtenir le premier sommet restant que l’on n’a pas encore vu. On l’insère alors dans la table de hachage et on rajoute tous ses voisins dans le reste.
Votre mission, si vous l’acceptez consiste à remplir la méthode extraire_reste_non_vu sans modifier son prototype. Il s’agit donc de popper un par un les éléments du reste et de boucler sur ceux qui ne sont pas encore vus.
Le code fourni est ici. Un petit cargo run lancera un test basique.
Solution
Bon, je ne sais pas si vous avez été frappés par le borrow checker. L’idée de base
est de répéter les pop à l’aide de repeat_with tant que la pile n’est pas vide
et de filtrer pour ne garder que les sommets non vus.
La petite difficulté est que pour ça, le pop a besoin d’un emprunt mutable sur self mais
en même temps le filtre a besoin d’un emprunt en lecture sur self également.
La première fois que l’on tombe sur un conflit de ce genre, on est bien embêtés.
Par exemple le code suivant :
let suivant = std::iter::repeat_with(|| self.reste.pop())
.take_while(|&s| s.is_some())
.map(|s| s.unwrap())
.filter(|s| !self.vus.contains(&s))
.next();
ne compile pas et donne :
La solution est pourtant assez simple et fait partie des deux trois trucs un peu cachés qui permettent de résoudre des problèmes de borrow: on commence par réaliser un premier emprunt sur self pour récupérer un couple de références. Après ça, le reste et les sommets vus peuvent être traités de manière séparée.
fn extraire_reste_non_vu<'b>(&'b mut self) -> impl Iterator<Item = usize> + 'b {
let (reste, vus) = (&mut self.reste, &self.vus);
std::iter::repeat_with(move || reste.pop())
.take_while(|&s| s.is_some())
.map(|s| s.unwrap())
.filter(move |s| !vus.contains(&s))
}