Informatique

II- Les Opérateurs

Les opérateurs se répartissent en trois catégories distinctes : les opérateurs de base, les opérateurs élémentaires et les opérateurs de haut niveau. Nous présentons successivement ces trois catégories. Pour chacun des opérateurs nous présentons les notions qu'il intègre, sa signature, l'algorithme le déterminant, et un exemple illustratif. Les critères et contraintes ne sont pas présentés dans la signature de ces opérateurs, sauf exception.

II-1. Les Opérateurs de Base

Dans cette partie, nous présentons les opérateurs directement liés aux concepts du modèle de graphe (notion d'abstraction). Deux opérateurs binaires de base sont définis : l'opérateur DEVELOP et l'opérateur UNDEVELOP. L'opérateur DEVELOP permet d'obtenir des détails plus spécifiques sur un graphe en mêlant à ce graphe un sous-réseau associé à un master_noeud ou un master_arc du graphe. L'opérateur UNDEVELOP, permet d'obtenir un graphe plus restreint en remplaçant un sous-réseau par un master_noeud ou un master_arc.

II-1.1 L'opérateur de développement DEVELOP

L'opérateur DEVELOP permet d'obtenir des renseignements plus précis sur un graphe en développant certains de ses noeuds et arcs. Seuls les master_noeuds et les master_arcs de plus haut niveau du graphe peuvent être développés. Développer un master_noeud (resp. master_arc) consiste à remonter ses réseaux_associés (resp. son réseau_associé) d'un niveau d'abstraction, c'est-à-dire ajouter au graphe étudié l'ensemble des noeuds et l'ensemble des arcs des réseaux_associés à ce master_noeud (resp. du réseau_associé à ce master_arc). Le graphe résultant du développement de ces noeuds et/ou arcs est alors appelé "graphe étendu".

II-1.1.1 Notion de développement et structure de données

Le développement d'un master_arc implique le changement d'état de ce master_arc dans le résultat. Le réseau_associé du master_arc étant ajouté au graphe étudié, il vient "remplacer" le master_arc dans ce graphe. Le master_arc et son réseau_associé ne peuvent coexister ensemble dans un même graphe car ils représentent un même chemin d'un noeud à un autre. Il est donc nécessaire de rajouter une information sur le master_arc montrant qu'il a été développé, afin de ne pas pouvoir utiliser cet arc dans un chemin. Un arc développé ne possède donc qu'une existence "virtuelle" dans un graphe.

Le développement d'un master_noeud implique également le changement d'état de ce master_noeud dans le graphe résultat. Puisque ce master_noeud peut lui-même être l'extrémité initiale ou finale d'un arc (ou master_arc) du graphe étudié, développer ce master_noeud consiste à ajouter ses réseaux_associés dans le graphe et à changer l'état du master_noeud, en lui ajoutant une information de développement. A la différence des master_arcs développés, les master_noeuds développés et leurs réseaux_associés peuvent coexister dans un même graphe. A la différence des arcs développés, un noeud développé possède une existence réelle (visible) dans un graphe.
La notion de développement est une notion ajoutée au modèle de données. Elle se concrétise par l'ajout d'un élément ("état") dans l'OID des noeuds (resp. arcs). Cet élément est défini par une chaîne de caractères contenant les valeurs "développé" ou "non_développé".
La nouvelle structure de l'OID d'un noeud devient :

type OID_noeud

tuple

(

hiérarchie_d'abstraction : OID_général,

état : string

);
et la nouvelle structure de l'oid d'un arc devient :

type OID_arc

tuple

(

extrémité_initiale : OID_noeud,

extrémité_finale : OID_noeud,

hiérarchie_d'abstraction : OID_général,

état : string

);
Lors du développement d'un master_arc, tous les noeuds et arcs du réseau_associé à ce master_arc sont ajoutés dans le graphe résultat. Afin de garder une cohérence hiérarchique, ces noeuds et arcs doivent garder la notion d'appartenance à un même réseau_associé.

Pour ce faire, l'OID des noeuds et des arcs est modifié afin de pouvoir contenir une référence à un réseau_associé. Cette référence sera symbolisé par la présence dans l'OID des noeuds et des arcs de l'OID du ou des réseaux auxquels ils appartiennent.

La nouvelle structure de l'OID d'un noeud devient :

type OID_noeud

tuple

(

hiérarchie_d'abstraction : OID_général,

état : string,

réseaux : list (OID_réseau)

);
et la nouvelle structure de l'OID d'un arc devient :

type OID_arc

tuple

(

extrémité_initiale : OID_noeud,

extrémité_finale : OID_noeud,

hiérarchie_d'abstraction : OID_général,

état : string,

réseaux : list (OID_réseau)

);
Lorsque les noeuds et arcs appartenant au réseau_associé d'un master_arc développé sont incorporés au graphe résultat, ils n'appartiennent plus à ce réseau_associé, puisque celui-ci a été détruit par le développement du master_arc. Cependant la notion d'appartenance à ce réseau_associé doit rester dans le graphe résultat. La notion de réseau développé est donc créée. Un réseau développé représente l'"image virtuelle" d'un réseau_associé. Si, dans un graphe, un master_arc est détruit, son réseau_associé l'est également.
Ce réseau_associé est alors remplacé par un réseau développé, ce qui permet de garder, pour les noeuds et arcs dépendant du réseau_associé détruit, la notion d'appartenance à un même réseau. La notion de réseau développé se concrétise par l'ajout d'un élément ("état") dans l'OID des réseaux. Deux états sont possibles : "développé" ou "non_développé".
La nouvelle structure de l'OID d'un réseau devient :

type OID_réseau

tuple

(

hiérarchie_d'abstraction : list(OID_global_réseau),

état : string

);

La signature de l'opérateur DEVELOP est présentée Figure III-1.

DEVELOP : G0 (N0, E0, nG0, eG0, yG0) x G(N, E, nG, eG, yG) -> G'(N',E', n'G, e'G, y'G) où G0 est un graphe contenant un ensemble N0 de noeuds à développer, et un ensemble E0 d'arcs à développer, G(N, E, nG, eG, yG) est un graphe à étendre, G'(N',E', n'G, e'G, y'G) est un graphe étendu

Figure III-1. Signature de l'opérateur DEVELOP

II-1.1.2 Spécification de l'opérateur DEVELOP

Les fonctions permettant de décrire l'opérateur DEVELOP sont présentées en Annexes.

Soit un graphe G(N,E) à étendre, et G₀ un graphe contenant un ensemble N₀ de noeuds à développer dans G, et un ensemble E₀ d'arcs à développer dans G. Les noeuds (resp. arcs) de N₀ (resp. E₀) sont des master_noeuds (resp. master_arcs) appartenant à N (resp. E) et ne présentant pas déjà le caractère développé.

Soit G'(N',E') le graphe résultant du développement des noeuds et arcs de G₀ dans G.

1) Les ensembles N' et E' sont respectivement initialisés à N et E.

