Informatique
II-3.2 L'opérateur d'INCLUSION
Yüklə 2,35 Mb.
|
- Bu səhifədəki naviqasiya:
- II-3.2.1 Propriétés des opérateurs dINCLUSION
- II-3.2.2 Lopérateur dINCLUSION de noeuds
- II-3.2.3 Lopérateur dINCLUSION darcs
- II-3.2.4 Lopérateur dINCLUSION de noeuds et darcs
- II-3.2.5 Illustration par un exemple
- II-3.3 Lopérateur dINTERSECTION
- II-3.3.1 Propriétés des opérateurs dINTERSECTION
- II-3.3.2 Lopérateur dINTERSECTION de noeuds
- II-3.3.3 Lopérateur dINTERSECTION darcs
- II-3.3.4 Lopérateur dINTERSECTION de noeuds et darcs
- II-3.3.5 Illustration par un exemple
II-3.2 L'opérateur d'INCLUSIONL'opérateur d'inclusion correspond aux opérateurs d'inclusion ensembliste. Il se décompose en trois opérateurs différents : l'opérateur d'inclusion d'un ensemble de noeuds dans un graphe (Pic_n), l'opérateur d'inclusion d'un ensemble d'arcs dans un graphe (Pic_e), et l'opérateur d'inclusion d'un graphe (représentant un ensemble de noeuds et d'arcs) dans un graphe (Pic_ne). Ces opérateurs possèdent certaines propriétés communes, mais des spécifications différentes. Nous détaillerons tout d'abord ces propriétés qui définissent l'opérateur d'inclusion, au sens général du terme, puis examinerons chacune des spécifications des opérateurs dérivés de l'opérateur d'inclusion. Un exemple général sera présenté.
II-3.2.1 Propriétés des opérateurs d'INCLUSIONLa différence principale de ces opérateurs avec un opérateur classique d'inclusion d'un ensemble de noeuds (resp. arcs, resp. noeuds et arcs) dans un autre ensemble réside dans la notion d'abstraction du modèle de graphe. L'opérateur d'inclusion vérifie l'appartenance d'un noeud (resp. arc, resp noeud ou arc) à un graphe à quelque niveau que ce noeud (resp. arc, resp. noeud ou arc) se trouve. Le but de ces opérateurs est la vérification de l'appartenance de chaque élément d'un ensemble de noeuds (resp. arcs, resp. noeuds et arcs) à un autre ensemble. Le résultat retourné est soit le premier ensemble de noeuds (resp. arcs, resp. noeuds ou arcs), soit un graphe vide (si un élément du premier ensemble n'est pas dans le second), soit tous les noeuds (resp. arcs, resp. noeuds et arcs) du second ensemble dans le cas où l'ensemble dont l'inclusion doit être vérifiée est un ensemble vide. Ce dernier cas correspond à l'extraction de tous les noeuds (resp. arcs, resp. noeuds et arcs) d'un graphe. Chacun de ces opérateurs est un opérateur binaire. Notons que la spécification de ces opérateurs fait appel à la notion d'invalidation utilisée par l'opérateur de SELECTION. La signature de ces opérateurs d'INCLUSION est présentée Figure III-63.
Figure III-63. Signature des opérateur d'inclusion II-3.2.2 L'opérateur d'INCLUSION de noeudsL'opérateur d'inclusion de noeuds (Pic_n) permet de vérifier l'inclusion d'un ensemble de noeuds dans un autre ensemble de noeuds. Chacun de ces ensembles est représenté par un graphe pouvant contenir aussi bien des noeuds que des arcs. Tous les noeuds 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. Les fonctions supplémentaires permettant de décrire l'opérateur d'inclusion de noeuds sont présentées en Annexes. Soit un graphe G1(N1,E1) et un graphe G(N,E) sur lesquels s'applique l'opérateur d'inclusion de noeuds. Soit G'(N',E') le graphe résultant de la vérification de l'inclusion de l'ensemble total des noeuds de G1 dans l'ensemble total des noeuds de G. 1) Les ensembles N' et E' sont initialisés aux ensembles vides.
2) Le graphe G1 est testé. L'opérateur d'inclusion retourne deux résultats différents suivant si G1 est un graphe vide ou non. Appliqué sur un graphe G1 vide, Pic_n retourne l'ensemble des noeuds de G. Appliqué sur un graphe G1 non vide, Pic_n retourne le graphe G1 ou un graphe vide.
2.1) G1 est un graphe vide. L'opérateur d'inclusion de G1 dans G correspond à rechercher tous les noeuds de G. Cette recherche s'effectue par le biais de l'opérateur de SELECTION appliqué sur G et sur un critère correspondant à une recherche de noeud sans autre spécificité.
2.2) G1 n'est pas un graphe vide. Tous les noeuds de G1, quel que soit leur niveau d'abstraction dans ce graphe, sont mis dans un ensemble de noeuds ens_noeuds_G1. Tous les noeuds de G, quel que soit leur niveau d'abstraction dans ce graphe, sont mis dans un ensemble de noeuds ens_noeuds_G. La fonction Extraire_Tous_Noeuds_Graphe utilisée est illustrée en Annexes. Cette fonction permet d'extraire tous les noeuds d'un graphe en les mettant dans un ensemble de noeuds, sans se soucier de cohérence hiérarchique entre les noeuds. Chaque noeud de ens_noeuds_G1 est ensuite examiné. Un noeud appartenant à ens_noeuds_G permet de poursuivre l'examen des autres noeuds de ens_noeuds_G1. Un noeud n'appartenant pas à ens_noeuds_G autorise à rendre pour résultat de l'opérateur d'inclusion un graphe vide. Lorsque tous les noeuds de G1 ont été examinés et se trouvent dans G, l'opérateur retourne pour résultat le graphe G1.
II-3.2.3 L'opérateur d'INCLUSION d'arcsL'opérateur d'inclusion d'arcs (Pic_e) permet de vérifier l'inclusion d'un ensemble d'arcs dans un autre ensemble d'arcs. Chacun de ces ensembles est représenté par un graphe pouvant contenir aussi bien des noeuds que des arcs. Tous 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 master_noeud ou à un master_arc. Les fonctions supplémentaires permettant de décrire l'opérateur d'inclusion de noeuds sont présentées en Annexes. Soit un graphe G1(N1,E1) et un graphe G(N,E) sur lesquels s'applique l'opérateur d'inclusion d'arcs. Soit G'(N',E') le graphe résultant de la vérification de l'inclusion de l'ensemble total des arcs de G1 dans l'ensemble total des arcs de G. 1) Les ensembles N' et E' sont initialisés aux ensembles vides.
2) Le graphe G1 est testé. L'opérateur d'inclusion retourne deux résultats différents suivant si G1 est un graphe vide ou non. Appliqué sur un graphe G1 vide, Pic_e retourne l'ensemble des arcs de G. Appliqué sur un graphe G1 non vide, Pic_e retourne le graphe G1 ou un graphe vide.
2.1) G1 est un graphe vide. L'opérateur d'inclusion de G1 dans G correspond à rechercher tous les arcs de G. Cette recherche s'effectue par le biais de l'opérateur de SELECTION appliqué sur G et sur un critère correspondant à une recherche d'arc sans autre spécificité.
2.2) G1 n'est pas un graphe vide. Tous les arcs de G1, quel que soit leur niveau d'abstraction dans ce graphe, sont mis dans un ensemble d'arcs ens_arcs_G1. Tous les arcs de G, quel que soit leur niveau d'abstraction dans ce graphe, sont mis dans un ensemble d'arcs ens_arcs_G. La fonction Extraire_Tous_Arcs_Graphe utilisée est illustrée en Annexes. Cette fonction permet d'extraire tous les arcs d'un graphe en les mettant dans un ensemble d'arcs, sans se soucier de cohérence hiérarchique entre les arcs. Chaque arc de ens_arcs_G1 est ensuite examiné. Un arc appartenant à ens_arcs_G permet de poursuivre l'examen des autres arcs de ens_arcs_G1. Un arc n'appartenant pas à ens_arcs_G autorise à rendre pour résultat de l'opérateur d'inclusion un graphe vide. Lorsque tous les arcs de G1 ont été examinés et se trouvent dans G, l'opérateur retourne pour résultat le graphe G1.
II-3.2.4 L'opérateur d'INCLUSION de noeuds et d'arcsL'opérateur d'inclusion de noeuds et d'arcs (Pic_ne) permet de vérifier l'inclusion d'un ensemble de noeuds et d'un ensemble d'arcs dans un autre ensemble de noeuds et d'arcs. Chacun de ces ensembles est représenté par un graphe pouvant contenir aussi bien des noeuds que des arcs. Tous les éléments 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 a un arc. Les fonctions supplémentaires permettant de décrire l'opérateur d'inclusion de noeuds sont présentées en Annexes. Soit un graphe G1(N1,E1) et un graphe G(N,E) sur lesquels s'applique l'opérateur d'inclusion de noeuds et d'arcs. Soit G'(N',E') le graphe résultant de la vérification de l'inclusion de l'ensemble total des noeuds et des arcs de G1 dans l'ensemble total des noeuds et des arcs de G. 1) Les ensembles N' et E' sont initialisés aux ensembles vides.
2) Le graphe G1 est testé. L'opérateur d'inclusion retourne deux résultats différents suivant si G1 est un graphe vide ou non. Appliqué sur un graphe G1 vide, Pic_ne retourne le graphe G. Appliqué sur un graphe G1 non vide, Pic_ne retourne le graphe G1 ou un graphe vide.
2.1) G1 n'est pas un graphe vide. Tous les noeuds (resp. arcs) de G1, quel que soit leur niveau d'abstraction dans ce graphe, sont mis dans un ensemble de noeuds ens_noeuds_G1 (resp. d'arcs ens_arcs_G1). Tous les noeuds (resp. arcs) de G, quel que soit leur niveau d'abstraction dans ce graphe, sont mis dans un ensemble de noeuds ens_noeuds_G (resp. d'arcs ens_arcs_G). La fonction Extraire_Tous_Noeuds_Graphe (resp. Extraire_Tous_Arcs_Graphe) est utilisée, puis chaque noeud de ens_noeuds_G1 est examiné. Un noeud appartenant à ens_noeuds_G permet de poursuivre l'examen des autres noeuds de ens_noeuds_G1 et des arcs de ens_arcs_G1. Un noeud n'appartenant pas à ens_noeuds_G autorise à rendre pour résultat de l'opérateur d'inclusion un graphe vide. Lorsque tous les noeuds de G1 ont été examinés et se trouvent dans G, les mêmes examens sont effectués sur les arcs de G1. Lorsque tous les arcs de G1 ont été examinés et se trouvent dans G, l'opérateur retourne pour résultat le graphe G1.
II-3.2.5 Illustration par un exempleSoit un graphe G(N,E) contenant un sous-ensemble des noeuds et des arcs du réseau mondial illustré au chapitre II. Ce graphe contient deux master_noeuds (Paris 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). Le seul arc_sortant de ces réseaux est Pte d'Orléans-Sortie0 de l'A6 par l'A6. Aucun arc_entrant n'est défini. Lyon représente l'abstraction d'un unique réseau_associé (Bordure de Lyon). Le seul arc_entrant de ce réseau est Sortie21 de l'A6-Car. Europe par l'A6. Aucun arc_sortant n'est défini. La Figure III-64 représente le plus haut niveau d'abstraction (niveau 3) du graphe G.
Figure III-64. Graphe G - niveau 3 Les réseaux_associés à Paris sont illustrés dans les Figures A.II-35 et A.II-36. Le réseau_associé au master_noeud Lyon est illustré Figure A.II-46. Le réseau_associé au master_arc Paris-Lyon par l'A6 est illustré Figure A.II-55. Soit un graphe G1(N1, E1) contenant le noeud simple Paris, le master_noeud invalidé Lyon représentant l'abstraction du réseau_associé illustré Figure A-II.46 et contenant uniquement les noeuds Opéra et Perrache, ainsi que l'arc liant ces deux noeuds. Le graphe G1 contient également l'arc simple Paris-Lyon par l'A6 et le master_arc invalidé Paris-Lyon par la N7. Le réseau_associé à Paris-Lyon par la N7 contient uniquement les noeuds Fontainebleau et Perrache. La Figure III-65 illustre le graphe G1.
Figure III-65. Graphe G1 Appliqué sur le graphe G1 et le graphe G, l'opérateur d'inclusion de noeuds retourne le graphe G1 : tous les noeuds de ce graphe appartiennent à l'ensemble des noeuds du graphe G, que ces noeuds soient des noeuds simples dans le graphe G1 (Paris) et des master_noeuds dans le graphe G. De la même manière, appliqué sur le graphe G1 et le graphe G, l'opérateur d'inclusion d'arcs retourne le graphe G1 : tous les arcs de ce graphe appartiennent à l'ensemble des arcs du graphe G, que ces arcs soient des arcs simples dans le graphe G1 (Paris-Lyon par *A6) et des master_arcs dans le graphe G. Appliqué sur le graphe G1 et le graphe G, l'opérateur d'inclusion de noeuds et d'arcs retourne également le graphe G1.
Figure III-66. Graphe G1 Appliqué sur le graphe G1 et le graphe G, l'opérateur d'inclusion de noeuds retourne un graphe vide : le noeud Pl. Valmy n'appartient pas à l'ensemble des noeuds du graphe G. De la même manière, appliqué sur le graphe G1 et le graphe G, l'opérateur d'inclusion d'arcs retourne un graphe vide : l'arc Pl. Valmy-Pl. A.Godien par la N6 n'appartient pas à l'ensemble des arcs du graphe G. Appliqué sur le graphe G1 et le graphe G, l'opérateur d'inclusion de noeuds et d'arcs retourne également un graphe vide. II-3.3 L'opérateur d'INTERSECTIONL'opérateur d'intersection correspond aux opérateurs d'intersection ensembliste. Il se décompose en trois opérateurs différents : l'opérateur d'intersection d'un ensemble de noeuds avec un autre ensemble de noeuds (Pis_n), l'opérateur d'intersection d'un ensemble d'arcs avec un autre ensemble d'arcs (Pis_e), et l'opérateur d'intersection d'un graphe (représentant un ensemble de noeuds et d'arcs) avec un autre graphe (Pis_ne). Ces opérateurs possèdent certaines propriétés communes, mais des spécifications différentes. Nous détaillerons tout d'abord ces propriétés qui définissent l'opérateur d'intersection, au sens général du terme, puis examinerons chacune des spécifications des opérateurs dérivés de l'opérateur d'intersection. Un exemple général sera présenté.
II-3.3.1 Propriétés des opérateurs d'INTERSECTIONLa différence principale de ces opérateurs avec un opérateur classique d'intersection d'un ensemble de noeuds (resp. arcs, resp. noeuds et arcs) avec un autre ensemble réside dans la notion d'abstraction du modèle de graphe. L'opérateur d'intersection doit vérifier l'appartenance d'un noeud (resp. arc, resp noeud ou arc) à un graphe à quelque niveau que ce noeud (resp. arc, resp. noeud ou arc) se trouve. Le but de ces opérateurs est de trouver un ensemble de noeuds (resp. arcs, resp. noeuds et arcs) tel que chaque élément de cet ensemble appartienne aux deux ensembles de noeuds (resp. arcs, resp. noeuds et arcs) sur lesquels est appliqué l'opérateur choisi. Le résultat retourné est l'ensemble des noeuds (resp. arcs, resp. noeuds ou arcs) communs aux deux ensembles. Chacun de ces opérateurs est un opérateur binaire. Notons que la spécification de ces opérateurs fait appel à la notion d'invalidation utilisée par l'opérateur de SELECTION. La signature de ces opérateurs d'INTERSECTION est présentée Figure III-67.
Figure III-67. Signature des opérateur d'intersection II-3.3.2 L'opérateur d'INTERSECTION de noeudsL'opérateur d'intersection de noeuds (Pis_n) permet de trouver les noeuds appartenant à l'intersection de deux ensembles de noeuds. Chacun de ces ensembles est représenté par un graphe pouvant contenir aussi bien des noeuds que des arcs. Tous les noeuds 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 d'intersection de noeuds effectue les mêmes opérations que l'opérateur de SELECTION, en considérant que la vérification de critère sur les arcs retourne toujours Faux, et que la vérification de critère sur les noeuds retourne Vrai lorsque le noeud considéré appartient à un ensemble de noeuds donné.
Soit G'(N',E') le graphe résultant de l'intersection de l'ensemble total des noeuds de G1 avec l'ensemble total des noeuds de G2. 1) Les ensembles N' et E' sont initialisés aux ensembles vides. Tous les noeuds de G2 (quel que soit leur niveau d'abstraction) sont mis dans un ensemble de noeuds ens_noeuds_G2.
2) Soit un arc e1 de E1. Seuls les master_arcs sont examinés. Suivant le résultat de l'examen du réseau_associé à e1 (graphe vide ou non), l'arc n'est pas ajouté à E' ou devient un master_arc invalidé, afin de garder une cohérence dans la hiérarchie des noeuds du graphe.
3) Soit un noeud n1 de N1. Le résultat de l'application de l'opérateur Pis_n sur l'ensemble N1 des noeuds résulte des opérations suivantes :
3.1) Un noeud simple appartenant à l'ensemble de noeuds ens_noeuds_G2 est ajouté à N'.
3.2) Un noeud simple n1 n'appartenant pas à l'ensemble ens_noeuds_G2 est invalidé et ajouté à N' uniquement dans le cas où il est lié à des arcs de E'.
3.3) Un master_noeud n1 nécessite l'examen de ses réseaux_associés. L'opérateur Pis_n est appliqué sur chacun de ces réseaux. Le résultat de cette application retourne, pour chaque réseau, un graphe vide ou non vide. Un réseau dont aucun des noeuds n'appartient à ens_noeuds_G2 est ôté de l'ensemble des réseaux de n1. Un réseau dont au moins un noeud appartient à 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 Pis_n. Le master_noeud n1 peut ou non appartenir à ens_noeuds_G2 (cas 3.3.1 et 3.3.2).
3.3.1) Le master_noeud n1 appartient à 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' auxquels il est attaché en tant qu'extrémité initiale ou finale sont examinés.
3.3.1.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.
3.3.2) Le master_noeud n1 n'appartient pas à l'ensemble ens_noeuds_G2. Un master_noeud n1 ne possédant plus aucun réseau est invalidé s'il est lié à des master_arcs de E'. Un master_noeud n1 possédant encore des réseaux_associés est invalidé et chacun des arcs de E' 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. Le noeud n1 est ajouté à l'ensemble de noeuds N' dans le cas où il est lié à un master_arc.
4) Lors de l'examen des noeuds n1 de N1, certains master_noeuds sont devenus des noeuds simples. Pour conserver une cohérence hiérarchique entre les noeuds, un master_noeud n1 devenu noeud simple est ajouté au réseau_associé de son noeud fantôme "frère", et placé au plus bas niveau de la filiation de ce noeud frère. L'oid de n1 est modifié en conséquence et n1 est ajouté à N'.
II-3.3.3 L'opérateur d'INTERSECTION d'arcsL'opérateur d'intersection d'arcs (Pis_e) permet de trouver les arcs appartenant à l'intersection de deux ensembles d'arcs. Chacun de ces ensembles est représenté par un graphe pouvant contenir aussi bien des noeuds que des arcs. Tous 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 d'intersection d'arcs 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 toujours Faux, et que la vérification de critère sur les arcs retourne Vrai lorsque l'arc considéré appartient à un ensemble d'arcs donné.
Soit G'(N',E') le graphe résultant de l'intersection de l'ensemble total des arcs de G1 avec l'ensemble total des arcs de G2. 1) Les ensembles N' et E' sont initialisés aux ensembles vides. Tous les arcs de G2 (quel que soit leur niveau d'abstraction) sont mis dans un ensemble d'arcs ens_arcs_G2.
2) Soit un arc e1 de E1. Le résultat de l'application de l'opérateur Pis_e sur l'ensemble E1 des arcs résulte des opérations suivantes.
2.1) Un arc simple appartenant à l'ensemble d'arcs ens_arcs_G2 est ajouté à E'.
2.2) Un master_arc e1 appartenant à l'ensemble ens_arcs_G2 nécessite l'examen de son réseau_associé par l'opérateur Pis_e. Suivant le résultat de cet examen, l'arc devient ou non un arc simple. Un master_arc est ajouté à E'; un arc simple est ajouté à ens_arcs_simples.
2.3) 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 Pis_e. 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. Un noeud simple n1 est invalidé et ajouté à N' si des arcs lui sont liés. Ces arcs sont modifiés en conséquence. Un master_noeud n1 est invalidé et nécessite l'examen de ses réseaux_associés.
3.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. n'1 est ajouté à N'.
3. 2) Le noeud n1 est un master_noeud et nécessite l'examen de ses réseaux_associés. L'opérateur Pis_e est appliqué entre G2 et chacun de ces réseaux. Le résultat de cette application retourne, pour chaque réseau, un graphe vide ou non vide. Un réseau dont aucun des arcs n'appartient à l'ensemble ens_arcs_G2 est ôté de l'ensemble des réseaux de n1. Un réseau dont au moins un arc appartient à l'ensemble ens_arcs_G2 est transformé pour ne laisser dans le réseau que les arcs appartenant à cet ensemble, et les noeuds liés à ces arcs. Suivant le résultat de l'examen des réseaux_associés à n1, deux cas se présentent.
3.2.1) Un master_noeud n1 ne possédant plus aucun réseau_associé est invalidé et ajouté dans un ensemble de noeuds ens_noeuds_simples, ainsi que dans N' s'il est lié à des arcs. Ces arcs liés à n1 sont modifiés en conséquence, qu'ils appartiennent à E' ou à l'ensemble d'arcs ens_arcs_simples.
3.2.2) Un master_noeud n1 possédant encore des réseaux_associés est invalidé et ajouté dans N' (qu'il soit lié ou non à des arcs). Les arcs liés à n1 sont modifiés en conséquence, qu'ils appartiennent à E' ou à l'ensemble d'arcs ens_arcs_simples.
3.2.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-3.3.4 L'opérateur d'INTERSECTION de noeuds et d'arcsL'opérateur d'intersection de noeuds et d'arcs (Pis_ne) permet de trouver les noeuds et les arcs appartenant à l'intersection de deux graphes contenant des noeuds et des arcs. 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 d'intersection de noeuds et d'arcs 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 Vrai lorsque le noeud considéré appartient à un ensemble de noeuds donné, et que la vérification de critère sur les arcs retourne Vrai lorsque l'arc considéré appartient à un ensemble d'arcs donné.
Soit G'(N',E') le graphe résultant de cette intersection. 1) Les ensembles N' et E' sont initialisés aux ensembles vides. Tous les arcs de G2 (quel que soit leur niveau d'abstraction) sont mis dans un ensemble d'arcs ens_arcs_G2. Tous les noeuds 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 Pis_ne sur l'ensemble E1 des arcs résulte des opérations suivantes :
2.1) Un arc simple appartenant à l'ensemble d'arcs ens_arcs_G2 est ajouté à E'.
2.2) Un master_arc e1 appartenant à l'ensemble ens_arcs_G2 nécessite l'examen de son réseau_associé par l'opérateur Pis_ne. Suivant le résultat de cet examen, l'arc devient ou non un arc simple. Un master_arc est ajouté à E'; un arc simple est ajouté à ens_arcs_simples.
2.3) 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 Pis_ne. 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 Pis_ne sur l'ensemble N1 des noeuds résulte des opérations suivantes :
3.1) Un noeud simple appartenant à l'ensemble de noeuds ens_noeuds_G2 est ajouté à N'.
3.2) Un noeud simple n1 n'appartenant pas à 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 Pis_ne est appliqué sur chacun de ces réseaux. Le résultat de cette application retourne, pour chaque réseau, un graphe vide ou non vide. Un réseau dont aucun des noeuds n'appartient à ens_noeuds_G2 est ôté de l'ensemble des réseaux de n1. Un réseau dont au moins un noeud appartient à 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 Pis_ne. Le master_noeud n1 peut ou non appartenir à ens_noeuds_G2 (cas 3.3.1 et 3.3.2).
3.3.1) Le master_noeud n1 appartient à 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é initiale ou finale 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 n'appartient pas à 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-3.3.5 Illustration par un exempleSoit un graphe G1(N1, E1) contenant un sous-ensemble des noeuds et des arcs du réseau mondial illustré au chapitre II. Ce graphe contient deux master_noeuds (Paris 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). Le seul arc_sortant de ces réseaux est Pte d'Orléans-Sortie0 de l'A6 par l'A6. Aucun arc_entrant n'est défini. Lyon représente l'abstraction d'un unique réseau_associé (Bordure de Lyon). Le seul arc_entrant de ce réseau est Sortie21 de l'A6-Car. Europe par l'A6. Aucun arc_sortant n'est défini. La Figure III-68 représente le plus haut niveau d'abstraction (niveau 3) du graphe G1.
Figure III-68. Graphe G1 - niveau 3 Les réseaux_associés à Paris sont illustrés dans les Figures A.II-35 et A.II-36. Le réseau_associé au master_noeud Lyon est illustré Figure A.II-46. Le réseau_associé au master_arc Paris-Lyon par l'A6 est illustré Figure A.II-55. Soit un graphe G2(N2, E2) contenant le master_noeud invalidé Paris, le noeud simple invalidé Lyon, le noeud simple invalidé Tours, le master_arc Paris-Lyon par l'A6 et le master_arc invalidé Paris-Tours par l'A10. Le master_noeud Paris représente l'abstraction d'un unique réseau (Réseau Intérieur Parisien) contenant le master_noeud 14ème (qui représente l'abstraction d'un réseau contenant uniquement le noeud Pte Orléans), et le master_noeud *Paris (qui représente l'abstraction d'un réseau contenant uniquement le noeud 18ème). Le master_arc Paris-Lyon par l'A6 représente l'abstraction d'un réseau contenant uniquement les noeuds invalidés Paris et Lyon, et le master_arc Paris-Lyon par *A6 (qui représente l'abstraction d'un réseau contenant le noeud invalidé Partis, les noeuds Pte Orléans et Sortie0 de A6, et l'arc entre Pte Orléans et Sortie0 de A6). Le master_arc invalidé Paris-Tours par l'A10 représente l'abstraction d'un réseau contenant uniquement les noeuds invalidés Paris et Tours et le master_arc invalidé Paris-Tours par *A10. Le master_arc invalidé Paris-Tours par *A10 représente l'abstraction d'un réseau contenant uniquement les noeuds invalidés Paris et Tours et le master_arc invalidé Paris-Tours par **A10. Le master_arc invalidé Paris-Tours par **A10 représente l'abstraction d'un réseau contenant uniquement le noeud Montargis. Les noeuds et arcs notés en gras représentent des noeuds et des arcs invalidés. La Figure III-69 illustre le graphe G2.
Figure III-69. Graphe G2 Appliqué sur le graphe G1 et le graphe G2, l'opérateur d'intersection de noeuds retourne un graphe G' : tous les noeuds de ce graphe appartiennent à l'ensemble des noeuds du graphe G1, mais certains noeuds de G1 ont été invalidés. Tous les arcs de G1 ont été invalidés. Le résultat de l'opérateur d'intersection de noeuds sur G1 et G2 est illustré Figure III-70.
Figure III-70. Graphe G' Appliqué sur le graphe G1 et le graphe G2, l'opérateur d'intersection d'arcs retourne un graphe G' : tous les arcs de ce graphe appartiennent à l'ensemble des arcs du graphe G1, mais certains arcs de G1 ont été invalidés. Tous les noeuds de G1 ont été invalidés. Le résultat de l'opérateur d'intersection d'arcs sur G1 et G2 est illustré Figure III-71.
Figure III-71. Graphe G' Appliqué sur le graphe G1 et le graphe G2, l'opérateur d'intersection de noeuds et d'arcs retourne un graphe G' : tous les noeuds et arcs de ce graphe appartiennent à l'ensemble des noeuds du graphe G1, mais certains noeuds et arcs de G1 ont été invalidés. Le résultat de l'opérateur d'intersection de noeuds et d'arcs sur G1 et G2 est illustré Figure III-72.
Figure III-72. Graphe G' Yüklə 2,35 Mb. Dostları ilə paylaş:
|