Informatique

III- Récapitulatif : les différentes classes du modèle

Le modèle présenté possède trois classes de base : Noeud, Arc et Réseau. Héritant de celles-ci, des classes permettant d'introduire la notion d'abstraction dans le modèle ont été définies : Master_noeud, Master_arc et Réseau_associé.

Des types de base sont construits permettant de définir les différentes classes du modèle :
type OID_global : integer;

type OID_général : list (OID_global);

type ordre : list (integer);
type graphe

tuple

(

noeuds : unique set (Noeud),

arcs : unique set (Arc)

)
Pour chacune des classes de base, des types permettant de définir leur OID sont définis :

type OID_noeud : OID_général;

type OID_arc

tuple

(

extrémité_initiale : OID_noeud,

extrémité_finale : OID_noeud,

hiérarchie_d'abstraction : OID_général

);
type OID_global_réseau

tuple

(

partie_noeud_arc : OID_général,

ordre : ordre

);
type OID_réseau : list (OID_global_réseau);

Les classes de base possède un OID permettant d'identifier chaque objet de ces classes, et un identifiant qui est un sous-ensemble de leur étiquette. La classe Arc identifie également les noeuds extrémités initiale et finale des arcs. La classe Réseau représente un ensemble de noeuds et d'arcs.
class Noeud

type tuple

(

oid : OID_noeud,

nom : string

)

end;

class Arc

type tuple

(

oid : OID_arc,

nom : string,

noeud_initial : Noeud,

noeud_final : Noeud

)

end;

class Réseau

type tuple

(

oid : OID_réseau,

nom : string,

graphe : graphe

)

end;
Les classes permettant d'introduire la notion d'abstraction dans le modèle présenté héritent des trois classes de base précédentes. La classe Master_noeud possède en plus des attributs de la classe Noeud un ensemble de réseaux_associés. La classe Master_arc possède en plus des attributs de la classe Arc un réseau_associé. La classe Réseau_associé possède en plus des attributs de la classe Réseau un ensemble d'arcs_entrant et un ensemble d'arcs_sortant.

class Master_noeud

inherit Noeud

type tuple

(

réseaux_associés : unique set (Réseau_associé)

)

end;
class Master_arc

inherit Arc

type tuple

(

réseau_associé : Réseau_associé

)

end;
class Réseau_associé

inherit Réseau

type tuple

(

arcs_entrant : unique set (Arc),

arcs_sortant : unique set (Arc)

)

end;

IV- Exemple de référence

Nous présentons ici un exemple de base qui va servir de référence tout le long de ce document. Cette base est un graphe G(N, E, n_G, e_G, y_G) où N représente l'ensemble des noeuds du graphe et E l'ensemble de ses arcs.

Les noeuds modélisent des villes possédant une population, un coût moyen d'hôtel et une liste de monuments à visiter. Les noeuds sont donc des éléments de la classe Ville définie précédemment. La fonction d’étiquetage n_G des noeuds fait correspondre à chaque noeud son nom, sa population, son coût moyen par hôtel et une liste des monuments à visiter.

Les arcs modélisent des voies routières possédant un type de transport (autoroute, nationale, départementale, chemin piétonnier), un coût de transport et une distance. Les arcs sont donc des éléments de la classe Route définie précédemment. La fonction d’étiquetage e_G des arcs fait correspondre à chaque arc son nom, son type de transport, son coût de transport et sa distance. Le nom d’un arc comporte le nom de ses extrémités initiale et finale.

Les réseaux modélisent des réseaux routiers possédant un type de réseau (autoroutes, nationales, départementales), et une vitesse maximale autorisée. Les réseaux sont donc des éléments de la classe Réseau_routier définie précédemment.
Le graphe G utilisé en exemple est conséquent. Ce choix est motivé par le désir de définir un graphe correspondant à un cas existant.

Les noeuds et les arcs de ce graphe sont organisés en hiérarchies. Ces hiérarchies sont indépendantes les unes des autres. La hiérarchie des réseaux dépend directement de la hiérarchie des noeuds et de celle des arcs.

Nous présentons tout d'abord les hiérarchies des noeuds et des arcs.

Ces hiérarchies définissent des noeuds et des arcs qui sont utilisés pour construire des réseaux. Chacun de ces réseaux illustre un cas particulier de graphe.

Nous identifions les noeuds et les arcs par leur nom.

Rappelons que les noeuds fantômes possèdent le nom de leur noeud père précédé du caractère "*". Les arcs fantômes possèdent également le nom de leur arc père précédé de ce même caractère.

