Etape 4 – Arcs de graphe

En mathématiques, plus précisément en théorie des graphes, un graphe est défini comme une structure composée d'un ensemble de nœuds, appelés aussi sommets, reliés entre-eux par des liens.

Il existe deux grandes classes de graphes : les graphes non orientés, dans lesquels les liens n'ont pas de sens et sont appelés arêtes, et les graphes orientés, dans lesquels les liens ont un sens et sont appelés arcs. Les graphes utilisés dans les applications de routage sont toujours orientés, et nous ne considérerons donc que ce type de graphe ici.

Les graphes sont souvent représentés visuellement sous la forme d'un ensemble de boîtes représentant les nœuds et de lignes liant ces boîtes entre-elles et représentant les liens. Dans le cas des graphes orientés, la direction des arcs est représentée par des pointes de flèches. Par exemple, l'image ci-dessous montre un graphe orienté comportant 6 nœuds étiquetés de A à F, reliés par 7 arcs : un premier arc va de C à A, un second de A à B, un troisième de A à D, et ainsi de suite. A noter que le nœud E n'est connecté à aucun autre mais fait néanmoins partie du graphe.

Aussi bien les nœuds que les arcs peuvent être annotés avec une information spécifique à l'application. Par exemple, dans un graphe représentant un réseau routier et dont les nœuds sont des villes et les arcs les routes qui les relient, on peut imaginer annoter les nœuds avec les noms et positions géographiques des villes, et les arcs avec la longueur des routes les reliant. Le graphe ci-dessous illustre cette idée avec quatre villes de Suisse romande.

On constate sur ce graphe que certaines paires d'arcs symétriques et annotés identiquement sont représentées par une unique flèche bidirectionnelle, pour alléger la présentation. Par exemple, la flèche bidirectionnelle annotée 64 km et reliant les nœuds Lausanne et Genève représente en fait deux arcs : le premier, annoté 64 km et allant du nœud Lausanne au nœud Genève, et le second, également annoté 64 km, allant du nœud Genève au nœud Lausanne. Toutes les paires d'arcs symétriques sauf celle liant les nœuds Neuchâtel et Fribourg ont été représentées ainsi.

Il existe plusieurs manières de représenter les horaires de transports en commun par un graphe. Pour ce projet, nous utiliserons une représentation nommée graphe dépendant du temps. Dans cette représentation, les nœuds du graphe représentent les arrêts de transports en commun, et les arcs sont annotés avec deux informations relatives au trajet du nœud de départ à celui d'arrivée :

1. la durée de ce trajet à pied,
2. les heures de départ et la durée des différents trajets en transports publics.

La figure ci-dessous donne un exemple fictif d'un tel graphe pour une minuscule région lausannoise. Les sommets sont quatre arrêts (commerciaux) des tl, et les arcs sont annotés avec les deux informations susmentionnées.

En examinant ce graphe, on constate que si l'on se trouve à 9h18 à l'arrêt Bel-Air et que l'on désire se rendre le plus rapidement possible à l'arrêt B.-Constant, la meilleure solution consiste à attendre jusqu'à 9h20 l'arrivée d'un véhicule pour St-François, où on arrive après 3 minutes de trajet (donc à 9h23) puis soit de continuer avec le véhicule qui part à 9h25 et arrive deux minutes plus tard (donc à 9h27) à B.-Constant, soit de continuer à pied pour arriver, en 4 minutes, à 9h27 également. Le trajet dure au total 9 minutes, trois de moins que si l'on fait tout à pied.

On constate par contre que si l'on se trouve à 10h00 à l'arrêt Bel-Air, alors la solution la plus rapide pour se rendre à B.-Constant est de marcher et d'y arriver 12 minutes plus tard. Le prochain véhicule ne circule effectivement pas avant 9h20 le lendemain, à supposer que le graphe du lendemain soit identique.

A noter qu'en consultant un tel graphe, il est impossible de savoir si un changement de véhicule est nécessaire ou pas. Comme expliqué dans le document d'introduction du projet, ce choix a été fait pour simplifier les choses, les erreurs qu'il introduit n'étant généralement pas importantes pour cette application.

Comme la figure 3 l'illustre, les arcs sont annotés avec une liste de trajets, c-à-d une liste de couples (heure de départ, durée du trajet). Avant de pouvoir écrire la classe des arcs, il faut donc décider d'une représentation de ces trajets.