N' = N E' = E

2) Le développement d'un arc e₀ de E₀ appartenant à E et ne présentant pas le caractère développé consiste à transformer le réseau_associé au master_arc e₀ en un réseau développé. Tous les noeuds et arcs de ce réseau développé sont alors ajoutés au graphe G' et le master_arc e₀ est transformé.

Le développement d'un arc e₀ de E₀ résulte des opérations suivantes :

Ri(Ni,Ei) = Développe_Réseau (Réseau_Associé_Arc(e0)); G'(N',E') = Remplace_Oidréseau_Graphe ( G'(N',E'), Oid_Réseau (Réseau_Associé_Arc (e0)), Oid_Réseau (Ri) ); N' = N' n1niveau Ni; E' = E' Èe1niveau Ei; e'0 = Développe_Arc (Remplace_Réseau_Arc (e0,Ri)); E' = E' -e1niveau {e0} Èe1niveau {e'0};

3) Le développement d'un master_noeud n₀ de N₀, appartenant à N et ne présentant pas le caractère développé consiste à transformer chacun des réseaux_associés à n₀ en un réseau développé. Chacun des noeuds et des arcs de ces réseaux est alors rajouté au graphe G', et le noeud n₀ est transformé en lui rajoutant le caractère développé.

Le développement d'un master_noeud n₀ de N₀, appartenant à N et ne présentant pas le caractère développé, résulte des opérations suivantes :