Figure II-28. Graphe de référence - niveau le plus haut
La hiérarchie des noeuds est illustrée dans la Figure A.II-1 des Annexes. Cette hiérarchie comporte cinq niveaux. A l'image de l'objet Object des systèmes de gestion de bases de données orientées objet [8], le plus haut niveau (le niveau 5) contient un noeud fictif le noeud Monde. Ce noeud permet de structurer hiérarchiquement avec les mêmes niveaux d'abstraction tous les noeuds de la base de données.

La hiérarchie des noeuds est représentée dans les OIDs des noeuds. La Figure A.II-2 présente ces OIDs.

Trois master_noeuds principaux ont été définis : Paris, Lyon, et Blois. Paris est un master_noeud possédant deux réseaux_associés ainsi que des master_noeuds fils. Lyon possède également deux réseaux_associés, mais aucun master_noeud fils. Blois possède un unique réseau_associé et aucun master_noeud fils.
La hiérarchie des arcs est illustrée dans les Figures A.II-3 à A.II-28 des Annexes. Cette hiérarchie comporte cinq niveaux. Tout comme dans le cas de la hiérarchie des noeuds, le niveau le plus haut contient un arc fictif allant du noeud Monde vers lui-même. Cet arc permet de hiérarchiser avec les mêmes niveaux d'abstraction tous les arcs de la base de données.

Les Figures A.II-3 à A.II-26 des Annexes représentent les niveaux 1 et 2 de la hiérarchie des arcs.

Les OIDs des arcs sont construits suivant le même principe que les OIDs des noeuds. L’OID d'un arc comporte un OID général ainsi que les OIDs de ses noeuds extrémités initiale et finale. Afin de faciliter la lecture, nous ne représentons pas les OIDs de ces noeuds dans la description des différents OIDs des arcs de la base. Les OIDs des arcs sont présentés dans les Figures A.II-27 et A.II-28.
La hiérarchie des réseaux dépend de la hiérarchie des noeuds et des arcs. Cette hiérarchie comporte cinq couches. La hiérarchie des réseaux est illustrée dans les Figures A.II-29 à A.II-80 des Annexes.
Au plus haut niveau de la hiérarchie des réseaux se trouve un réseau contenant le noeud Monde et l'arc Arc Général du plus haut niveau de la hiérarchie des arcs. Ce réseau dépend d'un noeud fictif dont l'OID global est 10000. Ce réseau général permet de hiérarchiser avec les mêmes niveaux d'abstraction tous les réseaux de la base de données.
Le Réseau Mondial (Figure A.II-30) contient deux noeuds se trouvant au même niveau hiérarchique (France et Suisse), les noeuds Sortie16 de l'A6 et Genève, et le noeud *Monde. Il contient le master_arc Sortie16 de l'A6-Genève par l'A40. Ce réseau permet d'illustrer l'existence d'un chemin entre deux noeuds (Paris et Genève) dans un réseau alors que ces noeuds n'appartiennent pas au réseau et qu'il n'existe aucun arc entre leurs noeuds "ancêtres" dans le réseau.
Le master_arc Arc général (Figure A.II-31) représente l'abstraction d'un réseau_associé (Réseau Arc général) contenant les noeuds Paris, Tours, *France, Monde et les arcs Paris-Tours par A10 et *Arc général.
Les Figures A.II-32 à A.II-48 illustrent les réseaux_associés correspondant aux master_noeuds de la base.
Le master_noeud France (Figure A.II-32) possède un réseau_associé (Réseau Français) contenant des noeuds appartenant à sa filiation : *France, **France, Paris, Lyon, Fontainebleau, Châteauroux, Tours, StPierre le Moûtier et Sortie16 de A6. Il contient les arcs Paris-Tours par A40, Paris-Châteauroux par N20, Fontainebleau-Tours par N152, Paris-Lyon par A6 et Tours-StPierre le Moûtier par N76. L'arc_sortant de ce réseau est l'arc Sortie16 de A6-Genève par A40. Dans ce réseau il n'existe aucun chemin visible permettant d'aller de Paris à Genève, mais Paris appartient bien aux noeuds du réseau.
Le master_noeud Suisse représente l'abstraction d'un réseau_associé (Réseau Suisse) contenant les noeuds Genève et *Suisse, et l'arc_entrant Sortie16 de A6-Genève par A40 (Figure A.II-33).
Le réseau_associé du master_noeud *Monde (Figure A.II-34) contient uniquement le noeud **Monde.
Le master_noeud Paris représente l'abstraction de deux réseaux_associés : Bordure de Paris et Réseau Intérieur Parisien (Figures A.II-35 et A.II-36). Ces réseaux contiennent des noeuds fils de Paris (*Paris, 12ème, 13ème, 14ème, et 18ème arrondissement) et des noeuds fils des précédents.

