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 :
- Rendre le code plus robuste
- Optimiser le calcul de plus court chemin
- Rendre le calcul de plus court chemin plus générique
- Améliorer les entrées/sorties du programme
Pour cela, nous allons faire une revue de code et procéder par étape.
Démarrage
- Forker le projet https://github.com/mborne/tp-refactoring-graph
- Cloner le fork
- Lire le fichier README pour :
- Découvrir l'organisation du code
- Construire le projet et exécuter les tests
- Démarrer et tester l'API
Mise en garde
Vous devrez impérativement :
- Livrer un code fonctionnel sur la branche par défaut de votre fork.
- Avoir au moins un commit (voire une branche) par question avec un commentaire permettant de l'identifier
Pour ce faire, il vous est vivement conseillé de :
- Lancer à chaque étape la construction et les tests automatiques (
mvn clean package
). - Compléter ces tests automatiques avec un test manuel sur l'API.
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 :
- Ajout d'un constructeur
Edge(source: Vertex, target: Vertex)
- Suppression du constructeur par défaut sur
Edge
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 :
- Ajout d'une fabrique
createVertex(coordinate: Coordinate, id: String): Vertex
dansGraph
- Ajout d'une fabrique
createEdge(source: Vertex, target: Vertex, id: String): Edge
dansGraph
- Masquage des constructeurs
Vertex()
etEdge(source,target)
- Suppression de
Graph.setVertices(vertices)
etGraph.setEdges(edges)
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
:
- Ajout d'un attribut
geometry: LineString
sur la classeEdge
avec un settersetGeometry(geometry: LineString)
- Mise à jour de
getGeometry()
pour renvoyer l'attributgeometry
s'il est défini - Mise à jour de
getCost()
pour renvoyer la longueur de la géométrie à l'aide de getLength de JTS - Mise à jour de
GraphReader
pour stocker la géométrie sur lesEdge
à l'aide desetGeometry
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 :
- Suppression de
setSource
etsetTarget
dansEdge
(1) - Ajout des attributs
inEdges: List<Edge>
etoutEdges: List<Edge>
surVertex
(2). - Ajout des getters
getInEdges(): List<Edge>
etgetOutEdges(): List<Edge>
surVertex
- Remplissage automatique de
inEdges
etoutEdges
dans le constructeurEdge(source,target)
- Ré-écrire
Graph.getInEdges
etGraph.getOutEdges
pour appelerVertex.getInEdges
etVertex.getOutEdges
- Exclure
inEdges
etoutEdges
du rendu JSON au niveau de l'API à l'aide de l'annotation@JsonIgnore
(3).
Remarques :
- (1) Nous n'avons pas besoin d'éditer les graphes après chargement, il est donc inutile de conserver
setSource
etsetTarget
qui complexifieraient la gestion deinEdges
etoutEdges
. - (2) Nous n'avons pas besoin pour l'algorithme actuel des
inEdges
mais nous choisissons de conserver une symétrie dans le modèle. - (3) ATTENTION : Sans cette étape, l'API plantera avec une récursion infinie.
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 :
- Au renvoi d'une
NotFoundException
dansGraph.findVertex(id: String)
dans le cas où le sommet n'est pas trouvé par son identifiant - A la personnalisation du rendu des
NotFoundException
viaconfig.CustomErrorHandler
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 :
edges
: La liste des arcs formant le cheminlength
: La somme des longueurs desedges
Pour ce faire, nous procédons ainsi :
- Ajout d'un modèle
Path
encapsulant une liste deEdge
nomméeedges
. - Ajout d'une méthode
getLength()
àPath
renvoyant la somme des longueurs desedges
. - Renvoi d'un
Path
dansfindPath
deDijkstraPathFinder
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 :
- Création d'une classe
PathNode
correspondant à un noeud de l'arbre - Migration des attributs
cost
,reachingEdge
etvisited
deVertex
versPathNode
- Ajout d'une propriété
nodes: Map<Vertex,PathNode>
dansDijkstraPathFinder
- Mise à jour de
initGraph
dansDijkstraPathFinder
pour initialisernodes
- Ajout d'une méthode utilitaire
getNode(vertex: Vertex): PathNode
dansDijkstraPathFinder
- Mise à jour du reste du code de la classe
DijkstraPathFinder
à l'aide degetNode
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
:
- Création de la classe
PathTree
- Migration des éléments correspondant de
DisjktraPathFinder
versPathTree
initGraph(origin)
devientPathTree(graph: Graph, origin: Vertex)
buildPath(vertex)
devientpathTree.getPath(destination: Vertex)
getNode(vertex)
devientpathTree.getNode(vertex: Vertex)
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 :
- Ajout d'une méthode
pathTree.isReached(destination: Vertex): boolean
pour clarifierpathTree.getNode(destination).getReachingEdge() != null
- Blindage de
pathTree.getPath(destination)
dans le cas où le sommet n'est pas atteint - Ajout d'une méthode
getOrCreateNode(vertex)
dansPathTree
et utilisation de cette méthode dansDijkstraPathFinder
- Reprise du constructeur
PathTree(graph, origin)
enPathTree(origin)
- Ajout de
pathTree.getReachedVertices(): Collection<Vertex>
- Parcourt des seuls sommets atteints dans
findNextVertex
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)
:
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
:
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
:
- Ajout de
vertex: Vertex
surPathNode
- Remplacement de la
Map<Vertex,PathNode>
par uneIndexedCollection<PathNode> nodes
surPathTree
- Ajout de
markVisited(vertex)
surPathTree
(2) - Ajout de
setReached(vertex,reachingCost,reachingEdge)
surPathTree
(2) - Ajout de
getNearestNonVisitedVertex(): Vertex
surPathTree
- Utilisation de
getNearestNonVisitedVertex()
dePathTree
dansfindNextVertex()
deDijkstraPathFinder
Remarque :
- (1) Une démonstration de l'utilisation de CQEngine est présente dans les tests : CqEngineTest
- (2) Pour que les indexes se mettent à jour lors des modifications des
PathNode
, il faut supprimer lePathNode
de la collection, modifier lePathNode
et le ré-ajouter à la collection.
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
:
- Extraction d'une méthode
buildTree(destination)
dansfindPath
0.13 - Extraction d'une classe PathTreeBuilder de DijkstraPathFinder
- Création d'une classe
PathTreeBuilder
avec un constructeurPathTreeBuilder(origin: Vertex)
- Migration de
buildTree
,visit
etfindNextVertex
deDijkstraPathFinder
versPathTreeBuilder
- Utilisation de
PathTreeBuilder
dansDijkstraPathFinder
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 :
- Création d'une interface
NextVertexFinder
avec une méthodefindNextVertex(pathTree: PathTree): Vertex
- Implémentation de
DijkstraNextVertexFinder
- Le constructeur
PathTreeBuilder(pathTree)
devientPathTreeBuilder(nextVertexFinder, pathTree)
0.15 - Implémentation de A-star
On ajoute l'implémentation de A-star comme suit :
- Modification de
findNextVertex(pathTree)
enfindNextVertex(pathTree,destination)
au niveau de l'interfaceNextVertexFinder
- Ajout de
AStarNextVertexFinder
implémentantNextVertexFinder
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 :
- Création d'une fabrique
NextVertexFinderFactory.createNextVertexFinder(method: String)
- Renommage de
DijkstraPathFinder
enPathFinder
- Ajout du paramètre
method: String
àfindPath
dePathFinder
- Ajout d'un paramètre
method
àfindPath
dansFindPathController