La représentation conforme aux principes de la programmation objet serait, bien entendu, une classe comportant l'heure de départ et la durée du trajet comme champs. Toutefois, comme nous l'avons fait avec les heures elles-mêmes à l'étape 2, nous allons ici enfreindre ces principes dans un soucis de simplicité et d'économie de mémoire et de temps. En fait, la représentation des heures sous forme d'entiers était justifiée uniquement par le souci de pouvoir représenter les trajets de manière efficace.

Lors de l'écriture de la classe SecondsPastMidnight, nous avons décrété que la plus grande valeur d'heure valide était celle représentant 29 h 59 min 59 s, soit 107'999 secondes. Or la plus grande valeur positive que l'on peut stocker dans un entier de type int en Java est 2³¹-1, soit 2'147'483'647. Même la plus grande valeur d'heure valide est loin d'utiliser la totalité de la capacité d'un entier int, et on peut donc se demander s'il n'est pas possible d'y placer les deux composantes d'un trajet.

On constate qu'en multipliant l'heure du trajet par 10'000, on obtient une valeur comprise entre 0 et 1'079'990'000, qui tient encore dans un entier de type int. Cette valeur étant un multiple de 10'000 par construction, ses quatre chiffres les plus à droite, en représentation décimale, sont forcément 0. On peut donc y stocker la durée du trajet, pour peu que celui-ci soit toujours compris entre 0 et 9'999.

Si la durée du trajet est représentée en secondes, 9'999 représente 2 h 46 min 39 s. Cela semble bien au-delà de la durée maximale raisonnable d'un trajet d'un arrêt à un autre dans la région lausannoise.

Pour résumer, les deux composantes d'un trajet, à savoir son heure de départ et sa durée, peuvent être stockées dans un seul entier Java de type int. Il suffit pour cela de placer l'heure de départ, représentée en secondes après minuit, dans les 6 chiffres les plus à gauche (dits de poids fort) de la représentation décimale de cet entier, tandis que la durée, représentée en secondes, est placée dans les 4 chiffres les plus à droite (dits de poids faible).

Prenons par exemple un trajet dont l'heure de départ est 9h20 et la durée 3 minutes. Exprimée en secondes après minuit, l'heure de départ est 33'600. Exprimée en secondes, la durée vaut quant à elle 180. En multipliant la première valeur par 10'000 et en y ajoutant la seconde, on obtient la valeur 336'000'180, qui représente le trajet. Il est facile de voir qu'en divisant cette valeur (de manière entière) par 10'000, on obtient l'heure de départ du trajet exprimée en secondes, tandis qu'en calculant le reste de cette même division, on obtient la durée du trajet en secondes.

Ce genre d'encodages est assez fréquent en informatique. Par exemple, les trois composantes couleur R, G et B des pixels d'une image sont souvent placées toutes ensembles dans un seul entier. Toutefois, les facteurs de multiplication utilisés sont généralement des puissances de 2 et pas de 10 comme ci-dessus, car les opérations de multiplication, division et calcul de reste peuvent alors se faire au moyen d'opérations sur les bits, très rapides. Les personnes à l'aise avec ces encodages peuvent, si elle le désirent, remplacer le facteur multiplicatif de 10'000 utilisé plus haut par 2¹⁴=16'384 et utiliser ensuite les opérateurs sur les bits de Java.

Après avoir décidé de la manière d'encoder les trajets, il reste à savoir où placer les méthodes d'encodage et de décodage. On pourrait les définir comme méthodes statiques d'une classe dont elles seraient la seule raison d'être, à l'image de SecondsPastMidnight, mais étant donné que les trajets ne sont utiles que dans le contexte des arcs de notre graphe, nous placerons ces méthodes directement dans la classe des arcs, définie ci-après.

La classe GraphEdge du paquetage ch.epfl.isochrone.timetable, immuable, finale et visible uniquement dans son paquetage, modélise un arc annoté du graphe des horaires. Elle contient aussi, comme dit précédemment, les méthodes d'encodage et de décodage des trajets.

Pour des raisons qui deviendront claires à la prochaine étape, seul l'arrêt de destination d'un arc est stocké dans l'arc lui-même.

La classe Builder, publique, finale et imbriquée statiquement dans la classe GraphEdge sert de bâtisseur à la classe Edge.

Comme pour l'étape précédente, nous vous fournissons des « tests » minimalistes qui ne font rien d'autre que s'assurer que vous n'avez pas commis de faute bête dans le nommage ou la visibilité des entités à définir. Ils se trouvent dans l'archive Zip tests-e04.zip.

N'oubliez donc pas de les compléter, et de bien tester vos méthodes d'encodage et de décodage de trajets, ainsi que la méthode earliestArrivalTime, probablement la plus complexes de cette étape.