Le réseau Réseau Intérieur de Paris ne contient aucun master_arc, uniquement des arcs simples. Il contient également des master_noeuds et des noeuds simples. Le réseau Bordure de Paris contient un master_arc, des master_noeuds et des noeuds simples. Dans le premier réseau, a priori, il n'existe aucun chemin entre Pte de la Chapelle et Pte d'Orléans, alors que dans le deuxième réseau, le master_arc permet d'établir un lien entre ces deux noeuds.

Sur ces deux réseaux, des requêtes d'augmentation et de diminution de détails vont pouvoir être posées, ainsi que des requêtes de chemin.

Le master_noeud *France (Figure A.II-37) représente l'abstraction d'un réseau_associé contenant les noeuds Lyon, Blois, **France, Tours, Châteauroux, StPierre le Moûtier, Sortie16 de A6, Fontainebleau. Il contient les arcs Fontainebleau-Tours par N152, Tours-StPierre le Moûtier par N76. Son arc_sortant est l'arc Sortie16 de A6-Genève par A40. Ses arcs_entrant sont les arcs Paris-Tours par A10, Paris-Lyon par A6, Paris-Châteauroux par N20.

Le master_noeud *Suisse (Figure A.II-38) représente l'abstraction d'un réseau_associé (Réseau de *Suisse) contenant les noeuds Genève et **Suisse, et l'arc_entrant Sortie16 de A6-Genève par A40.
Le master_noeud **Monde (Figure A.II-39) représente l'abstraction d'un réseau_associé (Réseau de **Monde) contenant le noeud ***Monde.
Le master_noeud 12ème arrondissement (Figure A.II-40) représente l'abstraction d'un réseau_associé contenant les noeuds *12ème, Pte Dorée, Pte Bercy, Pte Vincennes, Pl. Bastille, Pl. F.Eboué, Pt Bercy, et les arcs Pte Vincennes-Pte Dorée par Périph.Est, Pte Dorée-Pte Bercy par Bd Soult, Pte Dorée-Pl. Bastille par Av. Daumesnil, Pl. Bastille-Pt Bercy par Quai Rapée, Pte Bercy-Pt Bercy par Quai Bercy, et Pl. F.Eboué-Pte Bercy par Rue Taine. Son arc_entrant est l'arc Pte Bagnolet-Pte Vincennes par Périph.Est, et ses arcs_sortant sont les arcs Pte Bercy-Pte Italiepar Bd Masséna, et Pt Bercy-Pl. Italie par Bd V.Auriol. Ce réseau possède un master_arc, ce qui va permettre d'appliquer deux requêtes d'augmentation de détails à la suite (sur le master_noeud 12ème Arrondissement, puis sur le master_arc Av. Daumesnil). Il illustre également l'impossibilité d'atteindre un noeud (Pl. F.Eboué) à partie de n'importe quel autre noeud de ce réseau.
Le master_noeud 13ème arrondissement (Figure A.II-41) représente l'abstraction d'un réseau_associé contenant les noeuds de sa filiation et aucun arc. Les arcs_entrant de ce réseau sont les arcs Pte Bercy-Pte Italie par Bd Masséna, Pt Bercy-Pl. Italie par Bd V.Auriol. Ses arcs_sortant sont Pl. Italie-Pte Orléans par Bd A.Blanqui, Pte Italie-Pte Orléans par Périph.Est, et Pl. Italie-Sortie1 de N7 par N7.

Ce réseau ne possède aucun master_arc.

Le master_noeud 14ème arrondissement (Figure A.II-42) contient uniquement les noeuds Pte d'Orléans et *14ème. Ses arcs_entrant sont les arcs Pl. Italie-Pte Orléans par Bd A.Blanqui, Pte Italie-Pte Orléans par Périph.Est, et Pte Chapelle-Pte Orléans par Périph.Est. Ses arcs_sortant sont les arcs Pte Orléans-Sortie0 de A6 par A6, et Pte Orléans-Sortie1 de N20 par N20.

Ce réseau permet de lier le master_noeud Paris au reste du monde puisque les arcs sortant de ce réseau sont les seuls arcs de la couche 1 de la hiérarchie des arcs permettant de quitter Paris.