n'0 = Développe_Noeud (n0); arcs_sortant = Ø; arcs_entrant = Ø; n'0 = n0; " Ri Î Réseaux_Associés_Noeud (n0) R'i(N'i, E'i) = Développe_Réseau (Ri); G'(N',E') = Remplace_Oidréseau_Graphe ( G'(N',E'), Oid_Réseau (Ri), Oid_Réseau (R'i) ); N' = N' Èn1niveau N'i; E' = E' Èe1niveau E'i; n'0 = Remplace_Réseau_Noeud (n0,Ri,R'i); arcs_entrant = arcs_entrant Èe1niveau Arcs_Entrant(R'i); arcs_sortant = arcs_sortant Èe1niveau Arcs_Sortant(R'i); N' = Remplace_Noeud_Ens_Noeuds (N',n0,n'0); E' = Remplace_Noeud_Ens_Arcs (E',n0,n'0);

4) Les arcs_entrant et les arcs_sortant des réseaux précédents sont examinés. Si l'extrémité initiale (resp. finale) d'un arc_entrant (resp. arc_sortant) de ces réseaux appartient déjà à N', alors l'arc_entrant (resp. arc_sortant) est rajouté à E'.

" e Î arcs_entrant Si (Extrémité_Initiale(e) Î N') Alors E' = E' Èe1niveau {e}; Fsi " e Î arcs_sortant Si (Extrémité_Finale(e) Î N') Alors E' = E' Èe1niveau {e}; Fsi

II-1.1.3 Illustration par un exemple

Soit un graphe G(N,E) contenant un sous-ensemble des noeuds et des arcs du réseau mondial illustré au chapitre II (arcs Paris-Lyon par l'A6 et Sortie16 de l'A6-Genève par l'A40). Ce graphe contient deux master_noeuds (Paris et Lyon), deux noeuds (Sortie16 de l'A6, Genève) et deux master_arcs (Paris-Lyon par A6 et Sortie16 de l'A6-Genève par A40).

Paris représente l'abstraction de deux réseaux_associés. 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. Le seul arc_sortant est Pte Nord-Bourg en Bresse par la N83. Le réseau_associé au master_arc Paris-Lyon par l'A6 ne contient plus Paris, ni les réseaux_associés à ses master_arcs fils.

La Figure III-2 représente le graphe G ainsi que les réseaux_associés des master_arcs et master_noeuds du graphe. Seuls les arcs_entrant et arcs_sortant des réseaux_associés aux noeuds sont représentés. L'intérieur des réseaux est semblable aux représentations des Figures A.II-55, A.II-70 (pour les arcs), A.II-35, A.II-36 et A.II-45 (pour les noeuds) des Annexes.

Figure III-2. Graphe G avec visualisation des réseaux_associés
Appliquons l'opérateur DEVELOP sur le graphe G et sur un graphe contenant seulement le master_noeud Paris et le noeud Corbeil-Essonnes appartenant à un réseau de la filiation du Réseau_associé au master_arc Paris-Lyon par l'A6. Le plus haut niveau d'abstraction du graphe G₁ résultant de cette opération est représenté par la Figure III-3. Seul le master_noeud Paris a été développé car seul ce noeud apparaissait dans l'ensemble N des noeuds de G. Les deux réseaux_associés à Paris ont été développés.


Figure III-3. Graphe G₁

Appliquons l'opérateur DEVELOP sur le graphe G₁ et sur un graphe contenant seulement le master_arc Paris-Lyon par l'A6. Le plus haut niveau d'abstraction du graphe G₂ résultant de cette opération est représenté par la Figure III-4.

Figure III-4. Graphe G₂
Le graphe G₂ contient plusieurs master_arcs : Pte Chapelle-Pte Orléans par Périphérique Est, Sortie16 de l'A6-Genève par l'A40, Paris-Lyon par *A6 (arc fantôme fils de Paris-Lyon par A6) et Paris-Lyon par la N7. Appliquons DEVELOP sur ce graphe et sur un graphe contenant le master_arc Paris-Lyon par *A6. Le plus haut niveau d'abstraction du Graphe G₃ résultant de cette opération est représenté par la Figure III-5.


Figure III-5. Graphe G₃

II-1.1.4 Généralisation de l'opérateur DEVELOP

Par convention, l'opérateur DEVELOP fournit un développement des master_noeuds et/ou des master_arcs à un seul niveau. Appliquer DEVELOP sur un master_noeud permet de visualiser tous les noeuds et arcs contenus dans ses réseaux_associés (ses noeuds et arcs "fils"). Par contre, cette opération ne permet pas de visualiser l'ensemble des noeuds et des arcs dépendant, à quelque niveau d'abstraction que ce soit, de ce master_noeud (ses noeuds et arcs "petits-fils", par exemple). Notons qu'un noeud ou un arc développé existe toujours dans un graphe, à un niveau virtuel pour l'arc et réel pour le noeud, ceci afin de pouvoir appliquer l'opérateur inverse de l'opérateur DEVELOP. Les noeuds et arcs développés ne sont donc jamais éliminés de l'ensemble des noeuds et arcs du graphe. Ils sont simplement rendus ou non "invisibles".

Pour obtenir une application récursive de l'opérateur DEVELOP, un opérateur similaire, l'opérateur DEVELOP* est défini. Appliqué sur des noeuds et des arcs d'un graphe, DEVELOP* développe récursivement tous les master_noeuds et tous les master_arcs appartenant aux réseaux_associés à ces noeuds et ces arcs, jusqu'au plus bas niveau d'abstraction possible. Appliquer l'opérateur DEVELOP* sur un master_noeud permet de visualiser tous ses noeuds et arcs "fils", "petits-fils", "arrières-petits-fils", etc...

La signature de DEVELOP* est présentée Figure III-6.

DEVELOP* : G0 (N0, E0, nG0, eG0, yG0) x G(N,E, nG, eG, yG) -> G'(N',E', n'G, e'G, y'G) où G0 est un graphe contenant un ensemble N0 de noeuds à développer, et un ensemble E0 d'arcs à développer, G(N,E, nG, eG, yG) est un graphe à étendre, G'(N',E', n'G, e'G, y'G) est un graphe étendu

Figure III-6. Définition de l'opérateur DEVELOP*
Soit un graphe G(N,E) à étendre jusqu'au plus bas niveau, G₀ le graphe contenant l'ensemble N₀ des noeuds à développer dans G, et l'ensemble E₀ des arcs à développer dans G.

Soit G'(N',E') le graphe résultant du développement au plus bas niveau des noeuds et arcs de G₀ dans G.

1) Les règles de construction du résultat de l'opérateur DEVELOP* consistent à appliquer DEVELOP sur les noeuds et arcs de N₀ et E₀. Appelons noeuds et arcs "fils" les noeuds et arcs appartenant aux réseaux_associés des noeuds et arcs de N₀ et E₀. Si ces noeuds et ces arcs fils ne possèdent pas de réseau_associé, alors DEVELOP* s'arrête et le résultat est le graphe résultant de l'application de DEVELOP.

G1(N1, E1) = DEVELOP(G0 (N0, E0), G(N,E)); Ens_noeuds = Ø; Ens_arcs = Ø; " n Î N1 Si ( (Master_Noeud(n) = Vrai) Ù ( ($ n0 Î N0 | Noeud_Père_Noeud(n0,n) = Vrai) Ú ($ e0 Î E0 | Arc_Père_Nd(e0,n) = Vrai)) ) Alors Ens_noeuds = Ens_noeuds Èn1niveau {n}; Fsi " e Î E1 Si ( (Master_Arc(e) = Vrai) Ù ( ($ n0 Î N0 | Noeud_Père_Arc(n0,e) = Vrai) Ú ($ e0 Î E0 | Arc_Père_Arc(e0,e) = Vrai)) ) Alors Ens_arcs = Ens_arcs Èe1niveau {e}; Fsi

2) Si ces noeuds et ces arcs fils sont des master_noeuds et des master_arcs avec des réseaux_associés, alors DEVELOP* est réappliqué sur ces noeuds et ces arcs, ainsi que sur le graphe résultant de l'application de DEVELOP.

Si ( (Ens_noeuds Ø) Ú (Ens_arcs Ø)) Alors G'(N', E') = DEVELOP*( Construit_Graphe(G0, Ens_noeuds, Ens_arcs), G1(N1,E1)); Sinon G'(N', E') = G1(N1,E1); Fsi

Appliqué sur le graphe G de la figure III-2 et sur un graphe formé du noeud Paris, le résultat de l'opérateur DEVELOP* est le graphe G₄ de la Figure III-7. Chacun des master_noeuds et des master_arcs de la filiation de Paris ont été développés.

Figure III-7. Graphe G₄

Appliqué sur le graphe G de la figure III-2 et sur un graphe formé du master_arc Paris-Lyon par l'A6, le résultat de l'opérateur DEVELOP* est le graphe G₅ de la Figure III-8. Chacun des master_arcs de la filiation de Paris-Lyon par l'A6 a été développé.

Figure III-8. Graphe G₅

II-1.2 L'opérateur de regroupement UNDEVELOP

L'opérateur UNDEVELOP réalise une opération contraire à la précédente : au lieu de développer des noeuds et des arcs (c'est-à-dire de remonter leurs réseaux_associés d'un niveau d'abstraction), il permet de regrouper des noeuds et des arcs (c'est-à-dire de les descendre d'un niveau d'abstraction). Appliqué sur un graphe, cet opérateur binaire permet de reconstruire les réseaux_associés développés en reconstruisant les hiérarchies des noeuds, des arcs et des réseaux. Le graphe résultant de l'application de l'opérateur UNDEVELOP est appelé "graphe réduit".

II-1.2.1 Notion de regroupement et structure de données

Considérons l'opérateur DEVELOP comme un lien entre deux graphes : un graphe contenant les noeuds et arcs à développer, et un graphe contenant les noeuds et arcs des réseaux_associés aux noeuds et/ou arcs développés dans cet ensemble. Un master_noeud (resp. master_arc) est alors assimilé à l'ensemble des noeuds et des arcs dont il est l'abstraction. Chaque noeud et/ou arc est représenté comme un élément d'une arborescence dont les liens sont les opérations de développement.

Considérons le graphe de référence G(N,E, n_G, e_G, y_G). Ce graphe contient les noeuds Paris, Lyon, Sortie16 de l'A6 et Genève, ainsi que les arcs Paris-Lyon par l'A6 et Sortie16 de l'A6-Genève par l'A40 (graphe de la Figure III-2). Le développement de Paris et de Paris-Lyon par l'A6 peut s'écrire sous la forme de l'arbre représenté Figure III-9.


Figure III-9. Développement de Paris et Paris-Lyon par l'A6
Les réseaux_associés au master_noeud Paris contient en particulier les master_noeuds *Paris, 12ème, 13ème, 14ème et 18ème Arrondissements et le master_arc Pte Chapelle-Pte Orléans par Périphérique Est. Le réseau_associé au master_arc Paris-Lyon par l'A6 contient en particulier les master_noeuds Paris et Lyon et les master_arcs Paris-Lyon par *A6 et Paris-Lyon par la N7. Le développement des master_noeuds 12ème, et 14ème Arrondissements et des master_arcs Pte Chapelle-Pte Orléans par Périphérique Est et Paris-Lyon par *A6 transforme l'arbre précédent en une nouvelle arborescence.



Figure III-10. Développement de 12ème, 14ème, Périph.Est et Paris-Lyon par *A6
Le réseau_associé au master_noeud 12ème Arrondissement contient en particulier le master_arc Pte Dorée-Pl. Bastille par Av. Daumesnil. Le développement du master_arc Pte Dorée-Pl. Bastille par Av. Daumesnil transforme l'arbre précédent en une nouvelle arborescence représentée Figure III-11.



Figure III-11. Développement de Pte Dorée-Pl. Bastille par Av. Daumesnil

Appliquons maintenant l'opérateur UNDEVELOP sur le noeud Nemours appartenant au réseau_associé au master_arc Paris-Lyon par *A6, et sur le noeud 18ème Arrondissement appartenant au réseau_associé au master_noeud Paris. Appliquer UNDEVELOP sur le noeud Nemours (resp. le noeud 18ème Arrondissement) signifie ne plus rendre apparent le réseau_associé auquel il appartient. Les noeuds ou arcs pères de ces deux noeuds sont donc regroupés.

Le résultat de cet opérateur sera l'arbre représenté Figure III-12.


Figure III-12. Regroupement des pères de 18ème Arrondissement et de Nemours
Pour être capable de transformer un sous-réseau en un réseau_associé, il faut pouvoir retrouver l'OID de ce réseau_associé. Ceci est rendu possible par l'existence de la partie "réseau" dans l'OID des noeuds et des arcs, et par l'existence des réseaux développés. Un master_arc développé existant toujours dans le graphe (même s'il n'a plus qu'une existence virtuelle), il est possible de le recréer (en changeant son état qui passe de "développé" à "non développé"). Son réseau_associé existe, dans le graphe, sous la forme d'un réseau développé. Il est donc possible de recréer ce réseau.
Ces opérations de DEVELOP et UNDEVELOP ne conduisent donc à aucune perte d'information, même d'information alphanumérique comme les noms des réseaux ou des arcs. Ceci reste vrai également pour les master_noeuds. Aucune perte d'information n'est due à la re-création de ce master_noeud puisque un master_noeud développé existe toujours dans le graphe. Les noeuds et arcs de ses réseaux_associés se trouvent dans le graphe, et possèdent dans leur OID la référence de ce master_noeud et du réseau développé dont ils dépendent. Il est donc possible de les enlever du graphe et de les remettre dans les réseaux_associés au master_noeud. De plus, le master_noeud n'ayant pas été détruit, ces réseaux_associés existent toujours. Là encore, aucune perte d'information n'est effectuée.
La signature de cet opérateur est présentée dans la Figure III-13.

UNDEVELOP : G0 (N0, E0, nG0, eG0, yG0) x G(N,E, nG, eG, yG) -> G'(N',E', n'G, e'G, y'G) où G0 est un graphe contenant un ensemble N0 de noeuds et un ensemble E0 d'arcs sur lesquels il faut obtenir moins de détails, G(N,E, nG, eG, yG) est un graphe à réduire, G'(N',E', n'G, e'G, y'G) est un graphe réduit

Figure III-13. Signature de l'opérateur UNDEVELOP

II-1.2.2 Spécification de l'opérateur UNDEVELOP

Les fonctions supplémentaires permettant de décrire l'opérateur UNDEVELOP sont présentées en Annexes.

Soit un graphe G(N,E) et un graphe G₀ contenant les ensembles de noeuds et d'arcs N₀ et E₀ sur lesquels s'applique l'opérateur UNDEVELOP.

Soit G'(N',E') le graphe résultant du développement des noeuds et arcs de N₀ et E₀ dans G.

1) Les ensembles N' et E' sont respectivement initialisés à N et E, et la liste des réseaux développés auxquels appartiennent les noeuds et arcs de N₀ et E₀ est initialisée à la liste vide.

N' = N E' = E list_réseau = Ø

2) L'application de l'opérateur UNDEVELOP sur un noeud n₀ de N₀ (resp. arc e₀ de E₀) n'appartenant pas à un réseau développé laisse le graphe inchangé. Par contre, l'application de l'opérateur UNDEVELOP sur un noeud n₀ de N₀ (resp. e₀ de E₀) consiste à identifier dans le graphe G les réseaux développés (list_réseau) auxquels appartient ce noeud (resp. cet arc).

" n0 Î N0 list_réseau = list_réseau + Oidréseau_Développé_Noeud (n0); " e0 Î E0 list_réseau = list_réseau + Oidréseau_Développé_Arc (e0);

3) Les noeuds et arcs appartenant à ces réseaux développés (noeuds et arcs "frères" de e₀ ou n₀), ainsi que les noeuds et arcs dépendant des réseaux_associés à ces noeuds et arcs frères sont enlevés des ensembles N et E, s'ils n'appartiennent pas à d'autres réseaux développés que ceux de la liste ou s'ils ne sont pas des noeuds et arcs de plus haut niveau d'abstraction du graphe G (avant tout développement). Dans le cas contraire, leur OID est modifié pour intégrer le regroupement des réseaux.

" n Î N Si ( ( Noeud_Appartient_Réseaux (n,list_réseau) = Vrai ) Ú ( Noeud_Appartient_Filiation_Réseaux (n,list_réseau,G) = Vrai ) Alors Si ( ( Noeud_Autre_Réseau_Développé (n,list_réseau) = Faux ) Ù ( Noeud_Plus_Haut_Niveau_Graphe (n,G) = Faux ) ) Alors N' = N' -n1niveau {n}; Sinon N' = N' -n1niveau {n} Èn1niveau {Remplace_Oidréseaux_Noeud ( n, list_réseau, Regroupe_Oidréseaux(list_réseau))}; Fsi Fsi " e Î E Si ( ( Arc_Appartient_Réseaux (e,list_réseau) = Vrai ) Ú ( Arc_Appartient_Filiation_Réseaux (e,list_réseau,G) ) Alors Si ( ( Arc_Autre_Réseau_Développé (e,list_réseau) = Faux ) Ù ( Arc_Plus_Haut_Niveau_Graphe (e,G) = Faux ) ) Alors E' = E' -e1niveau {e}; Sinon E' = E' -e1niveau {e} Èe1niveau {Remplace_Oidréseaux_Arc ( e, list_réseau, Regroupe_Oidréseaux(list_réseau))}; Fsi Fsi

4) Appliquer UNDEVELOP sur un noeud n₀ de G signifie enlever tous les noeuds et arcs des réseaux_associés au noeud ou arc père de n₀. Les noeud ou arc père des noeuds n₀ de N₀ (resp. arcs e₀ de E₀) sont donc identifiés et regroupés.

" n0 Î N0 " n Î N Si ( Noeud_Père_Noeud (n,n0) = Vrai ) Alors N' = N' -n1niveau {n} Èn1niveau {Regroupe_Noeud (n) }; Fsi " e Î E Si ( Arc_Père_Noeud (e,n0) = Vrai ) Alors E' = E' -e1niveau {e} Èe1niveau {Regroupe_Arc (e) }; Fsi N" = N'; E" = E'; " e0 Î E0 " n Î N' Si ( Noeud_Père_Arc (n,e0) = Vrai ) Alors N" = N" -n1niveau {n} Èn1niveau {Regroupe_Noeud (n) }; Fsi " e Î E' Si ( Arc_Père_Arc (e,e0) = Vrai ) Alors E" = E" -e1niveau {e} Èe1niveau {Regroupe_Arc (e) }; Fsi

5) Le graphe réduit est composé des ensembles de noeuds et d'arcs N" et E".

G'(N',E') = Construit_Graphe (G, N",E");

II-1.2.3 Illustration par un exemple

Soit le graphe G₁ précédent contenant les noeuds Paris, Lyon, Sortie16 de l'A6 et Genève, les arcs Paris-Lyon par A6 et Sortie16 de l'A6-Genève par A40, et où le master_noeud Paris a été développé. Ce graphe est illustré dans la Figure III-3 précédente.

Appliquons l'opérateur UNDEVELOP sur ce graphe G₁ et sur un graphe contenant le noeud Pt de Bercy appartenant à un des réseaux_associés de Paris. Paris est regroupé. Le résultat de cette opération est le graphe G initial, illustré dans la Figure III-14.


Figure III-14. Graphe G
Appliquons maintenant l'opérateur UNDEVELOP sur le graphe G₄ de la Figure III-7 précédente et sur un graphe contenant seulement le noeud 12ème Arrondissement. Dans le graphe G₄, tous les master_noeuds fils de Paris avaient été développés (dont 12ème Arrondissement). Le graphe résultant de cette opération est le graphe G précédent. Paris a été regroupé, ainsi que tous ses master_noeuds et master_arcs fils.
De même, si nous appliquons UNDEVELOP sur le graphe G₃ de la Figure III-5 précédente (où le master_arc Paris-Lyon par l'A6 a été développé, ainsi que son fils Paris-Lyon par *A6), et sur un graphe formé du noeud Nemours appartenant au réseau_associé à Paris-Lyon par *A6, nous obtenons le graphe G₂ de la Figure III-4 précédente (où Paris-Lyon par *A6 n'est plus développé). Par contre, appliquant UNDEVELOP sur le graphe G₃ et sur un graphe formé du master_arc Paris-Lyon par la N7, nous obtenons le graphe G₁ de la Figure III-3 précédente : Paris-Lyon par l'A6 a été regroupé, ainsi que son fils Paris-Lyon par *A6.

II-1.2.4 Généralisation de l'opérateur UNDEVELOP

Par convention, l'opérateur UNDEVELOP fournit une simple réduction de sous-réseaux en master_noeuds et/ou en master_arcs. Pour obtenir une application récursive de l'opérateur UNDEVELOP, un opérateur similaire, UNDEVELOP*, a été créé. UNDEVELOP* permet l'obtention d'un graphe à son plus haut niveau d'abstraction (alors que DEVELOP* permettait l'obtention d'un graphe à son plus bas niveau d'abstraction à partir d'un niveau donné). UNDEVELOP* regroupe récursivement tous les noeuds et tous les arcs d'un graphe, à quelque niveau d'abstraction qu'ils se trouvent.

La signature de UNDEVELOP* est présentée dans la Figure III-15.

