Etape 5 – Graphe et arbre des trajets

Pour cette étape, la classe Graph est triviale puisqu'elle n'est équipée que du constructeur privé suivant :

• Graph(Set<Stop> stops, Map<Stop, List<GraphEdge>> outgoingEdges), qui construit un graphe avec les arrêts donnés comme nœuds et les arcs spécifiés dans la table associative. Cette table associe à un arrêt—donc un nœud du graphe—la liste des arcs qui partent de ce nœud.

Lors d'une étape ultérieure vous ajouterez à cette classe une méthode permettant de calculer les trajets les plus rapides d'un arrêt de départ vers tous les autres arrêts du réseau, mais pour l'instant elle ne contient rien d'autre que ce constructeur privé.

La raison pour laquelle le constructeur est privé est de s'assurer que celui-ci ne puisse être appelé que depuis le bâtisseur défini ci-dessous. Cela permet de simplifier un peu les choses, car si le bâtisseur garantit que les paramètres qu'il passe au constructeur de Graph sont valides et ne sont jamais modifiés par la suite, le constructeur n'a ni besoin de les vérifier, ni de les copier.

Cette simplification est discutable, et les personnes qui désireraient rendre le constructeur public peuvent le faire. Toutefois, il faut alors que leur constructeur fasse la vérification de ses arguments, et les copie ensuite en profondeur.

La vérification des arguments consiste à s'assurer que tous les arrêts qui apparaissent comme clefs dans la table associative sont présents dans l'ensemble des arrêts passée en premier argument, de même que tous ceux qui servent de destination aux arcs stockés comme valeurs dans cette même table.

Quant à la copie profonde des arguments, elle est très simple à faire pour l'ensemble des arrêts mais beaucoup moins pour la table des arcs, celle-ci contenant des listes qui pourraient elles-aussi être modifiées, et qui doivent donc également être copiées.

A noter que même si le constructeur est privé, il peut être judicieux de vérifier la validité des arguments, afin de détecter d'éventuels problèmes dans le bâtisseur. Dans ce cas, la vérification pourra toutefois se faire au moyen d'une assertion plutôt que d'un if.

La classe Graph.Builder est équipée d'un unique constructeur public :

• Builder(Set<Stop> stops), qui construit un bâtisseur pour un graphe d'horaire ayant les arrêts passés en argument comme nœuds.

et des méthodes suivantes :

• Builder addTripEdge(Stop fromStop, Stop toStop, int departureTime, int arrivalTime), qui ajoute au graphe en construction un trajet entre les arrêts de départ et d'arrivée donnés, aux heures données (en secondes après minuit). Lève l'exception IllegalArgumentException si l'un des deux arrêts ne fait pas partie de ceux passés au constructeur, si l'une des deux heures est négative, ou si l'heure d'arrivée est antérieure à l'heure de départ. Attention : une heure d'arrivée égale à l'heure de départ doit être tolérée, car cette situation se retrouve effectivement dans les horaires de transports en commun pour des arrêts très proches. Retourne this afin de permettre les appels chaînés.
• Builder addAllWalkEdges(int maxWalkingTime, double walkingSpeed), qui ajoute au graphe en construction la totalité des trajets à pied qu'il est possible d'effectuer entre n'importe quelle paire d'arrêts, en un temps inférieur ou égal au temps maximum de marche passé (en secondes), à la vitesse de marche donnée (en mètres par seconde). Lève l'exception IllegalArgumentException si le temps maximum de marche est négatif, ou si la vitesse de marche est négative ou nulle. Retourne this afin de permettre les appels chaînés.
• Graph build(), qui construit et retourne un nouveau graphe avec les nœuds passés à la construction du bâtisseur et les arcs ajoutés jusqu'à présent.

La méthode addAllWalkEdges doit faire l'hypothèse qu'il est toujours possible de marcher en ligne droite de n'importe quel point à un autre, et donc que le temps de marche entre deux arrêts ne dépend que de la distance qui les sépare et pas du sens du parcours. Dès lors, addAllWalkEdges ne doit considérer qu'une fois chaque paire d'arrêts et, si et seulement si la distance qui les sépare est inférieure à la distance maximale de marche, ajouter deux trajets à pied au graphe en cours de construction, un pour chaque sens.

La manière la plus simple de considérer chaque paire d'arrêts consiste à les mettre dans un tableau (ou plutôt une ArrayList) et à faire deux boucles imbriquées : la boucle extérieure parcourt tous les arrêts dans l'ordre, tandis que la boucle intérieure ne parcourt que les arrêts d'indice strictement supérieur à celui actuellement visité par la boucle extérieure.

Par exemple, pour un tableau contenant les éléments suivants :

A

B

C

D

E

le parcours se fait selon la table ci-dessous, dans laquelle la colonne de gauche donne les itérations de la boucle extérieure (de haut en bas) tandis que la colonne de droite donne les itérations de la boucle intérieure (de gauche à droite).

Ext.	Int.
A	B, C, D, E
B	C, D, E
C	D, E
D	E
E

Les paires de valeurs considérées dans cet exemple sont donc, dans l'ordre, (A, B), (A, C), (A, D), (A, E), (B, C), (B, D), (B, E), (C, D), (C, E) et enfin (D, E).