Le master_noeud 18ème arrondissement (Figure A.II-43) représente l'abstraction d'un réseau_associé contenant les noeuds *18ème et Pte Chapelle. Son arc_sortant est l'arc Pte Chapelle-Pte Villette par Périph.Est. Ce réseau ne possède aucun arc et aucun arc entrant.
Le master_noeud *Paris (Figure A.II-44) représente l'abstraction d'un réseau_associé contenant uniquement le noeud **Paris.
Le master_noeud Lyon représente l'abstraction de deux réseaux_associés : Réseau Intérieur Lyonnais et Bordure de Lyon. Le réseau Réseau Intérieur Lyonnais (Figure A.II-45) comporte un master_arc comme arc_sortant. Le réseau Bordure de Lyon (Figure A.II-46) comporte en plus un master_arc comme arc_entrant. Le réseau Bordure de Lyon comporte un master_arc dans l'ensemble de ses arcs.

Le réseau Réseau Intérieur Lyonnais comporte des noeuds isolés (Rpt Croix Luizet) qui ne sont pas isolés dans le réseau Bordure de Lyon. Il n'existe aucun chemin à l'intérieur du premier réseau de Lyon permettant de traverser Lyon jusqu'à la Pte Nord, alors que la combinaison des deux réseaux permet d'obtenir un tel chemin.

Le master_noeud Blois (Figure A.II-47) représente l'abstraction d'un unique réseau_associé. Ce réseau ne comporte aucun chemin permettant d'aller depuis un noeud quelconque de Blois jusqu'au noeud Lycée Hôtelier de Blois (ce noeud permettant ensuite d'aller jusqu'à Amboise).
Le master_noeud **France représente également l'abstraction d'un réseau_associé. Nous ne représentons pas ce réseau très complexe. Il contient tous les noeuds fils de **France et tous les arcs existant entre ces noeuds. Les arcs_entrant et arcs_sortant sont les arcs entre ces noeuds et les noeuds Paris, Lyon, Blois, Genève et tous leurs fils.
Le master_noeud **Suisse (Figure A.II-48) représente l'abstraction d'un réseau_associé comportant le noeud Genève et l'arc_entrant Sortie16 de A6-Genève.
Les Figures A.II-49 à A.II-76 illustrent les réseaux_associés des arcs de la couche 2, de la couche 3 et de la couche 4 de la hiérarchie des arcs.
Les Figures A.II-49 à A.II-54 illustrent les réseaux_associés des arcs de la filiation du master_arc Paris-Tours par A10.

Le master_arc Paris-Tours par A10 (Figure A.II-49) représente l'abstraction d'un réseau_associé comportant le master_arc Sortie5 de A10-Tours par Itinéraire de Délestage, le master_arc Paris-Tours par **A10 et les noeuds Paris, Sortie5 de A10 et Tours.

Ces réseaux illustrent la possibilité de trouver plusieurs chemins à l'intérieur d'un master_arc permettant d'aller d'un noeud à un autre. Ils illustrent de plus le fait d'avoir un noeud dans le réseau_associé d'un master_arc (Orléans, Mer, Meung s/L pour le master_arc Paris-Tours par **A10) et ce même noeud dans le réseau_associé d'un autre master_arc (Itinéraire de Délestage) du réseau, ce qui permet de passer d'un réseau à l'autre pour trouver un chemin de Paris à Tours.
Le master_arc *Arc Général entre Monde et Monde représente l'abstraction d'un réseau_associé. Ce réseau comporte tous les arcs fils de *Arc général dans la hiérarchie des arcs, ainsi que le noeud *France et *Suisse. Nous ne représentons pas ce réseau car il est similaire à celui représenté dans la hiérarchie des arcs (aux deux noeuds précédents près). Notons que le noeud Monde appartient bien à ce réseau car il est extrémité du master_arc *Arc général.
Les Figures A.II-55 à A.II-57 représentent les réseaux_associés du master_arc Paris-Lyon par A6 et de sa filiation.

Le master_arc Paris-Lyon par A6 représente l'abstraction d'un réseau_associé comportant deux master_arcs (Paris-Lyon par N7 et Paris-Lyon par *A6). Il n'existe aucun chemin dans le réseau_associé au master_arc Paris-Lyon par N7 permettant d'aller depuis l'extrémité initiale du master_arc à son extrémité finale. La seule possibilité de chemin existante consiste à "raccorder" le réseau de ce master_arc au réseau de Paris-Lyon par *A6 par l'intermédiaire de noeuds communs à ces deux réseaux (Sortie2 de N7, Nemours).

Les Figures A.II-58 à A.II-60 représentent les réseaux_associés du master_arc Pte Chapelle-Pte Orléans par Périphérique Est et de sa filiation.

Le master_arc Pte Chapelle-Pte Orléans par Périphérique Est représente l'abstraction d'un réseau_associé comportant le master_arc Pte Bercy-Pte Italie par Bd Masséna et le master_arc Pte Chapelle-Pte Orléans par *Périphérique Est. Ce réseau permet d'illustrer le fait d'avoir plusieurs niveaux d'abstraction à l'intérieur d'un master_noeud (Paris).

Les Figures A.II-61 à A.II-65 représentent les réseaux_associés du master_arc Sortie16 de A6-Genève par A40 et de sa filiation.

Le master_arc Sortie16 de A6-Genève par A40 représente l'abstraction d'un réseau_associé contenant les master_arcs Lyon-Pont d'Ain par A42, Pte Nord-Bourg en Bresse par N83 et Bourg en Bresse-Pte Nord par N83. Il contient le master_noeud Lyon. Il contient également le master_arc Sortie16 de A6-Genève par *A40.

Il permet d'illustrer le fait d'arriver par un arc (Bourg en Bresse-Pte Nord par N83) sur un noeud fils d'un master_noeud (Pte Nord) et de quitter ce master_noeud par un arc (Lyon-Pont d'Ain par A42) dont l'extrémité initiale est le master_noeud (Lyon) et non un de ses noeuds fils.
Les Figures A.II-66 à A.II-69 représentent les réseaux_associés du master_arc Fontainebleau-Tours par la N152 et de sa filiation.

Le réseau_associé au master_arc Fontainebleau-Tours par la N152 contient les master_arcs Mer-Blois par N152 et Blois-Amboise par N152, le master_noeud Blois, et le master_arc Fontainebleau-Tours par *N152. Il illustre le fait d'arriver sur un master_noeud par un master_arc et de quiter ce master_noeud par un master_arc. De plus, aucun chemin n'existe, à l'intérieur du master_noeud pour réaliser une liaison entre les deux premiers master_arcs.

Les Figures A.II-70 à A.II-72 représentent les réseaux_associés du master_arc Tours-StPierre le Moûtier par N76 et de sa filiation.

Le master_arc Tours-StPierre le Moûtier par N76 représente l'abstraction d'un réseau_associé contenant un master_arc (Montrichard-Blois par D765) et un master_noeud (Blois). Il contient également le master_arc Tours-StPierre le Moûtier par *N76. Il illustre le fait d'arriver sur un master_noeud (Blois) par un arc quelconque (Montrichard-Blois par D765) et de quitter ce master_noeud par un arc (Bas Rivière-Vierzon par D765) ayant pour extrémité initiale un des fils du master_noeud (Bas-Rivière).

Le master_arc **Arc général contient les master_arcs Paris-Châteauroux par N20, Pte Dorée-Pl. Bastille par Av. Daumesnil, Pte Nord-Opéra par Quais, StFons-Pte Nord par Bd L.Bonnevay et le master_arc ***Arc général.
Nous ne représentons pas le réseau associé à ce master_arc **Arc général. Il contient les arcs précédemment cités, ainsi que les noeuds Paris, Lyon et *France.

Les Figures A.II-73 à A.II-76 illustrent les réseaux_associés des arcs de la filiation de **arc Général.

Nous ne représentons pas le réseau associé au master_arc ***Arc général. Il correspond exactement au réseau représenté dans la hiérarchie des arcs. Il contient également les noeuds Paris, Lyon, Blois et *France.

Les master_arcs Pte Dorée-Pl. Bastille par Av. Daumesnil et Pte Nord-Opéra par quais représentent des master_arcs appartenant au réseau_associé d'un master_noeud (resp. Paris et Lyon).

Le master_arc StFons-Pte Nord par Bd L.Bonnevay représente un arc entrant d'un réseau_associé à un master_noeud (Lyon).

Le master_arc Paris-Châteauroux par N20 représente un master_arc dont le réseau_associé ne possède aucun chemin depuis l'arc entrant de ce réseau jusqu'à son arc sortant (il n'existe pas d'arc entre Sortie2 de N20 et Sortie1 de A10).

Les OIDs des réseaux décrits précédemment sont présentés dans les Figures A.II-77 et A.II-78.