Le but de cet exercice est de résoudre des labyrinthes rapidement en utilisant du parallélisme de tâches. Plus précisément on cherche le chemin pour aller à n'importe quel point du labyrinthe.

En pratique, un labyrinthe sera représenté par un graphe de N nœuds, étiquetés de 0 à N-1. Le nœud 0 sera l'entrée. Le type du graphe sera déclaré comme ci-dessous.

# #![allow(unused_variables)]
#fn main() {
/// Un graphe orienté représenté par des listes d'adjacence. Le graphe peut contenir des
/// boucles d'une seule arête et peut avoir plusieurs arêtes entre les mêmes nœuds.
struct Graph {
    nodes: Vec<Vec<usize>>,
}

impl Graph {
    /// Créé un nouveau graphe sans arêtes.
    fn new(num_nodes: usize) -> Self {
        Graph {
            nodes: (0..num_nodes).map(|_| vec![]).collect()
        }
    }

    /// Retourne les voisins d'un nœud.
    fn neighbors(&self, node: usize) -> &[usize] { &self.nodes[node] }

    /// Retourne le nombre de nœuds dans le graphe.
    fn num_nodes(&self) -> usize { self.nodes.len() }

    /// Ajoute une arête au graphe.
    fn add_edge(&mut self, src: usize, dst: usize) {
        self.nodes[dst].push(src);
        self.nodes[src].push(dst);
    }
}
#}

Afin de benchmarker nos algorithmes, on utilisera la fonction ci-dessous pour générer des graphes aléatoires.

# #![allow(unused_variables)]
#fn main() {
/// Génère un graphe aléatoire avec `num_nodes` nœuds et density*num_nodes arêtes.
fn gen_graph(num_nodes: usize, density: f64) -> Graph {
    assert!(density >= 1.0);
    let mut graph = Graph::new(num_nodes);
    let mut rng = rand::weak_rng();
    // Generate a tree.
    for i in 1..num_nodes { graph.add_edge(i, rng.gen_range(0, i)); }
    // Add edges.
    for _ in 0..(num_nodes as f64 * (density-1.0)) as usize {
        graph.add_edge(rng.gen_range(0, num_nodes-1), rng.gen_range(0, num_nodes-1));
    }
    graph
}
#}

Question 1. Écrivez une fonction find_path qui trouve un chemin entre l'entrée et tous les points du graphe. Cette fonction retournera un tableau contenant le prédécesseur de chaque noeud sur le chemin qui le relie à l'entrée.

Attention: On demande pas forcément le plus court chemin.

Question 2. Écrivez des benchmarks pour la fonction find_path sur:

• un graphe de 100 000 noeuds, avec une densité de 100 et
• un graphe de 100 000 noeuds, avec une densité de 10.

Question 3. Écrivez une version parallèle de la fonction find_path. Testez votre implémentation sur les différents graphes de benchmarks. Si votre version parallèle n'accélère pas beaucoup le calcul (ou le ralenti), essayez d'expliquer ce phénomène et d'améliorer votre code en conséquent.

Pour paralléliser votre code, vous pourrez utiliser (on non) certain des objets ou fonctions ci-dessous:

• les verrous,
• les types atomiques,
• la fonction join de rayon et
• la fonction scope de rayon.