É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 avec un démonstrateur OpenLayers :

Démonstrateur

Objectifs

Les objectifs sont les suivants :

Pour cela, nous procéderons par étape.

Démarrage

Mises en garde

Le TP a été modifié par rapport aux sessions précédentes (vous ne devez pas exploiter les forks existants). En outre, vous devrez impérativement :

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

0.1 - Blindage de la construction des arcs

Nous remarquons que le modèle 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.

Nous procédons comme suit :

0.2 - Ajout de fabriques pour les sommets et les arcs

En ajoutant un constructeur Edge(source: Vertex, target: Vertex), nous remarquons que nous avons 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.

Nous allons donc procéder comme suit :

Ainsi, à l'usage, nous passerons 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

Nous remarquons 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.

Nous allons 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), nous remarquons 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éter 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 pour les chemins non trouvés comme suit:

0.6 - 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.7 - Création d'un modèle dédié à l'arbre du plus court chemin

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

0.8 - Stockage des seuls sommets atteints dans PathTree

Nous remarquons 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.

Nous procédons donc comme suit :

0.9 - Optimisation du chargement du graphe

En chargeant ROUTE500 complet, nous observons un temps de chargement excessivement long. A l'aide de VisualVM, nous constatons que le programme passe le plus clair de son temps dans GraphReader.getOrCreateVertex qui fait appel à Graph.findVertex(coordinate: Coordinate) :

VisualVM - chargement du graphe

En inspectant Graph.findVertex(coordinate: Coordinate), nous remarquons 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.10 - Optimisation du temps de calcul

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

VisualVM - find path

En regardant de plus près findNextVertex, nous remarquons que nous parcourons 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;
    }
    //...

Nous allons donc nous appuyer sur la bibliothèque CQEngine (1) pour obtenir une collection de PathNode avec un indexe multiple ((visited,cost)) au niveau du PathTree comme suit :

Remarque :

0.11 - Calcul d'isochrone

Nous allons procéder comme suit pour ajouter une fonctionnalité de calcul d'isochrone :

Pour le calcul du polygone dans findIsochrone, nous procéderons comme suit :

Remarques :

0.12 - Démonstrateur pour les isochrones (Bonus)

Améliorer le démonstrateur pour permettre l'utilisation des deux fonctionnalités suivantes :

Remarques : Vous pouvez aussi améliorer les contrôles pour mieux présenter la sélection du point de départ et d'arrivé, le lancement et la fin des traitements,...