Éditer sur GitHub

TP - Refactoring de traitement de graphe

Introduction

Dans ce TP, l'idée est de se mettre en situation où nous devons industrialiser un prototype. Nous allons réfactorer une application qui charge un graphe et calcule le plus court chemin entre deux sommets.

L'application se présente sous la forme d'une API basée sur spring boot

Les objectifs sont les suivants :

Pour cela, nous allons faire une revue de code et procéder par étape.

Démarrage

Mise en garde

Vous devrez impérativement :

Pour ce faire, il vous est vivement conseillé de :

0.1 - Blindage de la construction des arcs

On remarque que l'on dispose d'un modèle qui ne protège pas contre les erreurs la création des sommets et des arcs. Il est tout à fait possible de créer par erreur un Edge avec une source ou une target nulle.

On procède comme suit :

0.2 - Ajout de fabriques pour les sommets et les arcs

En ajoutant un constructeur Edge(source: Vertex, target: Vertex), on remarque que l'on a simplifié la création des arcs et des sommets.

Toutefois, les opérations de création demeurent complexes et il reste la possibilité d'oublier d'ajouter les éléments aux listes de vertices et edges du graphe.

On va donc procéder comme suit :

Ainsi, on passera de :

Vertex a = new Vertex();
a.setId("a");
a.setCoordinate(new Coordinate(0.0, 0.0));
graph.getVertices().add(a);

Vertex b = new Vertex();
b.setId("b");
b.setCoordinate(new Coordinate(1.0, 0.0));
graph.getVertices().add(b);

Edge ab = new Edge(a, b);
ab.setId("ab");
graph.getEdges().add(ab);

à

Vertex a = graph.createVertex(new Coordinate(0.0, 0.0),"a");
Vertex b = graph.createVertex(new Coordinate(1.0, 0.0),"b");
graph.createEdge(a,b,"ab");

0.3 - Géométrie réelle des tronçons

On remarque au niveau de getCost et getGeometry que la géométrie des tronçons est un segment entre le sommet source et le sommet cible. La géométrie réelle est lue dans GraphReader mais elle n'est pas exploitée lors de la création du graphe.

On va procéder comme suit pour ajouter la géométrie réelle des tronçons de route sur les Edge :

0.4 - Indexation des arcs entrants et sortants

En lisant attentivement DijsktraPathFinder (ou un utilisant un outil de profilage tel VisualVM), on remarque que la méthode graph.getOutEdges(vertex: Vertex) est appelée très fréquemment dans la méthode visit(vertex: Vertex).

Cette approche étant loin d'être optimale, nous allons indexer les arcs sortants et entrants comme suit :

Remarques :

0.5 - Amélioration de la gestion des chemins non trouvés

Nous remarquons que findPath(Vertex origin, Vertex destination) de DijkstraPathFinder renvoie null si le chemin n'est pas trouvé. Ceci induit une réponse vide au niveau de l'API qui ne sera pas facile à interprétée par le client.

En comparaison, le cas où le sommet de départ ou d'arrivé est mieux géré grâce :

Nous procédons de même en renvoyant une NotFoundException avec le modèle de message suivant dans findPath(Vertex origin, Vertex destination) de DijkstraPathFinder : "Path not found from '%s' to '%s'".

0.6 - Amélioration du rendu des chemins

Nous remarquons que la mise en forme des chemins est un peu pauvre au niveau de l'API. Nous souhaitons produire un résultat sous forme d'un objet JSON avec deux propriétés :

Pour ce faire, nous procédons ainsi :

0.7 - Création d'un modèle dédié aux noeuds de l'arbre du plus court chemin

Nous constatons que Vertex est porteur de propriétés qui ne correspondent pas à la modélisation d'un réseau routier mais à l'algorithme de calcul du plus court chemin : cost, reachingEdge et visited.

Ceci a un lourd impact sur l'application : Il est en l'état impossible de lancer en parallèle deux calculs de plus court chemin car il y a aurait des conflits en édition sur les propriétés des Vertex pendant l'exécution de l'algorithme.

Nous procédons dans un premier temps comme suit pour refondre DijkstraPathFinder en limitant les reprises de code à effectuer :

0.8 - Création d'un modèle dédié à l'arbre du plus court chemin

On encapsule nodes: Map<Vertex, PathNode> de DijkstraPathFinder sous forme d'un arbre de plus court chemin nommé PathTree :

0.9 - Stockage des seuls sommets atteints dans PathTree

On remarque qu'il est inutile de stocker des PathNode pour tous les sommets du graphe, qu'il suffit d'initialiser la liste des nodes avec l'origine des chemins et de créer les PathNode quand on atteint de nouveaux sommets.

A l'exception du test pour savoir si on a atteint la destination dans DijkstraPathFinder, les appels à getNode correspondent à des sommets atteints.

On procède donc comme suit :

0.10 - Optimisation du chargement du graphe

En chargeant ROUTE500 complet, on observe un temps de chargement excessivement long. A l'aide de VisualVM, on se rend compte que le programme passe le plus clair de son temps dans GraphReader.getOrCreateVertex faisant appel à Graph.findVertex(coordinate: Coordinate) :

VisualVM - chargement du graphe

En inspectant Graph.findVertex(coordinate: Coordinate), on note un parcours complet des sommets à la recherche d'une égalité stricte de coordonnée. Cette approche est loin d'être optimale, nous pouvons optimiser en utilisant une Map<Coordinate, Vertex>.

0.11 - Optimisation du temps de calcul

En lançant des calculs de plus court chemin sur le graphe ROUTE500 complet, on remarque un temps de calcul trop important. A l'aide de VisualVM, on se rend compte que le programme passe le plus clair de son temps dans findNextVertex :

VisualVM - find path

En regardant de plus près, on remarque que l'on parcours l'ensemble des sommets atteints pour filtrer ensuite les sommets déjà visités.

for (Vertex vertex : pathTree.getReachedVertices()) {
    PathNode node = pathTree.getNode(vertex);
    // sommet déjà visité?
    if (node.isVisited()) {
        continue;
    }
    //...

On s'appuie sur la bibliothèque CQEngine (1) pour obtenir une collection de PathNode avec plusieurs indexes au niveau du PathTree :

Remarque :

0.12 - Préparation de la mise en oeuvre de variantes de l'algorithme

Afin de préparer la mise en oeuvre de variante de l'algorithme, on s'efforce de bien identifier les différentes étapes de la construction de l'arbre. Aussi, on veille à séparer la construction de l'arbre de production du résultat en procédant comme suit dans DijkstraPathFinder :

0.13 - Extraction d'une classe PathTreeBuilder de DijkstraPathFinder

0.14 - Préparation de la mise en place d'une stratégie de calcul du plus court chemin

Afin de pouvoir faire varier par la suite la méthode findNextVertex entre Dijkstra et A-star, on extrait une stratégie comme suit :

0.15 - Implémentation de A-star

On ajoute l'implémentation de A-star comme suit :

Remarque : Dans le cas de A-star, findNextVertex(pathTree,destination) renverra le sommet atteint minimisant "distance parcourue depuis l'origine + distance à vol d'oiseau pour atteindre la destination"

0.16 - Choix de la stratégie de calcul dans l'API

On procède comme suit pour permettre le choix d'une stratégie de calcul dans l'API :