TD 13 C++: STL: string, containers

Rappels

• Page du Cours
• Procédure de rendu
• Pour vérifier le rendu de ce TD: test.sh

Exercice 2: Graphe, BFS, Dijkstra

1. Complétez le fichier 2.1.h et implémentez-le dans un fichier 2.1.cc!

   // A directed graph is a set of nodes, linked by arcs. Arcs are directed: they
   // go from a node to another node.
   // In this implementation, each node is an integer in [0, num_nodes-1].
   //
   // For example, the following graph:
   //
   //  0 <--- 1 <--> 3 ---> 4
   //  ^      |       \     ^
   //  |      v        `----'
   //  '----- 2
   //
   // Can be obtained by calling this on a fresh DirectedGraph:
   //   AddArc(1, 0);
   //   AddArc(1, 3);
   //   AddArc(3, 1);
   //   AddArc(2, 0);
   //   AddArc(1, 2);
   //   AddArc(3, 4);
   //   AddArc(3, 4);
   //
   class DirectedGraph {
    public:
     void AddArc(int from, int to);
   
     // Returns 1 + the highest node index that was ever given to AddArc(), as
     // 'from' or 'to' argument.
     int NumNodes() const;
   
     // Returns the number of arcs originating from "node".
     // In the example above, OutDegree(1) = 3, OutDegree(4) = 0.
     int OutDegree(int node) const;
   
     // Returns all the destination nodes that were added with arcs
     // originating from "node".
     // In the example above, Neighbors(1) is {0, 2, 3} and Neighbors(2) is {0}.
     const vector<int>& Neighbors(int node) const;
   
    private:
     // TODO
   };

   Testez votre code:

   rm 2.tar.gz; wget --no-cache http://fabien.viger.free.fr/cpp/td13/2.tar.gz
   tar xf 2.tar.gz
   make 2.1

   RENDU: 2.1.h, 2.1.cc
   
   
2. Implémentez la fonction BFS() décrite dans le fichier 2.2.h:

   #include "2.1.h"
   
   // Runs a Breadth-First-Search on the graph, starting from node "src".
   // See https://en.wikipedia.org/wiki/Breadth-first_search .
   // Returns a vector of size N (N is the number of nodes of the
   // graph) representing the "parent" tree: parent[i] is the parent of
   // node #i in the BFS tree. The parent of "src" is itself, and the
   // parent of a node that wasn't reached by the BFS exploration is -1.
   vector<int> BFS(const DirectedGraph& graph, int src);

   La complexité devra être O(M + N), où M est le nombre d'arcs et N le nombre de noeuds.
   
   Test: vous devez d'abord faire le 2.3!
   make 2.2
   RENDU: 2.2.cc
   
   
3. Implémentez la fonction GetBfsDistances() décrite dans le fichier 2.3.h:

   #include <vector>
   using std::vector;
   
   // Extracts the distances of each node in the given BFS tree, which
   // is the returned format described in 2.2.h
   // Eg. in the following tree, whose root is "2":
   //
   //         .---- 4
   //         v
   //   2 <-- 3 <-- 1
   //   ^
   //   '---- 0 <-- 5
   //
   // The bfs tree is represented by the following 'parent' vector:
   // [2, 3, 2, 2, 3, 0]
   // And the distance vector should be:
   // [1, 2, 0, 1, 2, 2]
   //
   // If a node was not reached by the BFS, its parent is -1, and its distance
   // should also be -1.
   vector<int> GetBfsDistances(const vector<int>& bfs_tree);

   Test: make 2.3
   RENDU: 2.3.cc
   
   
4. Implémentez la fonction GetShortestPathFromRootedTree() décrite dans le fichier 2.4.h:

   #include <vector>
   using std::vector;
   
   // Returns the shortest path, from the source of a BFS to the given target node.
   // The argument is the target node and the BFS "parent" tree.
   // If the target node was not reached by the BFS, the returned path should be
   // empty.
   // Example: using the same example as in 2.3.h, with BFS 'parent' tree:
   // [2, 3, 2, 2, 3, 0]
   // Then:
   // - the shortest path to node #4 should be: [2, 3, 4]
   // - the shortest path to node #0 should be: [2, 0]
   // - the shortest path to node #5 should be: [2, 0, 5]
   // - the shortest path to node #2 should be: [2]
   vector<int> GetShortestPathFromRootedTree(const vector<int>& parent, int target);

   Test: make 2.4
   RENDU: 2.4.cc
   
   
5. Copiez 2.1.h et 2.1.cc dans 2.5.h et 2.5.cc, et modifiez la fonction AddArc() pour qu'elle prenne un argument supplémentaire: double length.
   Modifiez également la fonction Neighbors() pour qu'elle renvoie un const vector<pair<int, double>>&.
   
   Test: make 2.5
   RENDU: 2.5.h et 2.5.cc
   
   
6. (**) Implémentez la fonction Dijkstra() décrite dans le fichier 2.6.h:

   #include "2.5.h"
   
   // Runs a Dijkstra search on the graph, starting from node "src".
   // See https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm .
   // Returns the same "parent" vector as BFS() in 2.2.h.
   vector<int> Dijkstra(const DirectedGraph& graph, int src);

   On utilisera priority_queue<> sur une struct qu'on définira, qui correspond à un noeud du graph associé à sa distance depuis la source, assorti d'un opérateur < adapté à ce qu'on en veut pour la priority_queue.
   La complexité devra être O(N + M log(M)).
   Test: make 2.6
   RENDU: 2.6.cc