Informatique
II-3. Les Opérateurs de Haut Niveau
Yüklə 2,35 Mb.
|
- Bu səhifədəki naviqasiya:
- II-3.1 Lopérateur de CHEMINS
- II-3.1.1 Notion dapproximation et structure de données
- II-3.1.2 Spécification de lopérateur de CHEMINS
- II-3.1.3 Illustration par un exemple
II-3. Les Opérateurs de Haut NiveauDans cette partie, nous présentons les opérateurs directement liés à l'utilisateur d'un SIG de type réseau. Ces opérateurs permettent à l'utilisateur d'interroger le SIG. Ces opérateurs de haut niveau se divisent en trois classes, correspondant aux requêtes les plus courantes adressées à un SIG [13] : l'évaluation d'un chemin (opérateur de CHEMINS), l'intersection de chemins (opérateurs d'INTERSECTION) et l'inclusion de chemins (opérateurs d'INCLUSION). Les résultats d'une requête sont présentés au plus haut niveau d'abstraction du graphe résultant de ces opérateurs. L'opérateur de CHEMINS est un opérateur ternaire. Les opérateurs d'INTERSECTION et d'INCLUSION sont des opérateurs binaires. II-3.1 L'opérateur de CHEMINSL'opérateur de CHEMINS est inspiré de l'opérateur de chemin de la théorie des graphes. Cependant, il intègre la notion d'abstraction du modèle de graphe choisi. Cet opérateur rend pour résultat l'ensemble des chemins vérifiant certaines conditions. Ces conditions peuvent être des critères, des contraintes agrégatives ou des contraintes régulières. Le résultat de cet opérateur est donc un ensemble de graphes (un graphe représentant un chemin). L'opérateur de CHEMINS renvoie pour résultat des chemins "exacts" ou des chemins "approximés". Définissons tout d'abord les notions de chemin, de chemin exact et de chemin approximé.
L'opérateur de CHEMINS approxime certains noeuds et arcs du graphe ne possédant pas de chemin exact dans leurs réseaux_associés. Le plus haut niveau d'abstraction du graphe rendu sera un chemin, mais les niveaux inférieurs ne correspondront pas obligatoirement à un chemin. Cette notion d'approximation permet de rendre à l'utilisateur un résultat le plus complet possible : plutôt que de lui dire qu'il n'existe pas de chemin pour aller de Paris à Lyon, il est préférable de lui dire qu'il existe un chemin de Paris à Blois et de Blois à Lyon, mais que le chemin suivi à l'intérieur de Blois n'est pas décrit. L'opérateur de CHEMINS (noté PT) est un opérateur ternaire. Appliqué sur deux noeuds et un graphe, il permet d'obtenir un ensemble de chemins à partir du graphe. Chaque graphe résultat est un graphe hiérarchisé de même structure que le graphe hiérarchisé initial. La différence principale avec un opérateur classique de chemins réside dans la notion d'abstraction du modèle de graphe. L'opérateur de CHEMINS permet de trouver des chemins à tous les niveaux d'abstraction d'un graphe. La signature de l'opérateur de CHEMINS est présentée Figure III-48.
Figure III-48. Signature de l'opérateur de CHEMINS Une condition est exprimée sur les chemins à rechercher. Cette condition peut regrouper des critères, des contraintes agrégatives et des contraintes régulières. La vérification des critères s'effectue par l'appel de l'opérateur de SELECTION, précédant l'appel de l'opérateur de CHEMINS. Les contraintes régulières (représentées par l'expression contrainte_régulière) et les contraintes agrégatives (représentées par l'expression contrainte_agrégative) sont vérifiées durant l'exécution de l'opérateur de CHEMINS. Les contraintes agrégatives sont vérifiées à l'aide d'une fonction, Vérif_Contrainte_Agrégative. Les contraintes sont vérifiées sur chaque noeud et master_noeud n'appartenant pas à un réseau_associé à un master_noeud (appartenant au graphe ou au réseau_associé d'un master_arc), et pour chaque arc et master_arc n'appartenant pas au réseau_associé d'un master_arc (appartenant au graphe ou à un réseau_associé d'un master_noeud). La signature de la fonction Vérif_Contrainte_Agrégative est illustrée Figure III-49. Cette fonction est appelée sur chaque noeud et arc rencontré. Si le noeud ou l’arc ne correspond pas aux conditions exprimées, cette fonction retourne Vrai.
Figure III-49. Signature de la fonction Vérif_Contrainte_Agrégative Les contraintes régulières sont vérifiées sur chaque noeud et chaque arc rencontré lors de la recherche de chemin. Cette vérification est faite par l'appel d'un module, Vérif_Contrainte_Régulière. Ce module prend en entrée un automate construit à partir de l'expression régulière représentant la contrainte, un état d'entrée de l'automate, et un graphe contenant le noeud ou l'arc étudié. Il retourne un état de sortie de l'automate (état de sortie résultant de la poursuite de l'automate par le noeud ou l'arc étudié, à partir de l'état d'entrée), et un booléen indiquant si une situation correspondait effectivement au noeud ou arc étudié ou si aucune situation leur correspondant n'a pu être trouvée pour poursuivre l'automate. L'automate considéré par ce module est un graphe plat (un seul niveau de hiérarchie) contenant des noeuds et des arcs. Chaque noeud et arc est labellé. La succession des labels de ces noeuds et arcs forme une expression régulière. L'état d'entrée d'un tel automate est un graphe contenant les noeuds et arcs déjà parcourus de l'automate. Son état de sortie est un graphe contenant les noeuds et arcs déjà parcourus augmentés, si besoin est, du noeud ou de l'arc considéré par le module. La signature de ce module est illustrée Figure III-50.
Figure III-50. Signature du module Vérif_Contrainte_Régulière La signature de l'opérateur de chemins correspond à la signature illustrée dans la Figure III-48, augmentée des contraintes agrégatives et de l'automate correspondant aux contraintes régulières. Pour faciliter la lecture, nous ne notons le passage en paramètres de ces contraintes que lorsque cela s'avère nécessaire à la compréhension. II-3.1.1 Notion d'approximation et structure de donnéesUn noeud (resp. arc) ne possédant pas de chemin exact à l'intérieur de ses réseaux_associés (resp. son réseau_associé) peut être approximé. L'approximation signifie que le noeud (resp. l'arc) permet d'atteindre le noeud final du chemin, mais que le chemin à parcourir à l'intérieur de ce noeud (resp. cet arc) n'est pas connu avec exactitude. La notion d'approximation se concrétise par l'extension de la partie "état" de l'OID des noeuds et des arcs. Huit états possibles existent donc pour un noeud (resp. arc) : validé et développé (noté "validé/développé"), validé et non développé ("validé/non développé"), non validé et développé ("non validé/développé"), non validé et non développé ("non validé/non développé"), validé, développé et approximé ("validé/développé/approximé"), validé, non développé et approximé ("validé/non développé/approximé"), non validé, développé et approximé ("non validé/développé/approximé"), non validé, non développé et approximé ("non validé/non développé/approximé"). Notons que la notion d'approximation des noeuds et des arcs est transparente pour les opérateurs DEVELOP, UNDEVELOP, SELECTION, UNION et DIFFERENCE. Un noeud (resp. arc) approximé reste un noeud (resp. arc) normal. L'opérateur de CHEMINS nécessite la définition d'arc fictif. Un arc fictif est un arc non réel, qui n'existe pas initialement dans la base de données. Cet arc fictif possède un OID qui possède comme partie générale une liste composée d'un entier incrémenté à chaque nouvelle création d'un arc fictif et de l'entier 1 si cet arc fictif possède un réseau_associé (de l'entier 0 dans le cas contraire). La partie réseau de l'OID d'un arc fictif est vide, ainsi que sa partie validation. Les parties extrémité_initiale et extrémité_finale de l'OID contiennent les OIDs des noeuds extrémités initiales et finales de l'arc. Les arcs fictifs permettent de faire la liaison entre plusieurs niveaux d'abstraction d'un même graphe. Si un noeud ni se trouve à un niveau quelconque du graphe (dans un réseau_associé à un master_noeud ou un master_arc), mais également au plus haut niveau du graphe, alors les arcs fictifs vont lier ce noeud ni aux arcs ou aux noeuds qui le contiennent dans leurs réseaux_associés. Ainsi, si ni ne pouvait être atteint par un chemin au plus haut niveau du graphe, mais pouvait être atteint en descendant la hiérarchie des réseaux_associés, grâce à l'introduction de ces arcs fictifs, aucun chemin permettant d'atteindre ni ne sera ignoré, et une recherche de chemin au plus haut niveau d'abstraction du graphe permettra effectivement de trouver un chemin atteignant ni. II-3.1.2 Spécification de l'opérateur de CHEMINSLes fonctions supplémentaires permettant de décrire l'opérateur de CHEMINS sont présentées en Annexes. Détaillons cet opérateur de CHEMINS pour un graphe G(N,E) et deux graphes G1(N1,E1) et G2(N2,E2) contenant les noeuds initiaux et finaux des chemins à chercher. Une contrainte agrégative, contrainte_agrégative est appliquée sur cet opérateur. La contrainte régulière est appliquée par l'intermédiaire d'un automate Gautomate(Na,Ea) et d'un état d'entrée Gétat_entrée(Ne,Ee). Soit ens_graphes l'ensemble des graphes résultats obtenus après application de l'opérateur de CHEMINS sur G avec les deux graphes G1 et G2 et les contraintes. 1) L'ensemble ens_graphes est initialisé à l'ensemble vide. Le graphe Gétat_sortie(Ns,Es) est initialisé au graphe Gétat_entrée(Ne,Ee).
2) Pour chaque noeud n1 et chaque noeud n2 de G1 et G2, l'application de l'opérateur de CHEMINS consiste à trouver dans le graphe G les noeuds et arcs "ancêtres" des noeuds n1 et n2 (noeuds et arcs possédant ces noeuds dans leur filiation). Ces noeuds et arcs sont mis dans des ensembles ens_noeuds1, ens_arcs1, ens_noeuds2, ens_arcs2. L'opérateur de recherche de chemins va être appliqué entre ces noeuds et/ou arcs ancêtres. Si n1 (resp. n2) appartient à N, alors la recherche de ces ancêtres ne possède aucune utilité et l'ensemble ens_noeuds1 (resp. ens_noeuds2) contient uniquement n1 (resp. n2), alors que l'ensemble ens_arcs1 (resp. ens_arcs2) est vide.
3) Une fonction de recherche de chemins sur un seul niveau d'abstraction est ensuite appliquée entre les noeuds "ancêtres" de n1 (noeuds ancêtres et extrémité finale des arcs ancêtres de n1) et les noeuds "ancêtres" de n2 (noeuds ancêtres et extrémité initiale des arcs ancêtres de n2). Quatre cas se présentent pour une recherche de chemins : existence d'un noeud ancêtre de n1 et d'un noeud ancêtre de n2, existence d'un noeud ancêtre de n1 et d'un arc ancêtre de n2, existence d'un arc ancêtre de n1 et d'un noeud ancêtre de n2, existence d'un arc ancêtre de n1 et d'un arc ancêtre de n2. L'ensemble des graphes résultant de la recherche des chemins au premier niveau d'abstraction du graphe est un ensemble ens_graphes_1er_niveau, initialisé à un ensemble vide.
3.1) La vérification de la contrainte régulière est effectuée sur le noeud noeud1, ancêtre du noeud n1. La fonction de recherche de chemins sur un seul niveau d'abstraction (PT1niveau) est ensuite appliquée entre noeud1 et noeud2, sur le graphe G. Cette fonction retourne l'ensemble des chemins de plus haut niveau d'abstraction du graphe entre noeud1 et noeud2. Le noeud noeud1 est ensuite rajouté aux graphes résultat.
3.2) Des arcs fictifs sont créés dans le graphe entre l'extrémité finale des arcs ancêtres de n2 (arcs arc2), et des noeuds représentant soit l'extrémité initiale des master_arcs contenant les noeuds fils (noeuds du réseau_associé) de l'arc ancêtre de n2, soit les master_noeuds contenant les noeuds fils de l'arc ancêtre de n2, soit les noeuds fils de l'arc ancêtre de n2. Des arcs fictifs sont également créés dans le graphe entre des noeuds représentant soit l'extrémité finale des master_arcs contenant les noeuds fils de l'arc ancêtre de n2, soit les master_noeuds contenant les noeuds fils de l'arc ancêtre de n2, soit les noeuds fils de l'arc ancêtre de n2 et l'extrémité initiale des arcs arc2 ancêtres de n2. Après ajout de ces arcs fictifs dans le graphe, la fonction PT1niveau est appliquée entre chaque noeud ancêtre de n1 et l'extrémité initiale de chaque arc ancêtre de n2.
3.3) Les opérations que du cas 3.2) sont réitérées, mais les arcs fictifs sont construits entre les extrémités initiales et finales de l'arc arc1, ancêtre de n1, et les noeuds et/ou arcs dont les réseaux_associés contiennent les noeuds appartenant à la filiation du réseau_associé à l'arc arc1.
3.4) Les opérations que du cas 3.2) sont réitérées, mais les arcs fictifs sont construits entre les extrémités initiales et finales de l'arc arc1, ancêtre de n1, et les noeuds et/ou arcs dont les réseaux_associés contiennent les noeuds appartenant à la filiation du réseau_associé à l'arc arc1, ainsi qu'entre les extrémités initiales et finales de l'arc arc2, ancêtre de n2, et les noeuds et/ou arcs dont les réseaux_associés contiennent les noeuds appartenant à la filiation du réseau_associé à l'arc arc2.
4) Les graphes résultant de l'application de PT1niveau sont comparés deux à deux afin d'éliminer les graphes redondants. Puis ces graphes sont étendus (application de l'opérateur DEVELOP), et l'opérateur PT est réappliqué entre n1 et n2. Ce développement des master_noeuds et master_arcs du graphe permet d'effectuer une recherche de chemins à tous les niveaux du graphe, en réduisant au fur et à mesure le nombre de noeuds et d'arcs de ce graphe. Le résultat de cette réapplication de l'opérateur fournit les chemins résultant du premier appel de cet opérateur. Ces chemins sont alors regroupés, afin de les présenter au plus haut niveau d'abstraction possible, et les arcs fictifs sont enlevés. La contrainte agrégative est enfin vérifiée sur chaque chemin.
4.1) Les arcs fictifs sont enlevés du graphe et les master_noeuds et master_arcs du graphe étudié sont développés. L'opérateur de recherche de chemin PT est ensuite réappliqué entre n1 et n2 sur ce graphe étendu et modifié. Le graphe correspond à un chemin final s'il ne contient plus aucun noeud ou arc à développer.
4.2) Les chemins finaux identifiés dans l'opérations précédente sont regroupés jusqu'à leur plus haut niveau d'abstraction (application de l'opérateur UNDEVELOP*). Les arcs fictifs sont éliminés de ces graphes et la contrainte agrégative est vérifiée sur chaque graphe résultant.
L'opérateur de CHEMINS fait appel à une fonction PT1niveau. Cette fonction permet d'effectuer une recherche de chemins entre deux noeuds dans un unique niveau d'abstraction. Elle est basée sur un algorithme d'évaluation de chemins sur un graphe plat (en l'occurrence et pour simplifier la présentation sur l'algorithme de Dijkstra présenté dans le chapitre I). Pour des raisons évidentes de lisibilité, nous avons décomposé cette fonction en différents modules. L'algorithme de chacun de ces modules se trouve en annexes (Annexes du chapitre III). La recherche est effectuée uniquement si le noeud initial et le noeud final de cette recherche sont différents. L'application de la fonction PT1niveau sur deux noeuds n1 et n2 et un graphe G(N,E) consiste à identifier chacun des arcs e de G ayant n1 pour extrémité initiale. L'arc choisi est marqué et des arcs fictifs sont construits entre les extrémités initiales et finales de cet arc et des noeuds du graphe. Si l'arc choisi est un arc simple, ces noeuds correspondent aux extrémités initiales et finales d'arcs possédant l'extrémité finale de l'arc choisi dans la filiation de leur réseau_associé. Si l'arc choisi est un master_arc, ces noeuds correspondent aux noeuds de la filiation du réseau_associé à ce master_arc, ou aux noeuds ancêtres des noeuds appartenant à la filiation du réseau_associé au master_arc choisi, ou aux extrémités initiales et finales des arcs ancêtres des noeuds appartenant à la filiation du réseau_associé au master_arc choisi. PT1niveau est ensuite réappliqué entre l'extrémité finale de l'arc choisi et n2. Cette réapplication de PT1niveau fournit pour résultat des graphes. L'arc e est ajouté à ces graphes, ainsi que son extrémité finale. Les noeuds ancêtres de n1 et les noeuds appartenant à sa filiation (s'il s'agit d'un master_noeud) sont également identifiés (le noeud n1 est marqué pour ne plus lui appliquer la fonction) et la fonction PT1niveau est appliquée entre ces noeuds et n2. n1 est ensuite ajouté aux graphes résultant de cette réapplication. Si aucun chemin n'a été trouvé depuis le noeud n1, le noeud ou l'arc "père" du noeud n1 (n1 appartient à son réseau_associé) est approximé et d'autres chemins sont recherchés depuis les noeuds extrémités initiales des arcs_sortants des réseaux_associés à ce noeud ou à cet arc père, jusqu'à n2. Le module Vérif_Contrainte_Régulière est appelé sur chaque noeud et arc examiné. Le résultat de la fonction PT1niveau est un ensemble de graphes. Cet ensemble (ens_graphes_résultat) est initialisé à un ensemble vide. Soit ens_graphes_résultat l'ensemble de graphes résultant de l'application de la fonction PT1niveau sur deux noeuds n1 et n2 et un graphe G(N,E). 1) L'ensemble de graphes ens_graphes_résultat est initialisé à un ensemble vide et le booléen existe_arc est initialisé à faux.
2) Le noeud n1 est examiné uniquement s'il n'est pas déjà marqué (c'est-à-dire si aucune recherche de chemins par ses noeuds fils ou pères n'a été entreprise) ou s'il correspond au noeud final de la recherche. Dans ce cas, la recherche s'arrête lorsque les noeuds n1 et n2 sont semblables et que le noeud n1 n'est l'extrémité d'aucun arc fictif, ou lorsque ces noeuds sont ancêtres l'un de l'autre (n1 ancêtre de n2 ou n2 ancêtre de n1). Dans le cas où les noeuds n1 et n2 ne sont pas semblables ou ancêtres l'un de l'autre, la recherche de chemins commence par l'identification des arcs dont l'extrémité initiale est n1. Chaque arc existant est examiné (cas 2.1). Que de tels arcs existent ou pas, la recherche se poursuit par l'examen des noeuds et arcs ancêtres (ou fils) de n1 (cas 2.2). Dans le cas où aucun arc ne possède n1 (ou un ancêtre de n1) pour extrémité initiale, le noeud ou arc contenant n1 dans son réseau_associé (noeud ou arc ayant été développé) est approximé et la recherche de chemins se poursuit avec les noeuds extrémités initiales des arcs_sortants des réseaux_associés à ce noeud ou à cet arc "père" de n1 (cas 2.3).
2.1) Des arcs existent dont l'extrémité initiale est n1. Deux cas se présentent : l'arc est un master_arc ou l'arc est un arc simple. Dans les deux cas, L'arc choisi est marqué (si les contraintes sont vérifiées) et des arcs fictifs sont construits entre les extrémités initiales et finales de cet arc et des noeuds du graphe. Si l'arc choisi est un arc simple, ces noeuds correspondent aux extrémités initiales et finales d'arcs possédant l'extrémité finale de l'arc choisi dans la filiation de leur réseau_associé. Si l'arc choisi est un master_arc, ces noeuds correspondent aux noeuds de la filiation du réseau_associé à ce master_arc, ou aux noeuds ancêtres des noeuds appartenant à la filiation du réseau_associé au master_arc choisi, ou aux extrémités initiales et finales des arcs ancêtres des noeuds appartenant à la filiation du réseau_associé au master_arc choisi. Une fois ces arcs fictifs construits, la recherche de chemin se poursuit avec l'extrémité finale de l'arc marqué. Dans les deux cas (arc simple ou master_arc), dès qu'un ensemble de chemins est trouvé, l'arc est démarqué.
2.2) La recherche de chemins se poursuit avec l'examen des noeuds ancêtres (resp. fils) de n1 et des arcs "ancêtres" de n1 (possédant n1 dans la filiation de leur réseau_associé). L'opérateur PT1niveau est réappliqué entre les noeuds ancêtres (resp. fils) et n2 (après vérification des contraintes sur ces noeuds). Dans le cas où des arcs ancêtres de n1 existent dans le graphe, des arcs fictifs sont construits entre le noeud n1 et l'extrémité initiale de ces arcs. L'opérateur PT1niveau est alors rappelé entre l'extrémité initiale de ces arcs et n2 (après vérification des contraintes sur cette extrémité initiale). Dans tous les cas, le noeud n1 est marqué, afin de ne pas lui réappliquer l'opérateur PT1niveau.
2.3) Aucun arc ne possède n1 (ou un ancêtre ou un fils de n1) pour extrémité initiale. Le noeud ou l'arc contenant n1 dans son réseau_associé (noeud ou arc ayant été développé) est approximé et la recherche de chemins se poursuit avec les noeuds extrémités initiales des arcs_sortants des réseaux_associés à ce noeud ou à cet arc "père" de n1.
Notons que s'il n'existe aucun chemin à l'intérieur du réseau_associé à un noeud (resp. arc), ce noeud (resp. arc) est approximé, et son réseau_associé contient, à la fin de l'opérateur de CHEMINS, uniquement l'arc_entrant permettant d'entrer dans son réseau_associé, et l'arc_sortant permettant d'en sortir. II-3.1.3 Illustration par un exempleSoit un graphe G(N,E) contenant un sous-ensemble des noeuds et des arcs de l'exemple illustré au chapitre II. Ce graphe contient deux master_noeuds (Paris et Lyon), deux noeuds Tours et Sortie5 de l'A10, et trois master_arcs (Paris-Lyon par *A6, Paris-Tours par *A10 et Sortie5 de A10-Tours par *Itinéraire de Délestage). Paris représente l'abstraction d'un réseau_associé (Réseau Intérieur Parisien). Lyon représente l'abstraction de ses deux réseaux_associés (Réseau Intérieur Lyonnais et Bordure de Lyon). La Figure III-51 représente le plus haut niveau d'abstraction du graphe G.
Figure III-51. Graphe G Les réseaux_associés des master_arcs Paris-Lyon par *A6, Paris-Tours par *A10 et Sortie5 de A10-Tours par Itinéraire de Délestage sont illustrés dans les Figures A.II-56, A.II-53, et A.II-51 des Annexes. Les réseaux_associés des master_noeuds Paris et Lyon sont illustrés dans les Figures A.II-35, A.II-45 et A.II-46 des Annexes. L'opérateur de Chemins va être appliqué sur ce graphe G et sur les deux graphes G1 et G2 contenant respectivement les noeuds Pl. Italie et Tours. Dans les figures suivantes, les noeuds et arcs approximés sont indiqués en gras. Les arcs fictifs sont indiqués en pointillés. Nous allons détailler chacune des opérations effectuées par l'opérateur de Chemins. La première opération consiste à trouver Pl. Italie et Tours dans le graphe G. Les ancêtres de ces deux noeuds sont trouvés : le master_noeud Paris pour le noeud Pl. Italie, le noeud Tours et les master_arcs Paris-Tours par *A10 et Sortie5 de A10-Tours par *Itinéraire de Délestage pour le noeud Tours. L'opérateur de Chemins est donc décomposé en trois appels différents à la fonction PT1niveau : recherche de chemins entre Paris et Tours, entre Paris et Paris, entre Paris et Sortie5 de A10. Après chacun de ces appels, les arcs ancêtres du noeud Tours (Paris-Tours par *A10 ou Sortie5 de A10-Tours par Itinéraire de Délestage) sont rajoutés aux graphes résultant de l'appel de la fonction PT1niveau.
Figure III-52. Premier ensemble de graphes après application de PT1niveau La fonction PT1niveau appliquée entre Paris et Tours retourne plusieurs graphes résultats. La première opération de la recherche de chemins entre Paris et Tours dans le plus haut niveau d'abstraction de G consiste à choisir un arc partant de Paris, Paris-Lyon par *A6 par exemple. Un arc fictif est alors construit entre l'extrémité finale de l'arc Paris-Lyon par *A6 (dont l'ensemble des noeuds descendants contient Sortie0 de A6) et l'extrémité initiale de l'arc Paris-Tours par *A10 (dont l'ensemble des noeuds descendants contient également ce noeud). Deux autres arcs fictifs sont construits : l'un entre l'extrémité finale de Paris-Tours par *A10 et l'extrémité initiale de Paris-Lyon par *A6, l'autre entre l'extrémité finale de Paris-Tours par *A10 et l'extrémité finale de Paris-Lyon par *A6. Le graphe G modifié devient donc le graphe illustré dans la Figure III-53.
Figure III-53. Graphe G modifié L'arc fictif partant de Lyon est choisi pour poursuivre la recherche de chemins. Le seul arc non marqué partant de Paris est alors le master_arc Paris-Tours par *A10. La recherche de chemins aboutit alors à graphe contenant les arcs Paris-Lyon par *A6, Lyon-Paris par un arc fictif et Paris-Tours par *A10. Le noeud Tours est concaténé à ce graphe. Un autre arc peut être choisi comme début de la recherche de chemins entre Paris et Tours : l'arc Paris-Tours par *A10. Aucun arc fictif n'est alors construit. La recherche s'arrête alors immédiatement et retourne un graphe composée de ce master_arc et des noeuds Paris et Tours.
L'ensemble des graphes sur lesquels un développement va être effectué contient donc un graphe composé, au plus haut niveau, des noeuds Paris, Lyon et Tours, des master_arcs Paris-Lyon par *A6, Lyon-Paris par un arc fictif, et Paris-Tours par *A10. Il contient également un graphe composé, au plus haut niveau, des noeuds Paris et Tours, et du master_arc Paris-Tours par *A10. La Figure III-54 illustre le plus haut niveau d'abstraction de ces deux graphes (Graphe2 et Graphe3) résultant de l'application de la fonction PT1niveau entre Paris et Tours, après ajout d'arcs et de noeuds.
Figure III-54. Deuxième ensemble de graphes après application de PT1niveau La fonction PT1niveau appliquée entre Paris et Sortie5 de A10 retourne plusieurs graphes résultats. La recherche de chemins entre Paris et Sortie5 de A10 débute par le marquage d'un arc, par exemple Paris-Lyon par *A6. Un arc fictif est alors construit entre l'extrémité finale de l'arc Paris-Lyon par *A6 (dont l'ensemble des noeuds descendants contient Sortie0 de A6) et l'extrémité initiale de l'arc Paris-Tours par *A10 (dont l'ensemble des noeuds descendants contient également ce noeud). Deux autres arcs fictifs sont construits : l'un entre l'extrémité finale de Paris-Tours par *A10 et l'extrémité initiale de Paris-Lyon par *A6, l'autre entre l'extrémité finale de Paris-Tours par *A10 et l'extrémité finale de Paris-Lyon par *A6. Le graphe G modifié devient donc le graphe illustré dans la Figure III-53 précédente.
Le graphe G modifié devient donc le graphe illustré dans la Figure III-55.
Figure III-55. Graphe G modifié Le chemin se poursuit par le marquage de l'arc fictif entre Tours et Sortie5 de A10. La recherche de chemins a abouti à un graphe contenant les arcs Paris-Lyon par *A6, Lyon-Paris par un arc fictif, Paris-Tours par *A10, et Tours-Sortie5 de A10 par un arc fictif. Le master_arc Sortie5 de A10-Tours par *Itinéraire de Délestage est concaténé à ce graphe. La suite de la recherche aboutit à un graphe contenant les arcs Paris-Lyon par *A6, Lyon-Paris par un arc fictif, Paris-Tours par *A10, Tours-Paris par un arc fictif, et Paris-Sortie5 de A10 par un arc fictif. Le master_arc Sortie5 de A10-Tours par *Itinéraire de Délestage est concaténé à ce graphe. La Figure III-56 illustre le plus haut niveau d'abstraction des deux graphes (Graphe4 et Graphe5) résultant de l'application de la fonction PT1niveau entre Paris et Sortie5 de A10, après ajout d'arcs et de noeuds, en ayant choisi comme premier arc marqué le master_arc Paris-Lyon par *A6.
Figure III-56. Troisième ensemble de graphes après application de PT1niveau La recherche de chemins entre Paris et Sortie5 de A10 aurait pu débuter par le choix de l'arc Paris-Tours par *A10 à la place de l'arc Paris-Lyon par *A6. Les arcs fictifs issus du marquage de Paris-Tours par *A10 sont alors construits et le graphe G est modifié en conséquence (Figure III-57).
Figure III-57. Graphe G modifié Le chemin se poursuit par le marquage de l'arc fictif entre Tours et Sortie5 de A10. La recherche de chemins a abouti à un graphe contenant les arcs Paris-Tours par *A10, et Tours-Sortie5 de A10 par un arc fictif. Le master_arc Sortie5 de A10-Tours par *Itinéraire de Délestage est concaténé à ce graphe. La suite de la recherche aboutit à un graphe contenant les arcs Paris-Tours par *A10, Tours-Paris par un arc fictif, et Paris-Sortie5 de A10 par un arc fictif. Le master_arc Sortie5 de A10-Tours par *Itinéraire de Délestage est concaténé à ce graphe. La Figure III-58 illustre le plus haut niveau d'abstraction des deux graphes (Graphe6 et Graphe7) résultant de l'application de la fonction PT1niveau entre Paris et Sortie5 de A10, après ajout d'arcs et de noeuds, en ayant choisi comme premier arc marqué le master_arc Paris-Tours par *A10.
Figure III-58. Résultat de l'appel de la fonction PT1niveau entre Paris et Sortie5 de A10 Les graphes Graphe1, Graphe2, Graphe3, Graphe4, Graphe5, Graphe6 et Graphe7 sont comparés deux à deux. Les graphes totalement inclus dans un autre graphe (nonobstant les arcs fictifs) sont ôtés de cet ensemble de graphes. Après cette comparaison, le seul graphe restant à développer est le graphe Graphe4. Le développement du graphe Graphe4 fournit le graphe illustré dans la Figure III-59. Nous ne représentons dans cette Figure que les noeuds et arcs pouvant mener à un chemin (les noeuds et arcs des réseaux_associés au master_noeud Lyon ne sont pas représentés, non plus que certains noeuds et arcs du réseau_associé au master_arc Paris-Lyon par *A6). Afin de simplifier la Figure, certains noeuds et arcs du réseau_associé au master_arc Sortie5 de A10-Tours par *Itinéraire Délestage ne sont pas représentés. La succession de ces noeuds et arcs représente un chemin exact entre Sortie5 de A10 et Mer dans ce réseau_associé. Nous représentons ce chemin exact par un arc en pointillé (les pointillés sont plus larges que dans le cas de l’arc fictif).
Figure III-59. Développement du graphe Graphe4 Les mêmes opérations que précédemment sont appliqués sur le graphe résultant du développement du graphe Graphe4. Des arcs fictifs sont donc construits et des chemins sont trouvés. Détaillons la succession des opérations effectuées dans le cadre d'un chemin résultat. Le master_arc Paris-Tours par **A10 possède dans son réseau_associé les noeuds Sortie0 de A6, Sortie5 de A10, Mer, La Vallée Maillard (appartenant au réseau_associé de Blois), Amboise et Orléans. Lorsque l’arc Pte Orléans-Sortie0 de A6 par A6 est numéroté, l’arc fictif entre Sortie0 de A6 et l’extrémité initiale de Paris-Tours par **A10 (Paris) est construit. Cet arc fictif est ensuite numéroté ainsi que le master_arc Paris-Tours par **A10. Des arcs fictifs sont construits entre Tours et Sortie5 de A10 (et inversement), entre Tours et Mer (et inversement), entre Tours et Blois (et inversement), entre Tours et Amboise (et inversement), et entre Tours et Orléans (et inversement). Plusieurs possibilités de numérotation d’arcs existent alors. L’arc fictif entre Tours et Sortie5 de A10 est numéroté, puis la succession des arcs permettant d’aller de Sortie5 de A10 à Blois. L’arc fictif entre Blois et Tours est à son tour numéroté, puis l'arc fictif entre Tours et Amboise, puis l’arc Amboise-Tours par D751, ce qui termine le plus haut niveau de ce chemin. Développant ce chemin et appliquant une nouvelle fois l’opérateur de chemins, le graphe rendu est un graphe donc tous les arcs sont exacts. Le master_arc exact Paris-Tours par **A10 ne contient plus dans son réseau_associé que le chemin (exact) permettant d’aller de Sortie0 de A6 à Sortie5 de A10. Le master_arc exact Sortie5 de A10-Tours par *Itinéraire Délestage ne contient plus dans son réseau_associé que les noeuds Amboise et Tours et l’arc Amboise-Tours par D751.
Figure III-60. Plus haut niveau d’abstraction d’un graphe résultat Considérons maintenant comme graphe initial de la recherche de chemins entre Pl. Italie et Tours le même graphe G que précédemment, à la différence près que le réseau_associé du master_arc Sortie5 de A10-Tours par *Itinéraire de Délestage ne contient plus l'arc Amboise-Tours par D751. Après application de la fonction PT1niveau, le Graphe Graphe'4 obtenu est identique au graphe Graphe4 illustré dans la Figure III-59 précédente, à la différence de cet arc près. Le graphe Graphe'4 est illustré dans la Figure III-61 suivante.
Figure III-61. Graphe Graphe'4 Les mêmes opérations que précédemment sont appliqués sur le graphe résultant du développement du graphe Graphe4. Des arcs fictifs sont donc construits et des chemins sont trouvés. Détaillons la succession des opérations effectuées dans le cadre d'un chemin résultat. Le master_arc Paris-Tours par **A10 possède dans son réseau_associé les noeuds Sortie0 de A6, Sortie5 de A10, Mer, La Vallée Maillard (appartenant au réseau_associé de Blois), Amboise et Orléans. Lorsque l’arc Pte Orléans-Sortie0 de A6 par A6 est numéroté, l’arc fictif entre Sortie0 de A6 et l’extrémité initiale de Paris-Tours par **A10 (Paris) est construit. Cet arc fictif est ensuite numéroté ainsi que le master_arc Paris-Tours par **A10. Des arcs fictifs sont construits entre Tours et Sortie5 de A10 (et inversement), entre Tours et Mer (et inversement), entre Tours et Blois (et inversement), entre Tours et Amboise (et inversement), et entre Tours et Orléans (et inversement). Plusieurs possibilités de numérotation d’arcs existent alors. L’arc fictif entre Tours et Sortie5 de A10 est numéroté, puis la succession des arcs permettant d’aller de Sortie5 de A10 à Mer, puis l’arc Mer-Blois par D951. L’arc fictif entre Blois et Tours est à son tour numéroté, puis l'arc fictif entre Tours et Amboise et entre Amboise et Tours, ce qui termine le plus haut niveau de ce chemin. Développant ce chemin et appliquant une nouvelle fois l’opérateur de chemins, nous nous apercevons qu’il n’existe aucun chemin permettant d’aller de Blois à Tours. Le master_arc Sortie5 de A10-Tours par *Itinéraire Délestage est donc approximé et seuls sont laissés dans son réseau_associé les noeuds et arcs permettant d’entrer et de sortir de ce réseau_associé (les noeuds Sortie5 de A10, Tours, Sortie6 de N20, Amboise et les arcs Sortie5 de A10-Sortie6 de N20 par N154 et Amboise-Tours par D751). Le master_arc exact Paris-Tours par **A10 ne contient plus dans son réseau_associé que le chemin (exact) permettant d’aller de Sortie0 de A6 à Sortie5 de A10. Le graphe résultant de cette recherche de chemin est illustré dans la Figure III-62.
Figure III-62. Plus haut niveau d’abstraction d’un graphe résultat Le résultat d'une recherche de chemins entre deux noeuds sur un graphe G correspond à un ensemble de graphes dont certains sont des graphes possédant des noeuds et/ou des arcs approximés, et d’autres des graphes dont tous les noeuds et arcs sont exacts. Yüklə 2,35 Mb. Dostları ilə paylaş:
|