Les méthodes addTripEdge et addAllWalkEdges doivent toutes les deux pouvoir obtenir le bâtisseur d'un arc étant donnés les nœuds de départ et d'arrivée de cet arc.

Il est donc recommandé de leur offrir une méthode privée permettant, étant donnés un arrêt de départ et un arrêt d'arrivée, d'obtenir le bâtisseur de l'arc correspondant, en le créant au besoin.

Ces bâtisseurs d'arcs peuvent être stockés dans un champ privé du bâtisseur de graphe et de type Map<Stop, Map<Stop, GraphEdge.Builder>>. Comme son type l'indique, ce champ contient une première table associative qui associe à chaque arrêt de départ une autre table associative. Ces tables associatives de niveau 2 associent quant à elles un bâtisseur d'arc à un arrêt d'arrivée. La figure ci-dessous montre ce que pourrait contenir ce champ à un stade où les trajets suivants ont été ajoutés :

• un trajet de St-François à Georgette partant à 9h24 et durant 4 minutes,
• un trajet de St-François à B.-Constant partant à 9h20 et durant 1 minute,
• un trajet de Georgette à St-François partant à 9h18 et durant 5 minutes,
• le trajet à pied entre St-François à Georgette, dans les deux sens, durant 6 minutes.

Gérer correctement cette table associative de tables associatives est de loin l'aspect le plus complexe de cette classe, soyez donc sûr de bien comprendre comment le faire avant de vous mettre à programmer.

La classe FastestPathTree est équipée d'un seul constructeur public :

• FastestPathTree(Stop startingStop, Map<Stop, Integer> arrivalTime, Map<Stop, Stop> predecessor), qui construit un arbre des trajets les plus rapides avec l'arrêt de départ, la table des heures d'arrivée et la table des prédécesseurs donnés. La table des heures d'arrivée associe à un certain nombre d'arrêts l'heure de première arrivée à cet arrêt (en secondes après minuit). La table des prédécesseurs associe à chaque arrêt son prédécesseur dans l'arbre. Lève l'exception IllegalArgumentException si l'ensemble des clefs de la table des heures n'est pas égal à celui des clefs de la tables des prédécesseurs plus l'arrêt de départ.

Cette classe est de plus équipée des méthodes publiques suivantes :

• Stop startingStop(), qui retourne l'arrêt de départ.
• int startingTime(), qui retourne l'heure de départ, qui n'est autre que l'heure de première arrivée à l'arrêt de départ.
• Set<Stop> stops(), qui retourne l'ensemble des arrêts pour lesquels une heure de première arrivée existe.
• int arrivalTime(Stop stop), qui retourne l'heure d'arrivée à l'arrêt donné ou SecondsPastMidnight.INFINITE si l'arrêt donné n'est pas dans la table des heures d'arrivée passée au constructeur.
• List<Stop> pathTo(Stop stop), qui retourne le chemin pour aller de l'arrêt de départ à celui passé en argument. Lève l'exception IllegalArgumentException si l'arrêt passé n'est pas présent dans la table des heures d'arrivée. La liste retournée doit avoir l'arrêt de départ comme premier élément et l'arrêt passé en argument comme dernier élément. De plus, chaque paire d'éléments successifs doit être lié par un arc dans l'arbre.

Les deux tables passées au constructeur de FastestPathTree représentent chacune un aspect de l'arbre des trajets les plus rapides décrit plus haut. La table des heures d'arrivée contient l'heure de la première arrivée possible à chaque arrêt, tandis que la table des prédécesseurs décrit les arcs.

Ainsi, pour l'arbre des trajets les plus rapides donné en exemple à la figure 1, ces deux tables ressembleront à ceci :

On peut se demander pourquoi on utilise deux tables alors qu'une seule, associant à chaque arrêt à la fois l'heure de première arrivée et le prédécesseur, aurait suffi. La raison est que cela nous aurait forcé à définir une classe supplémentaire pour représenter ce couple formé de l'heure de première arrivée et du prédécesseur. Même si cela est tout à fait faisable, et probablement légèrement plus propre, la solution retenue a l'avantage de la simplicité.

Prenez garde à garantir l'immuabilité de la classe FastestPathTree en gérant les différents problèmes mentionnés dans les énoncés précédents avec des classes similaires.

La classe Builder est équipée du constructeur public suivant :

• Builder(Stop startingStop, int startingTime), qui construit un bâtisseur pour un arbre des trajets les plus rapides avec l'arrêt et l'heure de départ donnés. Dans cet arbre en construction, l'heure de première arrivée de l'arrêt de départ doit être l'heure de départ. Lève l'exception IllegalArgumentException si l'heure de départ est négative.

et des méthodes publiques suivantes :

• Builder setArrivalTime(Stop stop, int time, Stop predecessor), qui (re)définit l'heure de première arrivée et le prédécesseur de l'arrêt donné dans l'arbre en construction. Lève l'exception IllegalArgumentException si l'heure donnée est antérieure à l'heure de départ.
• int arrivalTime(Stop stop), qui retourne l'heure de première arrivée à l'arrêt donné, ou SecondsPastMidnight.INFINITE si aucune heure d'arrivée n'a été attribuée à cet arrêt jusqu'ici.
• FastestPathTree build(), qui construit l'arbre des trajets les plus rapides avec les nœuds ajoutés jusqu'ici.