É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 NodeJS Express écrite en TypeScript. Les objectifs sont les suivants :

Pour cela, nous commencerons par une revue de code en séance et procéderons 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

Nous remarquons que le modèle ne protège pas contre les erreurs la création des sommets et des arcs. Il est 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 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, nous passerons de :

const a = new Vertex();
a.id = "a";
a.coordinates = [0.0, 0.0];
graph.vertices.push(a);

const b = new Vertex();
b.id = "b";
b.coordinates = [1.0, 0.0];
graph.vertices.push(b);

const ab = new Edge(a, b);
ab.id = "ab";
graph.edges.push(ab);

à

const a = graph.createVertex([0.0, 0.0],"a");
const b = graph.createVertex([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 Edge.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 BdtopoLoader 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 RoutingService, 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 - 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 RoutingService en limitant les reprises de code à effectuer :

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

Pour finaliser la mise en oeuvre d'un modèle dédié à l'arbre de plus court chemin, nous encapsulons nodes: Map<Vertex, PathNode> de RoutingService sous forme d'un arbre de plus court chemin nommé PathTree :

0.9 - Stockage des seuls sommets atteints dans PathTree

Nous remarquons qu'il est inutile de stocker des PathNode pour tous les sommets du graphe. Il suffit d'initialiser la liste des nodes avec l'origine des chemins et de créer les PathNode quand de nouveaux sommets sont atteints.

A l'exception du test pour savoir si la destination est atteinte dans RoutingService, les appels à getNode correspondent à des sommets atteints.

Nous allons donc :