Abstract FR:

Des applications techniques telles que la gestion des réseaux routiers et électriques nécessitent de manipuler un grand volume d'information structurée sous la forme de graphe. Des problèmes typiques portent sur des parcours de chemins (par exemple, calcul du plus court chemin, du chemin avec la capacité maximale, du nombre de sous-composants d'un composant). Trois aspects principaux rendent difficile l'utilisation des algorithmes classiques pour résoudre ces problèmes a savoir, la taille des réseaux, la complexité de la structure des réseaux et la diversité des sources de données. Dans cette thèse, nous proposons un cadre base sur la notion de vue de graphe qui permet la définition des opérations de graphes et s'adapte à leur diversité de représentations. Une vue de graphe définit un graphe spécifique à partir des données stockées dans des sources différentes. La définition d'une vue de graphe consiste à établir une correspondance entre les éléments d'un graphe et les données sous-jacentes par l'intermédiaire de fonctions qui spécifient les éléments du graphe et la façon par laquelle le graphe peut être parcouru. Des opérateurs de dérivation sont proposes pour définir des nouvelles vues de graphes à partir de celles existantes. Ces opérateurs permettent la composition, dans une seule vue de graphe, de graphes contenant des étiquettes différentes de nœuds et des arcs et issus d'implémentations différentes. Des opérations de graphes telles que les parcours de chemins peuvent entre appliquées sur des vues de graphe de base et dérivées. La spécialisation d'un mécanisme de vue au problème spécifique de gestion de graphes, nous permet de proposer des stratégies adaptées au traitement des opérations de parcours de chemins. Nous validons le cadre proposé en supportant l'opération de fermeture transitive généralisée qui permet de résoudre une variété des problèmes de parcours de chemins. Une évaluation analytique des stratégies a été accomplie, nous permettant d'identifier les paramètres principaux qui influencent le comportement des stratégies pour le traitement de cette opération. Les résultats de cette évaluation ont été partiellement valides par un prototype qui implémente les idées principales du cadre proposé