UNDEVELOP* : G0 (N0,E0, nG0, eG0, yG0) x G(N,E, nG, eG, yG) -> G'(N',E', n'G, e'G, y'G) où G0 est un graphe contenant un ensemble N0 de noeuds et un ensemble E0 d'arcs sur lesquels il faut obtenir moins de détails, G(N,E, nG, eG, yG) est un graphe étendu, G'(N',E', n'G, e'G, y'G) est un graphe regroupé

Figure III-15. Application récursive de l'opérateur UNDEVELOP*
Les règles de construction du résultat de l'opérateur UNDEVELOP* consistent à appliquer UNDEVELOP sur les noeuds et arcs de G₀, puis à réappliquer UNDEVELOP* sur les noeud et arcs pères des noeuds et arcs de G₀.
Soit un graphe G(N,E) et un graphe G₀ contenant les ensembles de noeuds et d'arcs N₀ et E₀ sur lesquels s'applique l'opérateur UNDEVELOP*.

Soit G"(N",E") le graphe résultant du regroupement successif des noeuds et arcs de N₀ et E₀ dans G.

1) L'opérateur UNDEVELOP est appliqué sur G₀ et G. Le résultat de cette application est un graphe réduit G'(N',E'). L'ensemble des noeuds à regrouper est initialisé à un ensemble vide, de même que l'ensemble des arcs à regrouper dans G'.

G'(N',E') = UNDEVELOP (G0,G); trouvé = Faux; ens_noeuds_à_regrouper = Ø; ens_arcs_à_regrouper = Ø;

2) Chaque noeud n de N₀ est examiné. Si n possède un noeud (resp. arc) père dans N' (resp. E') qui appartienne à un réseau développé, alors ce noeud (resp. cet arc) père doit être regroupé.

" n Î N0 " n' Î N' Si ( ( Noeud_Père_Noeud (n',n) = Vrai ) Ù ( Oidréseau_Développé_Noeud (n') list() ) ) Alors ens_noeuds_à_regrouper = ens_noeuds_à_regrouper Èn1niveau {n'}; trouvé = Vrai; Fsi " e' Î E' Si ( ( Arc_Père_Noeud (e',n) = Vrai ) Ù ( Oidréseau_Développé_Arc (e') list() ) ) Alors ens_arcs_à_regrouper = ens_arcs_à_regrouper Èe1niveau {e'}; trouvé = Vrai; Fsi

3) Chaque arc e de E₀ est examiné. Si e possède un noeud (resp. arc) père dans N' (resp. E') qui appartienne à un réseau développé, alors ce noeud (resp. cet arc) père doit être regroupé.

4) S'il n'existe plus aucun noeud ou arc père des noeuds et arcs de N₀ et E₀ qui puisse être regroupé, alors UNDEVELOP* retourne le graphe G. Dans le cas contraire, UNDEVELOP* est réappliqué sur les noeuds et arcs à regrouper, et sur le graphe G'.

Si ( trouvé = Vrai ) Alors G"(N",E") = UNDEVELOP* ( Construit_Graphe ( G0,ens_noeuds_à_regrouper, ens_arcs_à_regrouper), G'(N',E') ); Sinon G"(N",E") = G'(N',E'); Fsi

Appliquons l'opérateur UNDEVELOP* sur le graphe G₄ de la Figure III-7 précédente et sur un graphe contenant seulement le noeud Pl. Bastille appartenant au réseau du 12ème Arrondissement. Dans le graphe G₄, tous les master_noeuds fils de Paris avaient été développés (dont 12ème Arrondissement). Le graphe résultant de cette opération est le graphe G de la Figure III-2. 12ème Arrondissement a été regroupé, ainsi que son père (Paris), et donc également tous les fils de son père.

De même, si nous appliquons UNDEVELOP* sur le graphe G₃ de la Figure III-5 précédente (où le master_arc Paris-Lyon par l'A6 a été développé, ainsi que son fils Paris-Lyon par *A6), et sur un graphe formé du noeud Nemours appartenant au réseau_associé à Paris-Lyon par *A6, nous obtenons le graphe G. Paris-Lyon par *A6 a été regroupé, ainsi que son père (Paris-Lyon par l'A6) et par conséquence tous les fils de son père (Paris-Lyon par la N7).

II-1.3 Conclusion

Les opérateurs DEVELOP et UNDEVELOP permettent d'exploiter les possibilités de la notion d'abstraction définie dans le modèle de graphe.

L'opérateur DEVELOP développe des master_arcs et des master_noeuds. L'opérateur UNDEVELOP est capable de reconstruire ces master_arcs et master_noeuds (grâce aux parties "hiérarchie_d'abstraction" et "réseaux" dans les OIDs des noeuds et des arcs). Cette reconstruction se situe à la fois au niveau topologique (au niveau de la topologie du graphe) et au niveau des données alphanumériques (non perdues lors du développement des master_noeuds et des master_arcs par l'opérateur DEVELOP). Du point de vue du modèle de graphe comme du point de vue des données alphanumériques, l'information a bien été préservée.