Informatique
II-2.2 L'opérateur d'UNION
Yüklə 2,35 Mb.
|
- Bu səhifədəki naviqasiya:
- II-2.2.1 Notion de prépondérance
- II-2.2.2 Spécification de lopérateur dUNION
- II-2.2.3 Illustration par un exemple
- II-2.3 Lopérateur de DIFFERENCE
- II-2.3.1 Spécification de lopérateur de DIFFERENCE
- II-2.3.2 Illustration par un exemple
II-2.2 L'opérateur d'UNIONDe la même manière qu'un opérateur classique d'union ensembliste, l'opérateur d'UNION (noté ) est un opérateur binaire. Il permet d'obtenir un graphe à partir de deux graphes donnés. Le graphe résultat est un graphe hiérarchisé de même structure que les graphes hiérarchisés initiaux. La différence principale avec un opérateur classique d'union ensembliste réside dans la notion d'abstraction du modèle de graphe. L'opérateur d'UNION s'applique sur tous les noeuds et arcs du graphe, puis récursivement, sur tous les réseaux_associés des noeuds et arcs spécialisés.
Figure III-24. Signature de l'opérateur d'UNION II-2.2.1 Notion de prépondéranceLes graphes sur lesquels s'applique l'opérateur d'UNION peuvent contenir des noeuds et des arcs très différents : noeuds et arcs développés ou non développés, noeuds et arcs invalidés ou validés, master_noeuds et master_arcs devenus noeuds et arcs simples suite à l'application de l'opérateur de SELECTION. Pour gérer ces différences, l'opérateur d'UNION doit établir un ordre de prépondérance entre les différents états possibles d'un noeud (resp. arc).
Nous supposerons pour ce faire, que tous les graphes considérés sont issus d'un même graphe de base sur lequel a été appliqué une succession variable d'opérateurs. Les seuls états différenciables d'un noeud (resp. arc) sont donc noeud simple ou master_noeud (resp. arc simple ou master_arc), noeud validé ou noeud invalidé (resp. arc validé ou arc invalidé). L'opérateur d'UNION donne prépondérance au master_noeud (resp. master_arc) par rapport au noeud simple (resp. arc simple), et au noeud (resp. arc) validé par rapport au noeud (resp. arc) invalidé. L'union de deux ensembles contenant le même noeud (resp. arc) validé dans un cas et invalidé dans l'autre retourne le noeud (resp. arc) validé; l'union de deux ensembles contenant le même noeud (resp. arc), simple dans un cas et master_noeud (resp. master_arc) dans l'autre retourne le master_noeud (resp. master_arc) et ses réseaux_associés (resp. son réseau_associé). Notons que cette notion de prépondérance est utilisable car l'opérateur de SELECTION garde les noeuds et arcs invalidés "ancêtres" d'un noeud ou d'un arc validé afin de conserver une cohérence hiérarchique entre les noeuds et les arcs. Notons également que la comparaison entre deux noeuds (resp. arcs) est établie par le biais de l'OID global des noeuds (resp. arcs). Cet OID est unique pour chaque noeud, arc ou réseau et permet donc de comparer deux noeuds (resp. arcs). II-2.2.2 Spécification de l'opérateur d'UNIONLes fonctions supplémentaires permettant de décrire l'opérateur d'UNION sont présentées en Annexes. Détaillons cet opérateur d'UNION pour deux graphes G1(N1,E1) et G2(N2,E2). Soit G'(N',E') le graphe obtenu après application de l'opérateur de CHEMINS sur les graphes G1 et G2. 1) Les ensembles N' et E' sont initialisés à l'ensemble vide. Un ensemble de noeuds ens_noeuds_trouvés_dans_N'2 est initialisé à l'ensemble vide. Un ensemble d'arcs ens_arcs_trouvés_dans_E'2 est initialisé à l'ensemble vide. Un ensemble de noeuds ens_noeuds_plus_haut_niveau est initialisé à l'ensemble vide. Un ensemble d'arcs ens_arcs_plus_haut_niveau est initialisé à l'ensemble vide. L'opérateur UNDEVELOP* est appliqué sur tous les noeuds et arcs des graphes G1 et G2.
2) Les noeuds de N'1 (non fantômes) sont examinés. Chaque noeud n'1 de N'1 est comparé à chaque noeud n'2 de N'2. Deux cas se présentent : le noeud n'1 et le noeud n'2 représentent le même noeud (auquel cas la variable un_noeud est identifiée à Vrai), ou le noeud n'1 ne correspond à aucun noeud n'2. Le noeud n' de N', résultant de cette comparaison, est également comparé à chaque arc e'2 de E'2 et à chaque arc e'1 de E'1.
2.1) Le noeud n'1 et le noeud n'2 correspondent au même noeud. Seuls quatre cas peuvent se présenter : les deux noeuds sont des noeuds simples (cas 2.1.1), un des deux noeuds est un master_noeud alors que l'autre est un noeud simple (cas 2.1.2 et cas 2.1.3), les deux noeuds sont des master_noeuds (cas 2.1.4). L'ensemble ens_noeuds_trouvés_dans_N'2 va contenir les noeuds de N'2 semblables à des noeuds de N'1.
2.1.1) Les deux noeuds n'1 et n'2 sont des noeuds simples. Le noeud résultant n' à rajouter dans l'ensemble des noeuds N' est le noeud n'1 (qui est exactement égal au noeud n'2). Le noeud n' est invalidé ou validé suivant l'état des noeuds n'1 et n'2 (cas 2.1.1.1), et ajouté à N'.
2.1.1.1) Un des deux noeuds, n'1 ou n'2, est validé. Le noeud n' est alors obligatoirement validé (en accord avec les notions de prépondérance définies précédemment). Le noeud n' est invalidé uniquement dans le cas où les deux noeuds n'1 et n'2 sont invalidés.
2.1.2) Le noeud n'1 est un noeud simple, alors que le noeud n'2 est un master_noeud. En accord avec la notion de prépondérance définie précédemment, le noeud résultant n' à rajouter dans l'ensemble des noeuds N' est le master_noeud n'2. Le noeud n' est invalidé ou validé suivant l'état des noeuds n'1 et n'2 (cas 2.1.1.1), et ajouté à N'.
2.1.3) Le noeud n'1 est un master_noeud alors que le noeud n'2 est un noeud simple. Le noeud résultant n' à rajouter dans l'ensemble des noeuds N' est le master_noeud n'1. Le noeud n' est invalidé ou validé suivant l'état des noeuds n'1 et n'2 (cas 2.1.1.1), et ajouté à N'.
2.1.4) Les deux noeuds n'1 et n'2 sont des master_noeuds. Chacun des réseaux_associés au master_noeud n'1 doit être examiné et comparé à chaque réseau_associé au master_noeud n'2 (cas 2.1.4.1). Les réseaux_associés de n'2 doivent également être examinés (cas 2.1.4.2). Les réseaux_associés de n'1 (resp. n'2) ne correspondant à aucun réseau de n'2 (resp. n'1) sont modifiés pour tenir compte de l'union des réseaux existant à la fois dans n'1 et n'2 (cas 2.1.4.3). Le noeud n', résultat de la comparaison de n'1 et n'2, est invalidé ou validé suivant l'état des noeuds n'1 et n'2 (cas 2.1.1.1), et ajouté à N'.
2.1.4.1) Deux cas se présentent lors de l'examen d'un réseau_associé R'1 de n'1. Ce réseau correspond à un réseau_associé R'2 de n'2. Il nécessite alors de rappeler l'opérateur d'UNION entre le contenu du réseau R'1 et le contenu du réseau R'2. Le réseau R' qui contient le résultat de cet appel est ajouté à l'ensemble des réseaux du master_noeud n' résultant de la comparaison des noeuds n'1 et n'2. L'ensemble des noeuds de R' est extrait et mis dans un ensemble ens_noeuds. Le réseau_associé R'1 ne correspond à aucun réseau du master_noeud n'2. Il est alors ajouté à un ensemble de réseaux ens_réseaux_non_trouvés.
2.1.4.2) Le réseau_associé R'2 de n'2 ne correspond à aucun réseau du master_noeud n'1. Il est alors ajouté à l'ensemble de réseaux ens_réseaux_non_trouvés.
2.1.4.3) Les réseaux_associés R de n'1 (resp. n'2) ne correspondant à aucun réseau de n'2 (resp. n'1) sont modifiés pour tenir compte de l'union des réseaux existant à la fois dans n'1 et n'2. Les noeuds ayant été modifiés lors de cette union remplacent dans les réseaux R les noeuds leur correspondant.
2.2) Aucun noeud de N'2 ne correspond au noeud n'1. L'existence d'un noeud ancêtre de n'1 dans N'1 est testée. Suivant la non-existence ou l'existence d'un noeud ancêtre de n'1, le noeud n'1 est ajouté à l'ensemble de noeuds final N' ou est ajouté à un ensemble de noeuds de plus haut niveau. L'ensemble ens_noeuds_haut_niveau va contenir les noeuds de N'1 qui ne sont semblables à aucun noeud de N'2 et qui appartiennent à la filiation de noeuds de N'1.
2.3) Les arcs e'2 de E'2 sont examinés. L'arc e'2 est un arc ancêtre du noeud n'1, c'est-à-dire que le noeud se trouve dans un réseau appartenant à la filiation de son réseau_associé. L'opérateur d'UNION est donc appliqué entre le réseau_associé à l'arc e'2 et un graphe contenant simplement le noeud n'. Cet appel retourne un graphe qui remplace le précédent réseau_associé de l'arc e'2.
2.4) Les arcs e'1 de E'1 sont examinés. L'arc e'1 est un arc ancêtre du noeud n'1, c'est-à-dire que le noeud se trouve dans un réseau appartenant à la filiation de son réseau_associé. L'opérateur d'UNION est donc appliqué entre le réseau_associé à l'arc e'1 et un graphe contenant simplement le noeud n'. Cet appel retourne un graphe qui remplace le précédent réseau_associé de l'arc e'1.
3) Les noeuds n'2 de N'2 (non fantômes) sont examinés s'ils ne correspondent à aucun noeud de N'1. L'existence d'un noeud ancêtre de n'2 dans N'2 est testée. Suivant la non-existence ou l'existence d'un noeud ancêtre de n'2, le noeud n'2 est ajouté à l'ensemble de noeuds final N' ou est ajouté à un ensemble de noeuds de plus haut niveau. L'ensemble ens_noeuds_haut_niveau va également contenir les noeuds de N'2 qui ne sont semblables à aucun noeud de N'1 et qui appartiennent à la filiation de noeuds de N'2. Chaque noeud n'2 de N'2 est également comparé à chaque arc e'1 de E'1.
3.1) Les arcs e'1 de E'1 sont examinés. L'arc e'1 est un arc ancêtre du noeud n'2, c'est-à-dire que le noeud se trouve dans un réseau appartenant à la filiation de son réseau_associé. L'opérateur d'UNION est donc appliqué entre le réseau_associé à l'arc e'1 et un graphe contenant simplement le noeud n'2. Cet appel retourne un graphe qui remplace le précédent réseau_associé de l'arc e'1.
4) Les noeuds de l'ensemble ens_noeuds_haut_niveau doivent être rajouté à l'ensemble de noeuds N'. Ils appartiennent à la filiation de noeuds déjà existant dans N'. Tous les noeuds présents dans N', à quelque niveau d'abstraction que ce soit, sont donc extraits et mis dans un ensemble de noeuds ens_noeuds. Chaque noeud de l'ensemble ens_noeuds_haut_niveau est ajouté à l'ensemble N' s'il correspond à un noeud de l'ensemble ens_noeuds. Le noeud fantôme, s'il existe, est extrait de l'ensemble des noeuds de N'1. Les noeuds de N' qui doivent appartenir à la filiation de ce noeud fantôme sont mis dans le réseau_associé de ce noeud, s'ils ne s'y trouvent déjà. Les noeuds de la filiation du noeud fantôme qui n'apparaissent plus dans N' sont éliminés de la filiation de ce noeud fantôme.
5) Les arcs de E'1 sont examinés. Chaque arc e'1 (non fantôme) de E'1 est comparé à chaque arc e'2 de E'2. Deux cas se présentent : l'arc e'1 et l'arc e'2 représentent le même arc (auquel cas la variable un_arc est identifiée à Vrai), ou l'arc e'1 ne correspond à aucun arc e'2.
5.1) L'arc e'1 et l'arc e'2 correspondent au même arc. Seuls quatre cas peuvent se présenter : les deux arcs sont des arcs simples (cas 5.1.1), un des deux arcs est un master_arc alors que l'autre est un arc simple (cas 5.1.2 et cas 5.1.3), les deux arcs sont des master_arcs (cas 5.1.4). L'ensemble ens_arcs_trouvés_dans_N'2 va contenir les arcs de N'2 semblables à des arcs de N'1.
5.1.1) Les deux arcs e'1 et e'2 sont des arcs simples. L'arc résultant e' à rajouter dans l'ensemble des arcs E' est l'arc e'1 (qui est exactement égal à l'arc e'2). L'extrémité initiale (resp. finale) de l'arc e' correspond à l'extrémité, initiale ou finale, de l'arc e'1 (resp. de l'arc e'2) si cette extrémité appartient à la filiation de l'extrémité initiale ou finale de l'arc e'2 (resp. de l'arc e'1). L'arc e' est invalidé ou validé suivant l'état des arcs e'1 et e'2 (cas 5.1.1.1), et ajouté à E'.
5.1.1.1) Un des deux arcs, e'1 ou e'2, est validé. L'arc e' est alors obligatoirement validé (en accord avec les notions de prépondérance définies précédemment). L'arc e' est invalidé uniquement dans le cas où les deux arcs e'1 et e'2 sont invalidés.
5.1.2) L'arc e'1 est un arc simple, alors que l'arc e'2 est un master_arc. En accord avec la notion de prépondérance définie précédemment, l'arc résultant e' à rajouter dans l'ensemble des arcs E' est le master_arc e'2. L'extrémité initiale (resp. finale) de l'arc e' correspond à l'extrémité, initiale ou finale, de l'arc e'1 (resp. de l'arc e'2) si cette extrémité appartient à la filiation de l'extrémité initiale ou finale de l'arc e'2 (resp. de l'arc e'1). L'arc e' est invalidé ou validé suivant l'état des arcs e'1 et e'2 (cas 5.1.1.1), et ajouté à E'.
5.1.3) L'arc e'1 est un master_arc alors que l'arc e'2 est un arc simple. L'arc résultant e' à rajouter dans l'ensemble des arcs E' est le master_arc e'1. L'extrémité initiale (resp. finale) de l'arc e' correspond à l'extrémité, initiale ou finale, de l'arc e'1 (resp. de l'arc e'2) si cette extrémité appartient à la filiation de l'extrémité initiale ou finale de l'arc e'2 (resp. de l'arc e'1). L'arc e' est invalidé ou validé suivant l'état des arcs e'1 et e'2 (cas 5.1.1.1), et ajouté à E'.
5.1.4) Les deux arcs e'1 et e'2 sont des master_arcs. Le réseau_associé au master_arc e'1 est comparé au réseau_associé au master_arc e'2. Le réseau R'1 correspond obligatoirement au réseau_associé R'2 de e'2. L'opérateur d'UNION est rappelé entre le contenu du réseau R'1 et le contenu du réseau R'2. Le réseau R'1 est modifié pour contenir le résultat de cet appel, et le réseau R'1 devient le réseau du master_arc e' résultant de la comparaison des arcs e'1 et e'2. L'extrémité initiale (resp. finale) de l'arc e' correspond à l'extrémité, initiale ou finale, de l'arc e'1 (resp. de l'arc e'2) si cette extrémité appartient à la filiation de l'extrémité initiale ou finale de l'arc e'2 (resp. de l'arc e'1). L'arc e' est invalidé ou validé suivant l'état des arcs e'1 et e'2 (cas 5.1.1.1), et ajouté à E'.
5.2) Aucun arc de E'2 ne correspond à l'arc e'1. L'existence d'un arc ou d'un noeud ancêtre de e'1 dans G'1 est testée. Suivant la non-existence ou l'existence d'un arc ou d'un noeud ancêtre de e'1, l'arc e'1 est ajouté à l'ensemble d'arcs final E' ou est ajouté à un ensemble d'arcs de plus haut niveau. L'ensemble ens_arcs_haut_niveau va contenir les arcs de E'1 qui ne sont semblables à aucun arc de E'2 et qui appartiennent à la filiation d'arcs ou de noeuds de G'1.
6) Les arcs e'2 (non fantômes) de E'2 sont examinés s'ils ne correspondent à aucun arc de E'1. L'existence d'un arc ou d'un noeud ancêtre de e'2 dans G'2 est testée. Suivant la non-existence ou l'existence d'un arc ou d'un noeud ancêtre de e'2, l'arc e'2 est ajouté à l'ensemble d'arcs final E' ou est ajouté à un ensemble d'arcs de plus haut niveau. L'ensemble ens_arcs_haut_niveau va également contenir les arcs de E'2 qui ne sont semblables à aucun arc de E'1 et qui appartiennent à la filiation d'arcs ou de noeuds de G'2.
7) Les arcs de l'ensemble ens_arcs_haut_niveau doivent être rajoutés à l'ensemble d'arcs E'. Ils appartiennent à la filiation d'arcs ou de noeuds déjà existant dans E'. Tous les arcs présents dans G', à quelque niveau d'abstraction que ce soit, sont donc extraits et mis dans un ensemble d'arcs ens_arcs. Chaque arc de l'ensemble ens_arcs_haut_niveau est ajouté à l'ensemble E' s'il correspond à un arc de l'ensemble ens_arcs. L'arc fantôme, s'il existe, est extrait de l'ensemble des arcs de E'1. Les arcs de N' qui doivent appartenir à la filiation de cet arc fantôme sont mis dans le réseau_associé de cet arc, s'ils ne s'y trouvent déjà. Les arcs de la filiation de l'arc fantôme qui n'apparaissent plus dans E' sont éliminés de la filiation de cet arc fantôme.
II-2.2.3 Illustration par un exempleSoit un graphe G1(N1, E1) contenant un sous-ensemble des noeuds et des arcs de l'exemple illustré au chapitre II. Ce graphe contient trois master_noeuds (*France, Paris et Lyon) dont deux invalidés (Paris et *France), quatre noeuds (Pte Chapelle, Pte Orléans, Car. Europe et Perrache), deux master_arcs (Paris-Lyon par A6, Pte Chapelle-Pte Orléans par Périphérique Est) dont un invalidé (Pte Chapelle-Pte Orléans par Périphérique Est), et un arc (Car. Europe-Perrache par A6). Paris représente l'abstraction d'un réseau_associé (Bordure de Paris). Lyon représente l'abstraction d'un réseau_associé (Bordure de Lyon). Dans les Figures suivantes, les noeuds et arcs notés en gras représentent des noeuds et des arcs invalidés. La Figure III-25 représente le plus haut niveau d'abstraction du graphe G1.
Figure III-25. Graphe G1 - Plus haut niveau d'abstraction Le réseau_associé au master_noeud Lyon (Bordure de Lyon) contient uniquement les noeuds *Lyon, Car. Europe et Perrache, et l'arc Car. Europe-Perrache par A6. La Figure III-26 représente le réseau_associé à Lyon. L'arc entrant de réseau est l'arc Sortie21 de A6-Car. Europe par A6.
Figure III-26. Réseau_associé au master_noeud Lyon La Figure III-27 représente le réseau_associé au master_noeud Paris (Bordure de Paris). Ce réseau contient les master_noeuds 18ème, 14ème et *Paris, les noeuds Pte Chapelle et Pte Orléans et le master_arc invalidé Pte Chapelle-Pte Orléans par Périphérique Est. Le réseau_associé au master_noeud 14ème contient simplement le noeud Pte Chapelle. Le réseau_associé au master_noeud 18ème contient simplement le noeud Pte Chapelle. Le master_arc Pte Chapelle-Pte Orléans par Périphérique Est contient seulement les noeuds Pte Chapelle et Pte Orléans et le master_arc Pte Chapelle-Pte Orléans par *Périphérique Est. Ce master_arc contient les noeuds Pte Chapelle, Pte Orléans, Pte Italie et l'arc Pte Italie-Pte Orléans.
Figure III-27. Réseau_associé au master_noeud Paris La Figure III-28 représente le réseau_associé au master_arc Paris-Lyon par l'A6. Ce réseau contient deux master_noeuds Paris (invalidé) et Lyon, et un master_arc Paris-Lyon par *A6. Le réseau_associé à Paris-Lyon par *A6 contient les noeuds et arcs illustrés dans la Figure A.II-56 des Annexes, à l'exception du noeud Pl.Valmy et de l'arc Sortie21 de A6-Pl. Valmy par A6.
Figure III-28. Réseau_associé au master_arc Paris-Lyon par l'A6 Soit un graphe G2(N2, E2) contenant un sous-ensemble des noeuds et des arcs de l'exemple illustré au chapitre II. Ce graphe contient deux master_noeuds (*France et Paris) dont un invalidé (*France), deux noeuds (Pte Chapelle et Lyon), et un master_arc (Paris-Lyon par A6). Paris représente l'abstraction de deux réseaux_associés (Bordure de Paris et Réseau Intérieur Parisien). La Figure III-29 représente le plus haut niveau d'abstraction du graphe G2.
Figure III-29. Graphe G2 - Plus haut niveau d'abstraction La Figure III-30 représente le premier réseau_associé au master_noeud Paris (Bordure de Paris). Ce réseau contient les master_noeuds 18ème et *Paris, les noeuds Pte Chapelle et 14ème et l'arc simple Pte Chapelle-14ème par Périphérique Est. Le réseau_associé au master_noeud 18ème contient simplement le noeud Pte Chapelle. Le réseau_associé au master_noeud *Paris contient les noeuds **Paris et 14ème. Le deuxième réseau_associé à Paris (Réseau Intérieur Parisien) contient simplement le noeud simple 14ème et le master_noeud *Paris.
Figure III-30. Premier réseau_associé au master_noeud Paris (Bordure de Paris) La Figure III-31 représente le réseau_associé au master_arc Paris-Lyon par A6. Ce réseau contient deux noeuds, Paris et Lyon, et un master_arc Paris-Lyon par N7. Ce master_arc possède simplement trois noeuds dans son réseau_associé (Paris, Lyon et Fontainebleau).
Figure III-31. Réseau_associé au master_arc Paris-Lyon par A6 La Figure III-32 représente le plus haut niveau d'abstraction du graphe G' résultant de l'UNION entre les graphes G1 et G2. Le noeud Paris est resté un master_noeud mais est devenu validé. Il possède deux réseaux_associés (Bordure de Paris et Réseau Intérieur Parisien). Le noeud 14ème est un master_noeud. L'arc Périphérique Est a pour extrémité finale le noeud Pte Orléans et est un master_arc validé. Le noeud Lyon est un master_noeud semblable au master_noeud Lyon du graphe G1. Le noeud *France est resté un master_noeud invalidé. Le master_arc Paris-Lyon par A6 possède un réseau_associé contenant deux master_arcs (Paris-Lyon par *A6 et Paris-Lyon par N7).
Figure III-32. Graphe G' - Plus haut niveau d'abstraction La Figure III-33 représente le premier réseau_associé au master_noeud Paris (Bordure de Paris). Le noeud 14ème n'apparaît plus dans le réseau_associé au master_noeud *Paris.
Figure III-33. Premier réseau_associé au master_noeud Paris La Figure III-34 représente le deuxième réseau_associé au master_noeud Paris (Réseau Intérieur Parisien). Ce réseau contient deux master_noeuds (*Paris et 14ème). Le master_noeud 14ème n'apparaît plus dans le réseau_associé au master_noeud *Paris.
Figure III-34. Deuxième réseau_associé au master_noeud Paris La Figure III-35 représente le réseau_associé au master_arc Paris-Lyon par A6. Ce réseau contient deux master_arcs (Paris-Lyon par *A6 et Paris-Lyon par N7). Le réseau_associé au master_arc Paris-Lyon par *A6 est similaire au réseau_associé du même arc dans le graphe G1. Le réseau_associé au master_arc Paris-Lyon par N7 est similaire au réseau_associé du même arc dans le graphe G2.
Figure III-35. Réseau_associé au master_arc Paris-Lyon par A6 II-2.3 L'opérateur de DIFFERENCEDe la même manière qu'un opérateur classique de différence ensembliste, l'opérateur de DIFFERENCE (noté DIFFERENCE) est un opérateur binaire non symétrique. Il permet d'obtenir un graphe représentant la différence de deux graphes donnés. Le graphe résultat est un graphe hiérarchisé de même structure que les graphes hiérarchisés initiaux. La principale particularité de cet opérateur de différence réside dans la notion d'abstraction du modèle de graphe. L'opérateur de DIFFERENCE s'applique sur tous les noeuds et arcs du graphe, puis récursivement, sur tous les réseaux_associés des noeuds et arcs spécialisés. Le but de l'opérateur de DIFFERENCE est de trouver un ensemble de noeuds et arcs tel que chaque élément de cet ensemble appartienne au premier graphe sur lequel est appliqué cet opérateur, et n'appartienne pas au second graphe. Le résultat retourné est l'ensemble des noeuds et des arcs appartenant au premier graphe et n'appartenant pas au deuxième. Notons que la spécification de cet opérateur fait appel à la notion d'invalidation utilisée par l'opérateur de SELECTION. La signature de l'opérateur de DIFFERENCE est présentée Figure III-36.
Figure III-36. Signature de l'opérateur de DIFFERENCE II-2.3.1 Spécification de l'opérateur de DIFFERENCEL'opérateur de DIFFERENCE permet de trouver les noeuds et les arcs appartenant à un graphe et n'appartenant pas à un second graphe. Tous les noeuds et les arcs de ces graphes doivent être considérés, qu'ils se trouvent au plus haut niveau d'abstraction du graphe, ou qu'ils appartiennent à la filiation d'un réseau_associé à un noeud ou à un arc. L'opérateur de DIFFERENCE effectue les mêmes opérations que l'opérateur de SELECTION, en considérant que la vérification de critère sur les noeuds retourne Faux lorsque le noeud considéré appartient à un ensemble de noeuds donné (ensemble des noeuds du second graphe sur lequel s'applique l'opérateur), et que la vérification de critère sur les arcs retourne Faux lorsque l'arc considéré appartient à un ensemble d'arcs donné (ensemble des arcs du second graphe sur lequel s'applique l'opérateur). Nous noterons que la différence entre un graphe (resp. d'arcs) comportant un unique noeud validé (resp. arc validé) avec un autre graphe comportant le même noeud (resp. arc) invalidé retourne le premier graphe. Les fonctions supplémentaires permettant de décrire l'opérateur de DIFFERENCE sont présentées en Annexes. Soit un graphe G1(N1,E1) et un graphe G2(N2,E2) sur lesquels s'applique l'opérateur de DIFFERENCE. Soit G'(N',E') le graphe résultant de cette différence. 1) Les ensembles N' et E' sont initialisés aux ensembles vides. Tous les arcs validés de G2 (quel que soit leur niveau d'abstraction) sont mis dans un ensemble d'arcs ens_arcs_G2. Tous les noeuds validés de G2 (quel que soit leur niveau d'abstraction) sont mis dans un ensemble d'arcs ens_noeuds_G2.
2) Soit un arc e1 de E1. Le résultat de l'application de l'opérateur de DIFFERENCE sur l'ensemble E1 des arcs résulte des opérations suivantes :
2.1) Un arc simple n'appartenant pas à l'ensemble d'arcs ens_arcs_G2 (c'est-à-dire dont l'OID global ne correspond à aucun OID global d'un arc de cet ensemble) est ajouté à E'.
2.2) Un master_arc e1 n'appartenant pas à l'ensemble ens_arcs_G2 nécessite l'examen de son réseau_associé par l'opérateur de DIFFERENCE. Suivant le résultat de cet examen (graphe vide ou non), l'arc devient ou non un arc simple. Un master_arc est ajouté à E'; un arc simple est ajouté à l'ensemble d'arcs ens_arcs_simples.
2.3) Un master_arc e1 appartenant à l'ensemble ens_arcs_G2 nécessite l'examen de son réseau_associé par l'opérateur de DIFFERENCE. Suivant le résultat de cet examen (graphe vide ou non), l'arc n'est pas ajouté à E' ou devient un master_arc invalidé. 3) Soit un noeud n1 de N1. Le résultat de l'application de l'opérateur de DIFFERENCE sur l'ensemble N1 des noeuds résulte des opérations suivantes :
3.1) Un noeud simple n'appartenant pas à l'ensemble de noeuds ens_noeuds_G2 est ajouté à N'.
3.2) Un noeud simple n1 appartenant à l'ensemble ens_noeuds_G2 est invalidé et ajouté à N' uniquement dans le cas où il est lié à des arcs.
3.2.1) Le noeud n1 est remplacé par le noeud n'1 comme extrémité initiale ou finale de l'arc e, si n1 était extrémité initiale ou finale de cet arc. Le noeud n1 est ajouté à l'ensemble de noeuds N' dans le cas où il est lié à un arc.
3.3) Un master_noeud n1 nécessite l'examen de ses réseaux_associés. L'opérateur de DIFFERENCE est appliqué sur chacun de ses réseaux. Le résultat de cette application retourne, pour chaque réseau, un graphe vide ou non vide. Un réseau dont tous les noeuds appartiennent à ens_noeuds_G2 est ôté de l'ensemble des réseaux de n1. Un réseau dont au moins un noeud n'appartient pas à ens_noeuds_G2 est transformé pour ne laisser dans ce réseau que les noeuds et arcs résultant de l'application de l'opérateur de DIFFERENCE. Le master_noeud appartient ou non à ens_noeuds_G2.
3.3.1) Le master_noeud n1 n'appartient pas à l'ensemble ens_noeuds_G2. Il est transformé en un noeud simple, et ajouté à un ensemble de noeuds ens_noeuds_simples, si le résultat de l'examen de ses réseaux_associés rend un graphe vide pour chacun de ces réseaux. Qu'il soit ou non transformé en noeud simple, les arcs de E' et de ens_arcs_simples auxquels il est attaché en tant qu'extrémité sont examinés. Le noeud est ajouté à N' s'il est lié à des arcs de E' ou de ens_arcs_simples.
3.3.2) Le master_noeud n1 appartient à l'ensemble ens_noeuds_G2. Un master_noeud n1 lié à des arcs de E' et ne possédant plus aucun réseau est invalidé. Un master_noeud n1 possédant encore des réseaux_associés est invalidé et chacun des arcs de E' et de ens_arcs_simples auxquels il est lié est examiné.
3.3.2.1) Le noeud n1 est remplacé par le noeud n'1 comme extrémité initiale ou finale de l'arc e, si n1 était extrémité initiale ou finale de cet arc.
4) Lors de l'examen des arcs e1 de E1, certains master_arcs sont devenus des arcs simples. Pour conserver une cohérence hiérarchique entre les arcs, un master_arc e1 devenu arc simple est ajouté au réseau_associé de son arc fantôme "frère", et placé au plus bas niveau de la filiation de cet arc frère. L'oid de e1 est modifié en conséquence et e1 est ajouté à E'. De la même manière, les master_noeuds devenus noeuds simples sont ajoutés au réseau_associé de leur noeud fantôme frère, et leur OID est modifié.
II-2.3.2 Illustration par un exempleSoit un graphe G1(N1, E1) contenant un sous-ensemble des noeuds et des arcs de l'exemple illustré au chapitre II. Ce graphe contient trois master_noeuds (*France, Paris et Lyon) dont un invalidé (*France), quatre noeuds (Pte Chapelle, Pte Orléans, Car. Europe et Perrache), deux master_arcs (Paris-Lyon par A6, Pte Chapelle-Pte Orléans par Périphérique Est), et un arc (Car. Europe-Perrache par A6). Paris représente l'abstraction d'un réseau_associé (Bordure de Paris). Lyon représente l'abstraction d'un réseau_associé (Bordure de Lyon). Dans les Figures suivantes, les noeuds et arcs notés en gras représentent des noeuds et des arcs invalidés. La Figure III-37 représente le plus haut niveau d'abstraction du graphe G1.
Figure III-37. Graphe G1 - Plus haut niveau d'abstraction Le réseau_associé au master_noeud Lyon (Bordure de Lyon) contient uniquement les noeuds *Lyon, Car. Europe et Perrache, et l'arc Car. Europe-Perrache par A6. La Figure III-38 représente le réseau_associé à Lyon. L'arc entrant de réseau est l'arc Sortie21 de A6-Car. Europe par A6.
Figure III-38. Réseau_associé au master_noeud Lyon La Figure III-39 représente le réseau_associé au master_noeud Paris (Bordure de Paris). Ce réseau contient les master_noeuds 18ème, 14ème et *Paris, les noeuds Pte Chapelle et Pte Orléans et le master_arc invalidé Pte Chapelle-Pte Orléans par Périphérique Est. Le réseau_associé au master_noeud 14ème contient simplement le noeud Pte Chapelle. Le réseau_associé au master_noeud 18ème contient simplement le noeud Pte Chapelle. Le master_arc Pte Chapelle-Pte Orléans par Périphérique Est contient seulement les noeuds Pte Chapelle et Pte Orléans et le master_arc Pte Chapelle-Pte Orléans par *Périphérique Est. Ce master_arc contient les noeuds Pte Chapelle, Pte Orléans, Pte Italie et l'arc Pte Italie-Pte Orléans.
Figure III-39. Réseau_associé au master_noeud Paris La Figure III-40 représente le réseau_associé au master_arc Paris-Lyon par l'A6. Ce réseau contient deux master_noeuds Paris (invalidé) et Lyon, et un master_arc Paris-Lyon par *A6. Le réseau_associé à Paris-Lyon par *A6 contient les noeuds et arcs illustrés dans la Figure A.II-56 des Annexes, à l'exception du noeud Pl.Valmy et de l'arc Sortie21 de A6-Pl. Valmy par A6.
Figure III-40. Réseau_associé au master_arc Paris-Lyon par l'A6 Soit un graphe G2(N2, E2) contenant un sous-ensemble des noeuds et des arcs de l'exemple illustré au chapitre II. Ce graphe contient deux master_noeuds (*France et Paris) dont un invalidé (*France), deux noeuds (Pte Chapelle et Lyon), et un master_arc (Paris-Lyon par A6). Paris représente l'abstraction de deux réseaux_associés (Bordure de Paris et Réseau Intérieur Parisien). La Figure III-41 représente le plus haut niveau d'abstraction du graphe G2.
Figure III-41. Graphe G2 - Plus haut niveau d'abstraction La Figure III-42 représente le premier réseau_associé au master_noeud Paris (Bordure de Paris). Ce réseau contient les master_noeuds 18ème et *Paris, les noeuds Pte Chapelle et 14ème et l'arc simple Pte Chapelle-14ème par Périphérique Est. Le réseau_associé au master_noeud 18ème contient simplement le noeud Pte Chapelle. Le réseau_associé au master_noeud *Paris contient les noeuds **Paris et 14ème. Le deuxième réseau_associé à Paris (Réseau Intérieur Parisien) contient simplement le noeud simple 14ème et le master_noeud *Paris.
Figure III-42. Premier réseau_associé au master_noeud Paris (Bordure de Paris) La Figure III-43 représente le réseau_associé au master_arc Paris-Lyon par A6. Ce réseau contient deux noeuds, Paris et Lyon, et un master_arc Paris-Lyon par N7. Ce master_arc possède simplement trois noeuds dans son réseau_associé (Paris, Lyon et Nemours).
Figure III-43. Réseau_associé au master_arc Paris-Lyon par A6 La Figure III-44 représente le plus haut niveau d'abstraction du graphe G' résultant de la DIFFERENCE entre les graphes G1 et G2. Le noeud Paris est resté un master_noeud invalidé. Il possède un réseau_associé (Bordure de Paris). Tous les noeuds de ce réseau sont invalidés à l'exception des noeuds Pte Italie, 13ème et Pte Orléans. L'arc Périphérique Est est un master_arc invalidé contenant un master_arc validé (*Périphérique Est). Le noeud Lyon est un master_noeud semblable au master_noeud Lyon du graphe G1, mais invalidé Le noeud *France est resté un master_noeud invalidé. Le master_arc Paris-Lyon par A6 possède un réseau_associé contenant le master_arc validé Paris-Lyon par *A6.
Figure III-44. Graphe G' - Plus haut niveau d'abstraction La Figure III-45 représente le réseau_associé au master_noeud Paris (Bordure de Paris). Seuls les noeuds et arcs validés de G1 n'apparaissant pas dans G2 sont restés validés.
Figure III-45. Réseau_associé au master_noeud Paris La Figure III-46 représente le réseau_associé au master_arc Paris-Lyon par A6. Ce réseau contient un seul master_arc (Paris-Lyon par *A6). Le réseau_associé au master_arc Paris-Lyon par *A6 est similaire au réseau_associé du même arc dans le graphe G1, à la différence près que le noeud Nemours de ce réseau est devenu un noeud invalidé.
Figure III-46. Réseau_associé au master_arc Paris-Lyon par A6 La Figure III-47 représente le réseau_associé au master_noeud invalidé Lyon. Ce réseau_associé (Bordure de Lyon) contient les noeuds *Lyon, Car. Europe et Perrache, et l'arc Car. Europe-Perrache par A6. L'arc entrant de réseau est l'arc Sortie21 de A6-Car. Europe par A6.
Figure III-47. Réseau_associé au master_noeud Lyon Yüklə 2,35 Mb. Dostları ilə paylaş:
|