Informatique

Chapitre II - Le modèle de graphe

Introduction

Les Systèmes d'Information Géographique (ou SIG) sont divisés en deux classes : les SIG traitant d'informations thématiques (i.e, villes, forêts) et les SIG traitant d'informations de type réseau (i.e, réseaux de transport, réseaux électriques). Un graphe (ensemble de noeuds et d'arcs labellés [10]) est la notion conceptuelle la plus aisée pour modéliser des informations orientées réseau.

Nous avons vu dans le chapitre précédent que les SIG de types réseaux existant actuellement sont incapables de répondre à certaines requêtes posées par un utilisateur. Un nouveau modèle de graphe [44] a donc été proposé [43]. Ce modèle de graphe allie les notions de la théorie des graphes telles que les noeuds, les arcs, les graphes, et les notions de l'orienté objet [6] telles l'objet et l'abstraction. Un noeud ou un arc représente l'abstraction de sous-réseaux. Aucune contrainte n'est définie sur la topologie de ce sous-réseau. Nous utilisons la notion d'OID logique (Object IDentifier) pour identifier les objets. Cette notion est similaire à celle de l'OID en bases de données orientées objet, la sémantique étant la même dans les deux cas. Néanmoins, l'OID défini dans le modèle de graphe est totalement indépendant du système de bases de données utilisé.

Une classe est définie, selon les définitions de l'orienté objet, comme un groupe d'objets ayant la même structure et le même comportement. Dans ce document, une classe est définie en utilisant le constructeur de tuple qui introduit la notion d'agrégation (tuple), le constructeur de liste (list), le constructeur ensembliste (set) et les types de base classiques (i.e., entier, caractère). Les classes représentent les différents objets de ce modèle.

Dans cette partie nous présentons le modèle de données (notion de noeuds, d'arcs et de réseaux et second niveau d'abstraction), la gestion des différents niveaux d'abstraction de ce modèle, un récapitulatif des différentes classes du modèle et un exemple général pour cette étude.

Ce modèle de données est totalement indépendant du système de base de données utilisé. Pour faciliter la lecture, une représentation de chacune des notions du modèle est donnée. Cette représentation utilise le formalisme du modèle de données orienté objet O₂ [8, 50].

I- Le modèle de données

Une information géographique de type réseau possède trois composantes : des propriétés alphanumériques (nom, population...), des propriétés géométriques (coordonnées géométriques de l'objet), et des propriétés topologiques (relations avec les autres objets géographiques). Le modèle de graphe proposé permet de modéliser la topologie d'un réseau géographique. Il intègre également des propriétés alphanumériques des objets. Les propriétés géométriques ne sont pas modélisées.

Des classes de base sont définies (noeud, arc et réseau). Un noeud ou un arc représente l'abstraction de réseaux. Des classes complexes (Master_noeud, Master_arc et Réseau_associé) sont alors définies pour intégrer cette notion. Ces classes représentent le second niveau d'abstraction du modèle.

I-1. Les composants de base

Un graphe est défini selon les principes de la théorie des graphes étudiées au chapitre I. Un graphe G est défini par G(N, E, n_G, e_G, y_G) où N représente l'ensemble des sommets du graphe, E l'ensemble de ses arcs, n_G la fonction d'étiquetage des sommets, e_G la fonction d'étiquetage des arcs et y_G la fonction d'incidence faisant correspondre deux sommets (son extrémité initiale et son extrémité finale) à un arc. Un graphe est considéré comme orienté.

Par la suite, nous appelons "noeud" un sommet possédant une étiquette, et "arc" un arc possédant une étiquette. Les étiquettes des noeuds et des arcs correspondent aux valeurs des fonctions d'étiquetage sur ces noeuds et ces arcs. Ils modélisent les caractéristiques alphanumériques des informations géographiques.

Un graphe G(N, E, n_G, e_G, y_G) est noté, sauf cas exceptionnel, G(N, E) et un arc est noté (n_i,n_j) où n_i est son extrémité initiale et n_j son extrémité finale. Les noeuds sont identifiés par un attribut "nom" considéré comme un sous-ensemble de l'étiquette. Les arcs sont identifiés par un attribut "nom" et par leurs extrémités initiale et finale.

Dans cette partie, nous présentons les composants de base du modèle de graphe, à savoir les noeuds, les arcs et les réseaux. Ces composants sont présentés en utilisant le formalisme O₂ et une représentation graphique. Chacun de ces composants définit une classe d'objets.

Les exemples sont issus de l'exemple illustratif du chapitre I (représentant des villes et des voies routières entre les villes).

I-1.1 Les Noeuds

La classe Noeud est définie par son identifiant.

class Noeud

type tuple

(

nom : string

)

end;

Un noeud est utilisé pour modéliser une ville par exemple. Une ville possède des caractéristiques alphanumériques qui lui sont propres. Selon le type d'application souhaitée, des classes supplémentaires sont créées. Ces classes héritent de la classe Noeud et possèdent en plus des attributs modélisant leurs caractéristiques.

Par exemple, une ville possède une population, un coût moyen d'hôtel et une liste de monuments à visiter. La classe Ville est définie par l'agrégation de trois attributs représentant ces caractéristiques :

class Ville

inherit Noeud

type tuple

(

population : integer,

coût_moyen_hôtel : integer,

monuments : list (string)

)

end;
Représenter une ville (un noeud) dont le nom est "Paris" consiste à créer un objet de la classe Ville. Par définition, cette ville est également un élément de la classe Noeud. Ce noeud est représenté graphiquement dans la Figure II-1.

Figure II-1. Un noeud

I-1.2 Les Arcs

La classe Arc est définie par l'agrégation d'attributs représentant ses noeuds extrémités initiale et finale et son identifiant.

class Arc

type tuple

(

nom : string,

noeud_initial : Noeud,

noeud_final : Noeud

)

end;
Un arc est utilisé pour modéliser une voie de communication entre deux noeuds. Une telle voie possède des caractéristiques alphanumériques. Selon le type d'application souhaitée, des classes supplémentaires sont créées. Ces classes héritent de la classe Arc et possèdent en plus des attributs modélisant leurs caractéristiques.

Par exemple, une voie routière possède un type de transport (autoroute, nationale, départementale, chemin piétonnier), un coût de transport et une distance. La classe Route est définie par l'agrégation de trois attributs représentant ces caractéristiques :
class Route

inherit Arc

type tuple

(

type_transport : string,

coût_transport : integer,

distance : integer

)

end;
Représenter une voie de communication (un arc) entre Paris et Tours dont le nom est "A10" consiste à créer un objet de la classe Route. Par définition, cette voie de communication est également un élément de la classe Arc. Cet arc est représenté graphiquement dans la Figure II-2.

Figure II-2. Un arc

I-1.3 Les Réseaux

Le réseau est un concept qui s'appuie sur la notion de graphe. Un graphe représente un ensemble de noeuds et d'arcs. Un réseau est un graphe appliqué à l'information géographique. Il représente la couverture d'un lieu géographique (e.g., au niveau ferroviaire, routier, aqueux). Un réseau possède des caractéristiques particulières (type de réseau, nom du réseau) alors qu'un graphe ne possède aucune caractéristique. Un réseau est un objet géographique identifiable : le réseau routier français est très clairement identifié, de même que le réseau aérien mondial. Un réseau est donc exprimé par une classe (qui regroupe des objets), alors qu'un graphe est défini par un type (aucun objet n'est attaché à un graphe).

Définition : Soit N un ensemble finis de noeuds {n₁, ..., n_p}. Un hypergraphe sur N [11] est une famille H = {E₁, ..., E_k} de parties de N telle que :

E_i Ø (i = 1, ..., k)

E_i = N (i = 1, ..., k)
Définition : Un Réseau est un hypergraphe.
Puisque les définitions de noeud et d'arc sont maintenant utilisables, définissons le type graphe :

type graphe

tuple

(

noeuds : unique set (Noeud),

arcs : unique set (Arc)

)
La classe Réseau est définie par l'agrégation d'attributs représentant son identifiant et l’ensemble des noeuds et des arcs composant le réseau. Cet ensemble est assimilable à un graphe.

class Réseau

type tuple

(

nom : string,

graphe : graphe

)

end;

Un réseau est utilisé pour modéliser un réseau de communication. Un tel réseau possède des caractéristiques alphanumériques. Selon le type d'application souhaitée, des classes supplémentaires sont créées. Ces classes héritent de la classe Réseau et possèdent en plus des attributs modélisant leurs caractéristiques.

Un réseau routier possède, par exemple, un type de réseau (autoroutes, nationales, départementales), et une vitesse maximale autorisée. La classe Réseau_routier est définie par l'agrégation de deux attributs représentant ces caractéristiques.

class Réseau_routier

inherit Réseau

type tuple

(

type_réseau : string,

vitesse_maximale : integer

)

end;

Représenter un réseau de communication, dont le nom est "Voies routières" et comprenant trois arcs (Paris, Tours), (Tours, StPierre le Moûtier) et (StPierre le Moûtier, Lyon) respectivement de nom "A10", "N76" et "N7", consiste à créer un objet de la classe Réseau_routier. Par définition, ce réseau routier est également un élément de la classe Réseau. Ce réseau est représenté graphiquement dans la Figure II-3 par un hypergraphe.

Figure II-3. Un réseau

I-2. Le second niveau d'abstraction

La décomposition suivant plusieurs niveaux d'abstraction est un moyen naturel de structurer des données orientées réseau. Le modèle de graphe introduit un second niveau d'abstraction : le niveau des Master_noeuds et des Master_arcs. Cette notion d'abstraction va permettre de prendre en compte la notion de différents niveaux de détails dans un graphe.

Définissons tout d’abord la notion de sous-réseau. Un sous-réseau est un réseau pouvant être assimilé à un noeud ou à un arc à un niveau d’abstraction différent. Le noeud (resp. l’arc) représente l’abstraction de ce sous-réseau. Il est alors appelé master_noeud (resp. master_arc).
La Figure II-4 présente un graphe possédant un seul niveau d'abstraction. Un tel graphe est appelé un graphe plat. La Figure II-5 présente un graphe possédant plusieurs niveaux. Paris est maintenant considéré comme l'abstraction d'un sous-réseau. L'arc Paris-Tours est également considéré comme l'abstraction d'un sous-réseau.


Figure II-4. Graphe plat


Figure II-5. Graphe à plusieurs niveaux

I-2.1 Les Réseaux_associés

Les master_noeuds et les master_arcs représentent l'abstraction d'un sous-réseau. Les master_noeuds et master_arcs sont appelés des noeuds et arcs généralisés. Le sous-réseau est appelé un réseau_associé. La classe Réseau_associé est une sous-classe de la classe Réseau. Un réseau_associé se définit comme un graphe G(N,E). Les éléments de N sont appelés les noeuds spécialisés. Les éléments de E sont appelés les arcs spécialisés. Pour relier ce réseau aux différents niveaux d'abstraction, les concepts d'arcs_entrants et d'arcs_sortants à un réseau_associé sont définis.

Les arcs_entrants (resp. arcs_sortants) d'un réseau_associé à un master_noeud (n) représentent l'ensemble des arcs "arrivant sur" (resp. "quittant") le réseau_associé du master_noeud. Ces arcs n’appartiennent pas au réseau_associé. Les arcs_entrants et arcs_sortants pour le réseau_associé G(N,E) d'un master_noeud n sont définis dans la Figure II-6.

arcs_entrants = { (ni,nj) / ni Ï N Ù nj Î N } arcs_sortants = { (ni,nj) / ni Î N Ù nj Ï N }

Figure II-6. Définition des arcs_entrants et arcs_sortants d'un master_noeud
Les arcs_entrants (resp. arcs_sortants) d'un réseau_associé à un master_arc (e) représentent l'ensemble des arcs partant du noeud initial (resp. permettant d'atteindre le noeud final) du master_arc. Soit la fonction Extrémité_Initiale (resp. Extrémité_Finale) d'un master_arc (e) telle que Extrémité_Initiale(e) (resp. Extrémité_Finale(e)) retourne le noeud extrémité initiale (resp. finale) de l'arc e ou un noeud appartenant au réseau_associé de l’extrémité initiale (resp. finale) de l’arc e, si ce noeud est un master_noeud. Les arcs_entrants et arcs_sortants pour le réseau_associé G(N,E) d'un master_arc e sont définis dans la Figure II-7.

arcs_entrants = { (ni,nj) / ni = Extrémité_Initiale (ei) Ù nj Î N } arcs_sortants = { (ni,nj) / ni Î N Ù nj = Extrémité_Finale (ei) }

Figure II-7. Définition des arcs_entrants et arcs_sortants d'un master_arc
Dans la Figure II-5 précédente, l'arc A10 entre Pte d'Orléans et Orléans est un arc_sortant du réseau_associé au master_noeud Paris, et ce même arc est un arc_entrant du réseau_associé au master_arc A10 entre Paris et Tours (car Pte d’Orléans appartient au réseau_associé à Paris). La classe Réseau_associé est définie par l'agrégation de deux attributs (arcs_entrant, arcs_sortant) :

class Réseau_associé

inherit Réseau

type tuple

(

arcs_entrant : unique set (Arc),

arcs_sortant : unique set (Arc)

)

end;

I-2.2 Les Master_noeuds

La classe Master_noeud est une sous-classe de la classe Noeud. Notons qu'un master_noeud peut représenter l'abstraction de plusieurs réseaux_associés. La classe Master_noeud est définie par l'agrégation d'un attribut (réseaux_associés) :

class Master_noeud

inherit Noeud

type tuple

(

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

)

end;
Les noeuds appartenant au réseau_associé d’un master_noeud n sont appelés des noeuds fils du noeud n, ou encore des noeuds dépendants du noeud n. Les noeuds fils d'un master_noeud n sont aussi des noeuds spécialisés. La notion de filiation n'est applicable que dans le cas des noeuds spécialisés d'un noeud n, mais pas dans le cas des arcs spécialisés de ce noeud.

Un master_noeud (Paris) est représenté graphiquement dans la Figure II-8.


Figure II-8. Un master_noeud

I-2.3 Les Master_arcs

Une notion similaire au Master_noeud est définie pour les arcs. La classe Master_arc est une sous-classe de la classe Arc. A la différence des master_noeuds, un master_arc ne représente l'abstraction que d'un unique réseau_associé. La classe Master_arc est définie par l'agrégation d'un attribut (réseau_associé).

class Master_arc

inherit Arc

type tuple

(

réseau_associé : Réseau_associé

)

end;
Les arcs appartenant au réseau_associé d’un master_arc e sont appelés des arcs fils de l’arc e, ou encore des arcs dépendants de l’arc e. La notion de filiation est ici applicable entre un arc e et ses arcs spécialisés et non entre cet arc et ses noeuds spécialisés.

Un master_arc (l'arc (Paris,Tours) de nom A10) est représenté graphiquement dans la Figure II-9.


Figure II-9. Un master_arc

I-3. Conclusion

Ce modèle de données est bien adapté à la gestion de plusieurs niveaux d'abstraction (ou niveaux de détails). La différence principale entre les réseaux_associés d'un master_noeud et les réseaux_associés d'un master_arc réside dans l'ensemble des noeuds de ces réseaux_associés. Le noeud initial et le noeud final d'un master_arc appartiennent à l'ensemble des noeuds du réseau_associé à cet arc. La différence principale entre un master_noeud et un master_arc réside dans le nombre de réseaux_associés. Un master_noeud peut avoir plusieurs réseaux_associés. Un master_arc possède un unique réseau_associé. Cependant, plusieurs réseaux_associés peuvent être définis en utilisant plusieurs master_arcs entre les mêmes noeud initial et noeud final. La Figure II-10 présente le réseau de la Figure II-4 avec l'introduction de master_noeuds et de master_arcs.

Figure II-10. Un réseau contenant des master_noeuds et des master_arcs