Les systèmes de contrôle de version utilisent de manière sous-jacente un graphe pour organiser les versions successives d’un projet. Néanmoins les algorithmes de graphe classiques peuvent se heurter aux spécificités des graphes de révision. D’une part, les graphes reçoivent très fréquemment des nouveaux sommets et des informations pré-calculées peuvent devenir obsolètes à chaque commit. D’autre part, deux utilisateurs différents peuvent avoir une vue différente sur le graphe, y compris sur les sommets qu’ils ont en commun.
Nous proposons une approche dichotomique donnant une stratégie de découpe de profondeur logarithmique du graphe. Nous appliquons cette méthode à deux problèmes: (1) la comparaison d’annotations entre deux vues d’un même graphe, et (2) la recherche de chemin dans le graphe. Pour le second problème, nous présentons également un algorithme basé sur la décomposition du graphe en chaînes totalement ordonnées.
Cette présentation est basée sur plusieurs travaux en collaboration avec Pierre-Yves David , Florian Horn and Euxane Tran-Girard :
https://hal.science/hal-04929088v1
https://hal.science/hal-04778558v1
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne