Informatique

I-2. Définitions sur les graphes

Nous intéressant plus particulièrement aux SIG de type réseau, cette partie donne les définitions issues de la théorie des graphes [10, 36] utiles à la compréhension des parties et chapitres suivants.

Aucune coordonnée géographique n'est définie sur les éléments traités par la théorie des graphes : il ne s'agit ici que de représentations logiques.
Un graphe est visuellement représenté par un schéma constitué d'un ensemble (supposé fini) de points n₁,...,n_p et d'un ensemble de lignes (composées de plusieurs segments de droite) reliant chacun deux de ceux-ci et notés e₁,...,e_m.

Les points n₁,...,n_p sont appelés les sommets du graphe, les lignes e₁,...,e_m sont appelées les arcs du graphe.

Définition : Un graphe G = (N,E) est le couple constitué :

1/ par un ensemble N = {n₁,...,n_p}

2/ par une famille E = (e₁,...,e_m) d'éléments du produit cartésien :

N x N = {(n_i,n_j) | n_i Î N, n_j Î N}

Les éléments de N sont les sommets de G.

Les éléments de E sont les arcs de G.

Définition : Un graphe vide est un graphe dont l'ensemble des sommets est vide.
Dans tout ce qui suit, un ensemble vide sera noté Ø.
Définition : Soit e un arc de la forme (n_i, n_j).

Le sommet n_i est appelé extrémité initiale de e.

Le sommet n_j est appelé extrémité finale de e.
Définition : Un arc e de la forme (n,n), où n Î N, est appelé une boucle.


Figure I-7. Un graphe
Deux types de graphes existent : des graphes non-orientés et des graphes orientés. Un graphe non­­-orienté est un graphe ne possédant pas de notion de direction : chaque ligne (appelée arête) est une paire de sommets (notée [n_i,n_j] où n_i et n_j sont des sommets). Un graphe orienté est un graphe possédant cette notion de direction : chaque arc est une flèche partant d'un sommet initial et allant jusqu'à un sommet final. Dans un graphe orienté, chaque arc représente un couple de sommets (noté (n_i,n_j) où n_i et n_j sont des sommets) et non une paire de sommets. Un arc orienté (une flèche) ne peut se parcourir que dans un seul sens : depuis son extrémité initiale jusqu'à son extrémité finale. L'ensemble des graphes orientés n'est en fait qu'un sous-ensemble de l'ensemble des graphes non-orientés. Un graphe non-orienté est transformé en graphe orienté en dupliquant chaque arête et en les orientant de manière opposée.


Figure I-8. Graphe non-orienté


Figure I-9. Graphe orienté

Dans la suite de ce document, nous nous placerons dans le cadre des graphes orientés.

Définition : n_j (n_j Î N) est un successeur de n_i (n_i Î N) dans un graphe G s'il existe un arc de la forme (n_i,n_j).

L'ensemble des successeurs de n_i se note G⁺_G(n_i).

Définition : n_i est un prédécesseur de n_j dans un graphe G s'il existe un arc de la forme (n_i,n_j).

L'ensemble des prédécesseurs de n_j se note G^-_G(n_j).

Définition : L'ensemble des voisins de n_i dans le graphe G est : G_G(n_i) = G⁺_G(n_i) È G^-_G(n_i)
Définition : Soit un graphe G (N, E). Soit k le nombre de noeuds de G (k = |N|).

La matrice booléenne d'adjacence A_G est la matrice kxk telle que l'intersection entre la ligne i et la colonne j de A_G contienne "vrai" s'il existe un arc de n_i à n_j et "faux" sinon.

Cette intersection est notée : A(n_i, n_j).
Définition : Un p-graphe est un graphe G (N,E) où le nombre d'arcs (n_i,n_j) entre deux sommets n_i et n_j de N ne peut excéder p.
Définition : Un graphe simple est un graphe G (N,E) où :

1/ Il n'y a pas de boucle

2/ Entre deux sommets n_i et n_j de N, il n'y a jamais plus d'un arc pour les relier.
Un graphe simple est donc un 1-graphe sans boucle.


Figure I-10. Graphe simple et graphe non simple
Une des applications principales de la modélisation des informations géographiques par des graphes dans les SIG est l'évaluation de chemins. Dans le cadre d'un graphe orienté ou non orienté, une évaluation de chemin consiste à trouver une "chaîne" permettant de joindre deux sommets. Ramené au cas des graphes orientés, cette chaîne est alors appelé "chemin".

Définition : Une chaîne de longueur q>0 est une séquence m = (e₁,...,e_i,...,e_q) d'arcs d'un graphe G telle que chaque arc de la séquence ait une extrémité en commun avec l'arc suivant, et l'autre extrémité en commun avec l'arc précédent. Trois cas peuvent être distingués :

- q = 1 :

la chaîne possède un seul arc e₁(n₁,n₂);

- q = 2 :

la chaîne possède deux arcs e₁ (n₁,n₂) et e₂ (n₃,n₄) tels que par exemple n₁ = n₃.

- q > 2 :

chaque arc e_i(n_i1,n_i2) de la chaîne (1i+1(n_i3,n_i4) suivant et l'autre extrémité en commun avec l'arc e_i-1(n_i5,n_i6) précédent (par exemple, n_i1=n_i3 et n_i2=n_i5).
Le nombre d'arcs de la séquence est la longueur de la chaîne m.

Une chaîne qui ne rencontre pas deux fois le même sommet est dite élémentaire.

Une chaîne qui n'utilise pas deux fois le même arc est dite simple.


Figure I-11. Chaînes simples et élémentaires
Définition : Un chemin de longueur q>0 est une chaîne m = (e₁,...,e_i,...,e_q) où pour tout arc e_i (avec 0i, n_j), n_j coïncide avec l'extrémité initiale de e_i+1.

Dans le cas d'un 1-graphe, un chemin est déterminé complètement par la succession des sommets n₁,...,n_k qu'il rencontre, et le chemin est noté indifféremment :

m = ((n₁,n₂),(n₂,n₃)...)

= [n₁,n₂,...,n_k]

Les graphes peuvent être cycliques ou acycliques.
Définition : Un cycle est une chaîne m = (e₁,...,e_q) telle que :

1/ Le même arc ne figure pas deux fois dans la séquence.

2/ Les deux sommets aux extrémités de la chaîne coïncident.


Figure I-12. Cycles
Définition : Un graphe acyclique est un graphe ne possédant aucun cycle.

Un graphe cyclique est un graphe possédant au moins un cycle.

Les graphes peuvent être planaires ou non-planaires.
Définition : Un graphe G est planaire s'il est possible de le représenter sur un plan de sorte que les sommets soient représentés graphiquement par des points distincts, les arcs par des segments de courbe, et que deux arcs ne se croisent pas en-dehors de leurs extrémités.


Figure I-13. Graphe non-planaire


Figure I-14. Graphe planaire
Ces définitions seront appliqués à l'étude des Systèmes d'Informations Géographiques de type réseau.
Les algorithmes les plus classiques de recherche d'un chemin entre un sommet de départ n_d et un sommet d'arrivée n_a consistent, à partir du sommet n_d du graphe et à numéroter positivement ou négativement tous les arcs rencontrés selon qu'ils sont parcourus dans le sens normal (c'est-à-dire de leur extrémité initiale vers leur extrémité finale) ou qu'ils sont "remontés" (de l'extrémité finale vers l'extrémité initiale). Lorsque le sommet n_a est rencontré, la succession des arcs numérotés positivement constitue un chemin de n_d à n_a. Les algorithmes de recherche de chemins entre deux sommets peuvent ne pas tenir compte de valuation possible sur les arcs ou les sommets, ou tenir compte d'une valuation positive ou nulle sur les arcs et rechercher un chemin avec évaluation d'une fonction de coût (algorithme de Dijkstra [47]). Ils peuvent également tenir compte d'une valuation quelconque sur les arcs (algorithme de Ford-Bellman [47]).

Nous présentons les algorithmes sans évaluation de fonction de coût, par l'examen d'un algorithme classique, puis les algorithmes avec évaluation de coût dans le cas où les valuations sont positives (cas le plus fréquent pour des réseaux de transport) par l'examen de l'algorithme de Dijkstra.

Algorithme :
Soit un graphe G (N,E) sans boucle modélisé par sa matrice d'adjacence booléenne A_G. G possède k noeuds (|N| = k).

L'algorithme en pseudo-code suivant évalue le chemin d'un sommet d'origine à un sommet destination. Le résultat est un graphe "Résultat" résultant de la fonction de recherche Eval_chemin (origine, destination, Résultat).

L'initialisation se fait en appelant Eval_chemin (sommet_d'origine, sommet_de_destination, G(Ø,Ø)).

Arc(n_i, n_j) est une fonction qui renvoie, lorsqu'il en existe, un des arcs existant entre n_i et n_j (cette fonction peut renvoyer un arc indifféremment car il n'existe aucune valuation sur les arcs). Cette fonction gère le caractère multi-graphe d'un graphe et renvoie toujours le même arc lorsqu'il existe plusieurs arcs entre deux sommets.

Union (È) est une fonction ensembliste réalisant l'union entre deux ensembles (de sommets ou d'arcs).
Eval_chemin (origine, destination, Chemin (N_C, E_C))

Si origine = destination Alors

N_C = N_C È {destination};

Afficher Chemin (N_C, E_C)

Sinon

Pour i = 1 à k Faire

Si A_G (origine, n_i) = Vrai et n_i Ï N_C Alors

Eval_chemin (n_i, destination,

Chemin (N_C È {origine},E_C È {Arc (origine, n_i)}) )

Fsi

Fpour

Fsi

Figure I-15. Exemple illustratif d'un algorithme de recherche de chemin
Les SIG logiques de type réseau modélisent les informations géographiques sous forme d'un graphe. Un graphe contient deux types d'objets fondamentaux : des sommets et des arcs. Pour un SIG logique de type réseau, un graphe modélise le caractère topologique d'un ensemble d'informations géographiques, c'est-à-dire la connectivité de ces informations entre elles. Un graphe modélisera par exemple le réseau routier français. Il comportera alors des sommets représentant les villes, et des arcs représentant les voies routières entre ces sommets.

A chacun des sommets et arcs peuvent être associées des valeurs alphanumériques. Ces valeurs représentent alors les propriétés non-localisées des informations géographiques. Un sommet pourra, par exemple, représenter l'information géographique "ville". Il lui sera alors associé des valeurs alphanumériques comme "population", "coût moyen d'un hôtel", "monuments à visiter". De la même manière, à un arc représentant l'information géographique "voie routière" seront associées les valeurs alphanumériques "distance", "type de transport", "coût de transport".

Cette précision nous conduit à étendre la notion de définition d'un graphe.
Une fonction d'étiquetage est définie pour les sommets et les arcs d'un graphe [20]. Cette fonction fait correspondre à chaque sommet (resp. arc) du graphe un ensemble de valeurs (un label) définies dans un domaine précis. Une fonction d'incidence permet d'identifier les arcs de labels différents pouvant exister entre deux mêmes sommets.

Définition : Soit un graphe G = (N,E).

Soient D_i = {d_i1, d_i2,....} des ensembles de constantes représentant un domaine de définition pour chacune des caractéristiques alphanumériques des sommets ou arcs du graphe.

Soit n_p le nombre de caractéristiques alphanumériques d'un sommet, et soit e_l le nombre de caractéristiques alphanumériques d'un arc.

La fonction d'étiquetage n_G des sommets est définie comme suit :

n_G : N -> I_n où I_n = D_n1 x D_n2 x...x D_np

La fonction d'étiquetage e_G des arcs est définie comme suit :

e_G : E -> I_e où I_e = D_e1 x D_e2 x...x D_el

La fonction d'incidence, notée y_G, est définie comme suit :

y_G : E -> N x N

Le graphe G peut alors être défini par G(N, E, n_G, e_G, y_G).

Dans la suite de ce document, un graphe sera de la forme G(N, E, n_G, e_G, y_G).
Ces fonctions d'étiquetage et cette fonction d'incidence vont permettre de poser des requêtes à un graphe modélisant un ensemble d'informations géographiques.
Pour des bases de données spatiales contenant un volume de données important et dont chacune des données est caractérisée par des valeurs alphanumériques, le problème n'est pas tant la recherche de chemin, mais la recherche de chemin sous contraintes (une contrainte représentant un ensemble de conditions sur les valeurs alphanumériques des sommets et/ou des arcs).

Pour réaliser cette recherche, les SIG utilisent non pas des algorithmes de recherche de chemin comme le précédent, mais plutôt des algorithmes de recherche du plus court chemin sous contraintes, comme l'algorithme de Dijkstra défini ci-après. Nous prenons comme exemple, pour illustrer le déroulement de cet algorithme, une contrainte de temps minimum.

Algorithme de Dijkstra :
Cet algorithme est basé sur une fonction de coût réévaluée à chaque nouveau sommet du graphe. Cette fonction de coût correspond à une fonction de temps minimum.
Considérons sur le graphe G(N, E, n_G, e_G, y_G) le sommet de départ n_d, le sommet d'arrivée n_a, et déterminons pour tout sommet n_i un nombre t(n_i) qui sera le "temps minimum d'arrivée en n_i". Chaque arc e entre le sommet n_i et le sommet n_j est valué par un temps : l_ij = e_G(e)

Deux ensembles sont définis : l'ensemble S des sommets définitivement marqués pour lesquels le temps d'atteinte minimum est parfaitement défini et ne variera plus, et l'ensemble S₁ des sommets non encore définitivement marqués et pour lesquels le temps minimum d'arrivée en ce sommet peut encore varier. S₁ est le complémentaire de S dans l'ensemble N des sommets.

La fonction p est la fonction "prédécesseur". Elle permet de déterminer pour chaque sommet à partir de quel précédent sommet a-t-il été atteint. Lorsque la fonction p, pour un sommet n_i, est positive, cela signifie que ce sommet appartient à l'ensemble S et que son temps d'atteinte minimum est donc déterminé.

La recherche du chemin s'effectue par étapes. A l'initialisation, les fonctions et ensembles sont définis par : t(n_d) = 0, et t(n_i) = +_¥ (" n_i n_d)

p(n_d) = - n_d, et p(n_i) = -_¥ (" n_i n_d)

S₁ = {n_d,n₁,n₂,...,n_a}

S = Ø
Algorithme :
Tant que S₁ Ø Faire

Pour tout k Î S₁ Faire

Si t(k) = Min _{(i Î S1)} {t(i)} Alors

j = k

Fsi

Fpour

Si t(j) < + Alors

Pour tout n_i Î S₁ G⁺_G(j) Faire

z = t(j) + lji;

Si z < t(n_i) Alors

t(n_i) = z;

p(n_i) = -j;

Fsi

Fpour

S₁ = S₁ - {j};

p(j) = -p(j);

Fsi

Ftantque

Lorsque l'algorithme s'arrête, le plus court chemin de n_d à n_a a été trouvé. Le temps de traversée total de ce chemin est la valeur de t(n_a). Les sommets du chemin sont retrouvés en suivant dans l'ordre inverse les valeurs des p(n_i) (en partant de p(n_a) et en remontant jusqu'à trouver un sommet n_i où p(n_i) = n_d).


Figure I-16. Exemple illustratif de l'algorithme de Dijkstra
Les entités géographiques représentant des réseaux de transport évoluent dans un monde en trois dimensions [40]. Nous limiterons notre étude à la modélisation d'informations en deux dimensions. Compte tenu de la sémantique et de la complexité des informations modélisées (routes utilisant des ponts ou des tunnels,...), la probabilité d'obtenir une représentation planaire en deux dimensions de tels réseaux est très faible. Dans la pratique, les réseaux de transport (routiers, aériens, gazeux, ferroviaires, électriques, aqueux...) sont modélisés par des graphes orientés, non planaires avec cycles [40].

Les graphes modélisés dans la suite de cette étude seront orientés et sans boucle. Il n'est défini aucune contrainte concernant les propriétés cycliques/acycliques et planaires/non planaires de ces graphes.

I-3. Requêtes pour les SIG de type réseau

Les SIG de type réseau modélisent les informations géographiques sous forme d'un graphe. Ce graphe modélise le caractère topologique d'un ensemble d'informations géographiques, mais contient aussi les propriétés non-localisées de ces informations. Le SIG de type réseau doit permettre d'effectuer des recherches d'informations sur ce graphe. Ces recherches se matérialisent pour l'utilisateur par le fait de poser une "requête" au SIG.

Aucun outil formel de définition du pouvoir d'expression pour ce type de SIG n'a actuellement été défini. Nous utiliserons donc une approche empirique en définissant une série de requêtes comme mesure du pouvoir d'expression (à l'image de [13]). Ces requêtes se classent en trois parties : les requêtes concernant la recherche de chemin, les requêtes concernant l'augmentation des détails dans le chemin, et les requêtes connexes à la recherche de chemins.

I-3.1 Recherche de chemins

Les requêtes concernant la recherche de chemins calculent une fermeture transitive sans cycle d'un sommet à un autre d'un graphe. Ces requêtes sont essentielles pour des SIG de type réseau. Sur chaque chemin recherché, des conditions peuvent être définies sur les propriétés alphanumériques des entités géographiques modélisées par des sommets et des arcs dans le graphe. Une condition peut porter sur les propriétés alphanumériques de chaque sommet et/ou arc du graphe (critères) ou sur les propriétés d'un ensemble de sommets et/ou d'arcs (contraintes agrégatives). Elle peut également imposer un ordre dans la vérification des conditions sur les sommets et/ou les arcs (contraintes régulières). Dans tous les cas, la vérification d'une condition est une fonction booléenne appliquée sur un graphe (éventuellement réduit à un arc ou un sommet) qui indique si cette condition est vérifiée ou non pour ce graphe.

Définition : Un critère porte sur un ensemble d'objets (sommets et/ou arcs) et vérifie pour chaque objet, indépendamment des autres objets de l'ensemble, son exactitude vis-à-vis d'une condition.

Un critère va tester pour chaque sommet et/ou arc du graphe les valeurs de la fonction d'étiquetage définie sur ce sommet et/ou cet arc.

Un critère sur une recherche de chemins est par exemple :

"Aller de Paris à Lyon en ne passant que par des villes de plus de 100000 habitants et en utilisant uniquement des autoroutes et des routes nationales".

Définition : Une contrainte agrégative est une contrainte portant sur un ensemble de sommets et/ou d'arcs et nécessitant le calcul d'une fonction agrégative (somme, moyenne, minimum, maximum, cardinalité) sur les valeurs de la fonction d'étiquetage pour cet ensemble de sommets et/ou d'arcs. Les sommets et/ou arcs doivent donc être considérés dans leur ensemble et non plus indépendamment les uns des autres.
Une contrainte agrégative sur une recherche de chemins est par exemple :

"Aller de Paris à Lyon avec un coût de voyage minimum (coût de trajet et coût d'hôtel)".

Définition : Une contrainte régulière est une contrainte portant sur un ensemble de sommets et/ou d'arcs et pouvant être exprimée sous forme d'une expression régulière sur les valeurs d'étiquetage de ces sommets et/ou de ces arcs.

Une contrainte régulière sur une recherche de chemins est par exemple :

"Aller de Paris à Lyon en utilisant des autoroutes jusqu'à Blois, puis des routes nationales de Blois à Lyon".
Notons qu’un critère peut également s’exprimer sous la forme d’une expression régulière. Par contre, une contrainte régulière permet d’exprimer une notion de succession d’actions ("Aller de Paris à Lyon en utilisant des autoroutes jusqu’à Blois, puis des routes nationales de Blois à Lyon"). Notre but en différenciant ces deux ensembles est d'étudier plus particulièrement la notion de succession dans les contraintes régulières.
Définition : Soit S un alphabet de la forme (a,...,z,A,...,Z,0,...9), et S* l'ensemble des mots de la forme {(a|...|z|A|...|Z|_|.| |0|...|9)⁺ (-) (a|...|z|A|...|Z|_|.| |0|...|9)⁺}.

C est l'ensemble des expressions de la forme {(somme | moyenne | min | max | nombre) (a|...|z|A|...|Z|_|.| |0|...|9)⁺ (=|>|<|¹|³|£) (a|...|z|A|...|Z|_|.| |0|...|9)⁺ }.

Les sommets et les arcs sont étiquetés. E devient alors un sous-ensemble du produit cartésien S*xNxN, où S* représente l'identifiant (l’étiquette) de l’arc.

Pour chacun de critères précédents (resp. contraintes précédentes), trois classes différentes peuvent être envisagées : des critères (resp. contraintes) sur les sommets seuls, des critères (resp. contraintes) sur les arcs seuls, et des critères (resp. contraintes) sur les sommets et les arcs ensembles. L'évaluation de ces critères (resp. contraintes) correspond à l'application d'une fonction booléenne sur les sommets et/ou les arcs. C représente une condition définie sur les étiquettes des sommets et des arcs.

Trois classes de critères possibles sont définies par les fonctions suivantes :

pour les sommets seuls : C_n : N x C -> Booléen

pour les arcs seuls : Ce : E x C -> Booléen

pour les sommets et les arcs : C_ne : N x E x C -> Booléen

où N (resp. E) est réduit à un seul sommet (resp. arc).
Les contraintes se définissent non plus sur des éléments isolés (des sommets et/ou des arcs), mais sur des ensembles.

Trois classes de contraintes agrégatives possibles sont définies par les fonctions suivantes :

pour les sommets : CA_n : N x C -> Booléen

pour les arcs : CA_e : E x C -> Booléen

pour les sommets et les arcs : CA_ne : N x E x C -> Booléen

Trois classes de contraintes régulières possibles sont définies par les fonctions suivantes :

pour les sommets : CR_n : N x C -> Booléen

pour les arcs : CR_e : E x C -> Booléen

pour les sommets et les arcs : CR_ne : N x E x C -> Booléen

Chacune de ces classes de critères et contraintes sera illustrée par une requête. La série de ces requêtes présente le support d'évaluation du pouvoir d'expression d'un SIG de type réseau sur la recherche de chemin.

Les types de requêtes	Sommets	Arcs	Sommets et Arcs
Critères	R1	R2	R3
Contraintes Régulières	R7	R8	R9

R₁: "Aller de Paris à Lyon en ne passant que par des villes de plus de 100000 habitants".

R₂: "Aller de Paris à Lyon en utilisant uniquement des routes nationales et des autoroutes".

R₃: "Aller de Paris à Lyon en ne passant que par des villes de plus de 100000 habitants et en utilisant uniquement des routes nationales et des autoroutes".

R₄: "Aller de Paris à Lyon avec un coût d'hôtel moyen inférieur à 100F".

R₅: "Aller de Paris à Lyon avec un coût de trajet moyen inférieur à 200F".

R₆: "Aller de Paris à Lyon avec un coût de voyage moyen (coût de trajet et coût d'hôtel) inférieur à 300F".

R₇: "Aller de Paris à Lyon en passant par Blois puis par StPierre le Moûtier".

R₈: "Aller de Paris à Lyon en utilisant des autoroutes puis des routes nationales".

R₉: "Aller de Paris à Lyon en utilisant des autoroutes jusqu'à Blois, puis des routes nationales de Blois à Lyon".

Une recherche de chemins va s'effectuer en appliquant un opérateur entre deux ensembles de sommets, sur un graphe, avec des critères et/ou contraintes définies sur le chemin à rechercher.

Les ensembles de sommets sont issus d'opérations de recherche de sommets vérifiant un critère. Ces ensembles peuvent donc être vides bien qu'ils ne puissent être vides en même temps [2]. Ceci permet de définir deux requêtes supplémentaires :

R₁₀: "Quelles villes de plus de 100000 habitants peut-on atteindre par des routes nationales depuis Paris ?".

R₁₁: "De quelles villes de plus de 100000 habitants peut-on partir pour atteindre Lyon par des routes nationales ?".

I-3.2 Augmentation des détails

L'utilisateur d'un SIG a souvent besoin de visualiser des informations géographiques à différents niveaux de détails. Cherchant un chemin de Paris à Lyon, par exemple, dans un premier temps, il veut pouvoir avoir une vue globale de son chemin. Ceci ne peut se faire qu'à un haut niveau d'abstraction. Ensuite, sachant que son chemin passe par Blois, il veut regarder plus en détail le chemin à l'intérieur de Blois. Il a donc besoin de plus de précisions sur Blois, ce qui correspond à un niveau d'abstraction plus faible. Ces requêtes ont pour but d'obtenir plus ou moins de détails sur un chemin donné.

Une requête d'augmentation des détails s'applique sur un graphe. Une telle requête résulte donc de l'application d'opérateurs sur un ensemble de sommets (éventuellement réduit à un unique sommet), ou sur un ensemble d'arcs (éventuellement réduit à un unique arc). Deux ensembles d'opérateurs peuvent être définis : des opérateurs permettant d'augmenter les détails dans un graphe et des opérateurs permettant de diminuer le nombre de détails dans un graphe.
Trois types d'opérateurs permettant d'augmenter les détails d'un graphe sont définis de la façon suivante :

pour les sommets :

A_n : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')

pour les arcs :

A_e : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')

pour les sommets et les arcs :

A_ne : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')
Trois types d'opérateurs permettant de diminuer les détails d'un graphe sont définis de la façon suivante :

pour les sommets :

D_n : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')

pour les arcs :

De : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')

pour les sommets et les arcs :

D_ne : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')
Pour ces opérateurs, le graphe G₁(N₁,E₁,n_G1,e_G1,y_G1) contient les sommets et/ou arcs sur lesquels l'utilisateur souhaite obtenir plus ou moins de détails.

Chacun de ces opérateurs sera illustré par une requête. La série de ces requêtes présente le support d'évaluation du pouvoir d'expression d'un SIG de type réseau sur l'augmentation ou la diminution des détails d'un chemin.

Les types de requêtes	Sommets	Arcs	Sommets et Arcs
Augmentation des détails	D1	D2	D3
Diminution des détails	D4	D5	D6

D₁: "Détailler Blois dans le chemin de Paris à Lyon, pour visualiser le chemin employé à l'intérieur de Blois".

D₂: "Détailler l'arc entre Fontainebleau et Tours dans le chemin de Paris à Lyon, pour visualiser le chemin employé entre Fontainebleau et Tours".

D₃: "Détailler l'ensemble du chemin de Paris à Lyon".

D₄: "Enlever les détails correspondant à Blois dans le chemin de Paris à Lyon".

D₅: "Enlever les détails correspondant à l'arc entre Fontainebleau et Tours dans le chemin de Paris à Lyon".

D₆: "Enlever les détails correspondant aux noeuds et arcs du chemin de Paris à Lyon".

I-3.3 Requêtes connexes

Les requêtes connexes à la recherche de chemin regroupent toutes les requêtes qui peuvent être posées sur le chemin résultant d'une recherche de chemin (sélection de sommets et/ou d'arcs, inclusion et intersection d'ensembles de sommets et/ou d'arcs). Un chemin est modélisé par un graphe. Lors de l'utilisation d'un SIG de type réseau, l'utilisateur peut poser d'autres requêtes que des requêtes sur les chemins ou des requêtes d'augmentation de détails. Il peut par exemple demander les sommets modélisant des villes de plus de 100000 habitants, dans un chemin donné, ou imposer que son chemin passe par ces villes. Ces requêtes s'apparentent aux requêtes des Systèmes de Gestion de Bases de Données classiques (e.g. sélection de tuples dans une relation) et aux requêtes de la théorie des ensembles (e.g. sélection de sommets dans un ensemble de sommets).

Nous pouvons distinguer trois ensembles d'opérateurs permettant de réaliser des requêtes connexes à la recherche de chemins.

Le premier ensemble d'opérateurs permet de sélectionner des sommets (resp. arcs) particuliers d'un graphe. Ces sommets (resp. arcs) doivent répondre à un critère de recherche similaire au critère défini pour la fonction C_n (resp. C_e). Cette recherche correspond à une sélection de type relationnel. Deux types d'opérateurs permettent de sélectionner des éléments constitutifs d'un graphe (sommets ou arcs). Ils sont définis de la façon suivante :

pour les sommets :

s_n : G(N,E,n_G,e_G,y_G) x C -> G'(N',E',n_G',e_G',y_G')

où E' = Ø

pour les arcs :

s_e : G(N,E,n_G,e_G,y_G) x C -> G'(N',E',n_G',e_G',y_G')

Le second ensemble d'opérateurs permet de vérifier si un ensemble de sommets (resp. arcs) est bien inclus dans un autre ensemble de sommets (resp. arcs). Ces opérateurs correspondent à des opérateurs d'inclusion ensembliste. Deux types d'opérateurs permettent de réaliser des inclusions d'ensembles de sommets ou d'arcs. Ils sont définis de la façon suivante :

pour les sommets :

Ì_n : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')

pour les arcs :

Ì_e : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')

Les sommets et arcs de G' correspondent aux sommets et arcs de G₁ si l'inclusion de sommets (resp. arcs) est vérifiée. Dans le cas contraire, N' et E' correspondent à des ensembles vides.
Le troisième ensemble d'opérateurs permet de trouver l'intersection entre deux ensembles de sommets (resp. arcs). Ces opérateurs correspondent à des opérateurs d'intersection ensembliste. Deux types d'opérateurs permettant de réaliser l'intersection entre deux ensembles de noeuds ou d'arcs. Ils sont définis de la façon suivante :

pour les sommets :

_n : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')

où E' = Ø

pour les arcs :

_e : G₁(N₁,E₁,n_G1,e_G1,y_G1) x G(N,E,n_G,e_G,y_G) -> G'(N',E',n_G',e_G',y_G')

Chacun de ces opérateurs sera illustré par une requête. La série de ces requêtes présente le support d'évaluation du pouvoir d'expression d'un SIG de type réseau sur les requêtes connexes à la recherche d'un chemin.

Les types de requêtes	Sommets	Arcs
Sélection	C1	C2
Intersection	C5	C6

C₁: "Quelles sont les plus grandes villes touristiques françaises (population > 100000) ?".

C₂: "Quelles sont les autoroutes dont le coût de trajet est très cher (coût > 10 F/km) ?".

C₃: "Les villes traversées lors du chemin de Paris à Lyon sont-elles parmi les plus grandes villes touristiques françaises ?".

C₄: "Les voies de communication empruntées lors du chemin de Paris à Lyon sont-elles parmi les autoroutes les plus chères ?".

C₅: "Quelles sont les villes traversées lors du chemin de Paris à Lyon qui sont parmi les plus grandes villes touristiques françaises ?".

C₆: "Quelles sont les voies de communication empruntées lors du chemin de Paris à Lyon qui sont parmi les autoroutes les plus chères ?".

I-3.4 Exemple de référence

Cet exemple va servir de base de données de référence pour l'étude des SIG de type réseau. Ces données sont organisées sous forme d'un graphe comprenant des sommets et des arcs.

Les sommets modélisent des villes. Ces villes possèdent un nom, une population, un ensemble de monuments à visiter et un coût moyen d'hôtel. Une ville est définie comme une ville touristique si l'ensemble de ses monuments à visiter n'est pas vide.

Les arcs modélisent des voies de communication routière. Ces arcs possèdent un nom, un type de transport (autoroute, départementale, nationale, voie de bus...), un coût de transport et une distance.

Figure I-17. Graphe de référence

nom	population	monuments	coût_moyen_hôtel
Paris	4000000	{Tour_Eiffel, Arc_Triomphe}	200
Lyon	1000000	{Hôtel_ville}	150

Figure I-18. Labels des sommets

nom	type_transport	coût_transport	distance
Paris-Blois par A10	Autoroute	70	170
Tours-Lyon par N76	Nationale	60	350

Figure I-19. Labels des arcs