Performances de l'algorithme 2-BFS - isima.fr · Remerciements A l’issue de notre projet de fin d’études, nous tenons à remercier chaleureusement Monsieur Christian LAFOREST,

Institut Supérieur D’Informatique de Modélisation et de Leurs Applications

BP 10125 63173 Aubière Cedex

Rapport de projet de troisième année ISIMAFilière calcul et modélisation scientifiques

Travail réalisé par : Merième BELLARBI et Rachid JARRAY

Encadrant : Mr Christian LAFORESTResponsable de filière : Mr Vincent BARRA

Lieu du projet : ISIMADurée : 100 heures

Performances de l'algorithme 2-BFS

Etude et Implémentation d'un algorithme permettant de calculer le diamètre

d’un graphe

Institut Supérieur D’Informatique de Modélisation et de Leurs Applications

BP 10125 63173 Aubière Cedex

Rapport de projet de troisième année ISIMAFilière calcul et modélisation scientifiques

Travail réalisé par : Merième BELLARBI et Rachid JARRAY

Encadrant : Mr Christian LAFORESTResponsable de filière : Mr Vincent BARRA

Lieu du projet : ISIMADurée : 100 heures

Performances de l'algorithme 2-BFS

Etude et Implémentation d'un algorithme permettant de calculer le diamètre

d’un graphe

Remerciements

A l’issue de notre projet de fin d’études, nous tenons à remercier chaleureusement

Monsieur Christian LAFOREST, notre tuteur, pour sa disponibilité et son encadrement. Tout au long

de l’année universitaire, il nous a prodigué les conseils nécessaires pour l’aboutissement de notre

projet et nous a orientés afin que nous puissions prendre les meilleures décisions étape du projet.

Nous remercions également Monsieur LAVEDRINE, qui a répondu avec gentillesse à nos

sollicitations pour la mise en œuvre de tests statistiques malgré son emploi du temps chargé.

Résumé

Notre projet de fin d’études s’intitule « Performances de l’algorithme du 2-BFS ». Nous

avons étudié l’algorithme à l’ISIMA et nous étions encadrés par Mr. Christian LAFOREST, professeur

au LIMOS (Clermont-Ferrand, France).

Ce projet fait partie d’une étude nationale sur les graphes de grande taille. En effet, les

graphes ont plusieurs applications pratiques en informatique. Ils sont essentiellement utilisés pour

modéliser des réseaux de transports, des réseaux de communications …etc. Par conséquent, les

ingénieurs ont très souvent besoin de connaître certains paramètres des graphes tels que le

diamètre. Cependant, les algorithmes qui mesurent le diamètre d’un graphe, ont un temps

d’exécution très important. L’algorithme du 2-BFS propose une alternative intéressante pour les

programmeurs, car il propose une estimation du diamètre tout en réduisant le temps d’exécution.

Notre objectif est de tester la pertinence du 2-BFS afin de conclure sur son utilisation dans des

modèles réels.

Nous allons dans cette optique implémenter l’algorithme en C++ et en Matlab, puis nous allons

répondre aux questions ci-dessous :

- L’algorithme retourne t-il souvent le diamètre exact?

- Quelle est la marge d’erreur maximale du 2-BFS ?

- Peut-on faire confiance aux résultats proposés par le 2-BFS?

Abstract

Our third year project is entitled « 2-BFS algorithm performance ». We carried out the study of this

algorithm in ISIMA and we were supervised by Mr. Christian LAFOREST, professor at LIMOS

(Clermont-Ferrand, FRANCE).

This project was suggested as a part of a national study about large graphs. In fact, graphs have

many practical applications, in many computer science sub-fields. They are used to model

communication network, rapid transit, social network …etc. Thus, we often need to know the exact

value of some graph parameters such as the diameter. However, algorithms which measure the

exact diameter take too long. The 2-BFS algorithm produces an estimate of the exact graph

diameter, and the aim of our project is to evaluate the computational efficiency since the cost of

executing algorithms is a central problem in computer science.

We were asked to implement in Matlab and C++ the 2-BFS algorithm to compute its validity bounds

in order to answer the questions below:

- How often does the algorithm return the exact diameter?

- What are the worst case error bounds for 2-BFS computations?

- Can we trust the results displayed by the 2-BFS algorithm?

Table des figures

Figure 1 Présentation des différentes tâches.................................................................................4Figure 2: Exemple de graphe connexe...........................................................................................6Figure 3: Calcul de la distance.......................................................................................................7Figure 4 Algorithme de principe du BFS.........................................................................................9Figure 5 Algorithme de principe du diamètre exact.....................................................................10Figure 6: Présentation des évolutions des temps d'exécutions des deux algorithmes pour des Graphes de Erdos Reyni (de probabilité égale à 0.3)....................................................................11Figure 7 Algorithme de principe du 2-BFS....................................................................................12Figure 8 Simulation du premier BFS sur cas simple......................................................................12Figure 9 Simulation du second BFS sur un cas simple...................................................................13Figure 10 Simulation du 2-BFS sur un graphe qui retourne le bon résultat...................................15Figure 11Simulation du 2-BFS sur un graphe avec retour d'un résultat erroné.............................15Figure 12 Simulation du 2-BFS sur un chemin..............................................................................16Figure 13 simulation du 2-BFS sur une étoile (départ du centre)..................................................17Figure 14 simulation du 2-BFS sur une étoile (départ d'une extrémité)........................................17Figure 15 simulation du 2-BFS sur une grille................................................................................18Figure 16 Simulation du 2-BFS sur un graphe complet.................................................................19Figure 17 Schématisation de la structure utilisée pour stocker les résultats.................................20Figure 18 Graphe utilisé pour illustrer la structure.......................................................................21Figure 19: Tableau contenant tous les sommets échos dans le cas d'un graphe simple................21Figure 20: Tableau contenant l'ensemble des excentricités pour un exemple..............................21Figure 21 Graphe complet privé d'une arête................................................................................22Figure 22 graphe complet privé d'une arête................................................................................23Figure 23 Cas où le 2-BFS retourne 1...........................................................................................23Figure 24 Cas où le 2-BFS retourne la valeur 2.............................................................................24Figure 25: Copies d'écran présentant quelques résultats du calcul de l'espérance.......................25Figure 26: Copies d'écrans d'exécutions de l'algorithme pour des arbres de taille variant de 50 à 100 26Figure 27 Schéma pour illustrer un chemin de diamètre égal au diamètre exact..........................27Figure 28: Courbe présentant le rapport entre le diamètre exact et l'espérance des valeurs retournés avec un pas de 10........................................................................................................29 Figure 29: Illustration de quelques valeurs statistiques dans le cas où le graphe est dense......30Figure 30: Illustration de la différence entre diamètre exacte et valeur de l'algorithme..............31Figure 31 Evolution de la probabilité d'obtenir un résultat inexact en fonction du nombre d'arêtes pour un nombre de sommets égale à 40......................................................................................32

Table des matières

Remerciements…………………………………………………………………………………………Résumé/Abstract…………………………………………………………………………….................Table des figures…………………………………………………………………………….................. Table des matières.......................................................................................................................7 Introduction.................................................................................................................................11 Présentation du projet...............................................................................................................2

1.1 Contexte.......................................................................................................................................21.2 Travail demandé...........................................................................................................................21.3 Organisation du travail.................................................................................................................5

2 Eléments de la théorie des graphes............................................................................................62.1 Premières définitions...................................................................................................................6

2.1.1 Définition (Graphe)...............................................................................................................62.1.2 Définition (Graphe connexe)................................................................................................62.1.3 Définition (Matrice d’adjacence)..........................................................................................62.1.4 Définition (Distance)............................................................................................................72.1.5 Définition (Excentricité).......................................................................................................82.1.6 Définition (Diamètre)............................................................................................................82.1.7 Définition (Rayon)................................................................................................................9

2.2 Exploration des sommets d’un graphe.........................................................................................92.3 Algorithme de calcul du diamètre exact d’un graphe................................................................102.4 L’algorithme du 2-BFS..............................................................................................................11

2.4.1 Une alternative pour réduire le temps d’exécution.............................................................112.4.2 Exemple d’exécution de l’algorithme du 2-BFS................................................................12

3 Recherche Analytique...............................................................................................................143.1 Comportement de l’heuristique sur un cas simple.....................................................................143.2 Comportement du 2-BFS sur des familles de graphes particulières..........................................16

3.2.1 Les chemins........................................................................................................................163.2.2 Les étoiles...........................................................................................................................163.2.3 La grille...............................................................................................................................173.2.4 Le graphe complet...............................................................................................................18

3.3 Comportement du 2-BFS sur des graphes connexes aléatoires ................................................193.3.1 Description de la structure de données utilisée pour les calculs.........................................193.3.2 Etude de l’heuristique sur les bornes du nombre d’arêtes .................................................223.3.3 Etude du cas particulier des arbres......................................................................................253.3.4 Evaluation de l’erreur entre le diamètre exact et celui calculé par le 2-BFS......................273.3.5 Evaluation de la probabilité d’obtenir un résultat inexact..................................................313.3.6 Premières conclusions.........................................................................................................33

4 Prolongements et limites .........................................................................................................344.1 Prolongements et réflexions sur la suite des études à menées...................................................344.2 Limites différents résultats obtenus...........................................................................................354.3 Difficultés rencontrées lors de la réalisation du projet..............................................................35

Conclusion..................................................................................................................................36 Références.................................................................................................................................37Annexes…………………………………………………………………………………………………

Etude et Implémentation d'une heuristique permettant de calculer le diamètre

Introduction

Les graphes possèdent de nombreuses applications pratiques, dans des domaines

très variés. Ils permettent, par exemple, de modéliser un réseau de transport en commun,

de réseaux sociaux, des problèmes d’ordonnancement et de routage. La taille des graphes

peu être très importante, par conséquent il est nécessaire de les manipuler par le biais

d’algorithmes rapides. Ces algorithmes permettent au programmeur de calculer des

paramètres tels que le diamètre. Dans les cas des graphes sociaux, ces paramètres sont

utilisés pour mettre en évidence les relations qui peuvent exister entre certains groupes

d’individus ou simplement des propriétés particulières. Ainsi, l'expérience du «petit

monde » de Stanley Milgram stipule que deux personnes choisies aléatoirement sont reliées

au plus par six personnes intermédiaires (ce qui signifie que le diamètre ne pourrait pas

dépasser 6).

Notre projet de fin d’études, consiste à faire une étude de l’algorithme du 2-BFS. Ce

dernier calcule une estimation du diamètre d’un graphe donné et permet de pallier les

inconvénients des algorithmes exacts qui utilisent un espace mémoire très grand et ont un

temps d’exécution très long. A l’issu de cette étude, nous devons conclure sur la pertinence

du 2-BFS et sont utilisation sur des modèles réalistes.

1


1 Présentation du projet

Dans cette première partie nous décrivons le contexte et les objectifs du projet. Nous

détaillons aussi la façon dont nous avons organisé le travail en binôme au cours de l’année

universitaire.

1.1 Contexte

Les graphes ont de nombreuses applications dans divers domaines liés à

l’informatique (télécommunications, transport, etc.). Dans la pratique, le programmeur est

souvent amené à manipuler des graphes de très grande taille. Par conséquent, le temps

dédié au calcul de certains paramètres de ces graphes peut donc être très long.

Il existe néanmoins des algorithmes qui peuvent travailler rapidement sur des grands

graphes mais qui ne donnent pas toujours une réponse exacte. L’objectif de notre projet est

d’implémenter et de tester un tel algorithme. Cet algorithme, appelé 2-BFS, permet

d’estimer le diamètre d’un graphe. Notre objectif est de répondre aux questions suivantes:

Existe-t-il des familles de graphes pour lesquelles l’algorithme du 2-BFS peut ne

pas retourner la valeur exacte du diamètre ?

Si oui, retourne-il souvent une valeur erronée ?

Est-ce que le 2-BFS peut retourner des valeurs très éloignées du diamètre exact ?

Dans quels contextes applicatifs cet algorithme pourrait être utilisable ?

1.2 Travail demandé

Le cahier de charge a été défini lors de notre première réunion avec monsieur

LAFOREST. La figure ci-dessous présente les tâches qui nous ont été assignées.

2


Exemple:

Evaluer, pour certains

types de graphes, l’écart

moyen entre le résultat

calculé par le 2-BFS et

la valeur exacte du

diamètre.

Recherche

expérimentale pour

déterminer dans quels

cas l'algorithme

retourne un mauvais

résultat.

Expérimentation du

programme sur ces

différents graphes en

prenant en compte la

densité des graphes.

Programmation des

générateurs de graphes

aléatoires et

particuliers (chemins,

arbres, grilles,..)

Programmation

de l’algorithme

du 2-BFS en C++

et en Matlab

Performances de

l’algorithme2-BFS

3


Figure 1 Présentation des différentes tâches

Evaluer, pour certains

types de graphes, l’écart

moyen entre le résultat

calculé par le 2-BFS et

la valeur exacte du

diamètre.

Recherche

expérimentale pour

déterminer dans quels

cas l'algorithme

retourne un mauvais

résultat.

Expérimentation du

programme sur ces

différents graphes en

prenant en compte la

densité des graphes.

Programmation des

générateurs de graphes

aléatoires et

particuliers (chemins,

arbres, grilles,..)

Programmation

de l’algorithme

du 2-BFS en C++

et en Matlab

Performances de

l’algorithme2-BFS

4


1.3 Organisation du travail

Afin de répondre au cahier de charge établi par Mr. LAFOREST, nous avons choisi de

travailler de façon parallèle sur les deux points suivants :

Réflexion théorique sur la qualité de l’algorithme du 2-BFS

Analyse expérimentale tester les hypothèses établies.

Nos résultats théoriques et notre expérimentation étaient régulièrement validés par notre

encadrant Mr. LAFOREST au cours de réunions hebdomadaires.

5


2 Eléments de la théorie des graphes

Dans cette seconde partie, nous abordons les notions élémentaires de la théorie des

graphes que nous avons utilisées dans notre projet.

2.1 Premières définitions

2.1.1 Définition (Graphe)

Un graphe est caractérisé par deux ensembles notés X et E qui désignent

respectivement les sommets et les arcs. Dans la cadre de notre projet, on travaillera

uniquement sur les graphes non orientés, c'est-à-dire les graphes où les arcs (i, j) et (j, i)

sont indiscernables. De plus, nous considérerons uniquement le cas des graphes non

pondérés, où chaque sommet a la même contribution.

2.1.2 Définition (Graphe connexe)

Un graphe G est dit connexe si et seulement si, pour tout couple de sommets (i, j)

appartenant à ce graphe, on peut trouver un chemin allant de i vers j dans G.

Figure 2: Exemple de graphe connexe

2.1.3 Définition (Matrice d’adjacence)

Soit G un graphe de n sommets. La matrice d’adjacence A est la matrice de

dimension n x n telle que : aij = 1 pour tout arc (i, j) du graphe G et aij = 0 pour tous les

autres éléments de la matrice A..

Remarque: Pour la suite du rapport, nous considérons uniquement les graphes connexes

6


non orienté. La matrice d’adjacence de ce type de graphe est symétrique.

Exemple: Dans le cas de la figure 1 la matrice d’adjacence sera alors :

0 1 0 0

1 0 1 1

0 1 0 1

0 1 1 0

2.1.4 Définition (Distance)

La distance entre deux sommets i et j d’un graphe G est le nombre minimum d'arêtes

qu'on doit parcourir pour aller de i vers j. C’est le nombre d'arêtes correspondant au chemin

le plus court de i vers j. On notera par la suite d (i, j) la distance entre i et j.

Exemple: La distance entre le sommet 1 et le sommet 4 vaut 2. Elle correspond au chemin

tracé en rouge.

Figure 3: Calcul de la distance

7


2.1.5 Définition (Excentricité)

L'excentricité d'un sommet i appartenant à un graphe G est la plus grande distance

séparant i d'un autre sommet j de ce graphe. Ecc(i)= max {d (i, j) : j ∊ V}.

Exemple:

Ecc(1) = 2

Ecc(2) = 1

Ecc(3) = 2

Ecc(4) = 2

2.1.6 Définition (Diamètre)

Le diamètre D d’un graphe G est la plus grande distance possible dans G.

D = max { Ecc(i), i ∈ V }

Exemple: Diamètre = max {2, 1, 2, 2} = 2

8


2.1.7 Définition (Rayon)

Le rayon R d’un graphe G est, à l’inverse du diamètre, le minimum des excentricités

des sommets de G.

Exemple: Si nous reprenons l’exemple précédent, nous obtenons R = min {2, 1, 2, 2} = 1.

2.2 Exploration des sommets d’un graphe

En théorie des graphes, il existe plusieurs algorithmes de parcours. Dans le cadre de

notre projet de fin d’études, nous utiliserons le parcours en largeur que l’on appelle aussi

BFS (Breadth First Search). Il permet d’explorer l’ensemble des sommets du graphe par

voisinage.

Algorithme de principe du BFS

- (a) On choisit un sommet de départ et on l’insère dans une file ;

- (b) On retire le premier sommet de la file et on le marque ;

- (c) On insère tous ses sommets adjacents qui ne sont pas marqués dans la file ;

- (d) Si la file est non vide, alors on revient au point (b).

Implémentation du BFS

Figure 4 Algorithme de principe du BFS

9


Exemple: Considérons le graphe ci-dessous. Si on choisit le sommet 1 comme sommet de

départ.

Le BFS va parcourir dans l’ordre les sommets : 1, 2, 3, 4.

2.3 Algorithme de calcul du diamètre exact d’un graphe

On sait que le diamètre d’un graphe G est défini comme étant la plus grande distance

possible G. Pour calculer le diamètre exact d’un graphe, le premier algorithme auquel on

pourrait penser consiste à faire un parcours en largeur à partir de tous les sommets pour

connaître leur excentricité et de retourner ensuite le maximum des excentricités.

Figure 5 Algorithme de principe du diamètre exact

Dans la pratique, la mise en œuvre de cet algorithme glouton sur des graphes possédant de

nombreux sommets peut être très coûteuse en termes de temps de calcul.

10


2.4 L’algorithme du 2-BFS

2.4.1 Une alternative pour réduire le temps d’exécution

Le 2-BFS qualifié d’heuristique car il fait appel à l’aléatoire pour le choix des sommets

de départs. L’intérêt du 2-BFS par rapport à l’algorithme glouton et qu’il offre un temps

d’exécution plus court. De plus, les expérimentations menés sur les graphe d’Erdos Reyni,

nous on permis de constater une augmentation sensible du rapport des deux temps

d’exécutions en fonction nombre de sommets.

Figure 6: Présentation des évolutions des temps d'exécutions des deux algorithmes pour des Graphes de Erdos Reyni (de probabilité égale à 0.3)

11


Le principe du 2-BFFS est le suivant :

Figure 7 Algorithme de principe du 2-BFS

2.4.2 Exemple d’exécution de l’algorithme du 2-BFS

Mettons en pratique le 2-BFS sur la figure 2.

Si on prend le sommet 1 comme sommet de départ alors on a :

Figure 8 Simulation du premier BFS sur cas simple

Le sommet le plus éloigné sont les sommets 3 et 4, on applique maintenant 2-BFS à partir du

sommet 4 par exemple.

12


Figure 9 Simulation du second BFS sur un cas simple

Le résultat retourné par le 2-BFS est donc 2 car cela correspond à la plus grade distance

obtenue lors de la deuxième exécution du BFS.

13


3 Recherche Analytique

Dans cette section, nous nous intéressons particulièrement à l’analyse théorique du

problème. Précédemment, nous nous sommes intéressés à des familles de graphes

particuliers. Nous, nous allons par la suite de prolonger ces analyses à des graphes de plus

grande taille générés de façon aléatoire.

3.1 Comportement de l’heuristique sur un cas simple

Initialement, nous avons simulé les exécutions de l’heuristique sur des graphes

simples pour répondre à la question théorique suivante:

Existe-t-ils des graphes pour lesquels l’algorithme du 2-BFS ne retourne pas le diamètre

exact ? (Q1)

Exemple1 : le 2-BFS retourne le bon diamètre

La figure ci-après représente un graphe aléatoire sur lequel nous allons simuler une

exécution du 2-BFS. Dans cette figure, les valeurs en rouge correspondent à la distance

entre G – choisi comme sommet de départ – et les autres sommets du graphe. Après

exécution du 2-BFS, on remarque que le sommet A est e plus éloigné de G. A est appelé

sommet «écho». Nous appliquons ensuite un deuxième BFS à partir de A. Le résultat

retourné correspond exactement à la valeur de diamètre.

14


- Diamètre retourné par le 2-BFS = 4

- Diamètre exact = 4

a

c

b

d f

e

g

0

1

2

2

3

4

3

0

1

2

1

2

3

4

Diamètre Exact = 4Diamètre Retourné = 4

Point « echo »Point de départ

Figure 10 Simulation du 2-BFS sur un graphe qui retourne le bon résultatExemple 2: le 2-BFS ne retourne pas le bon diamètre

On prend B comme sommet de départ.



Figure 11Simulation du 2-BFS sur un graphe avec retour d'un résultat erroné

15


Réponse à Q1 : Il existe bien des graphes dans lesquels l’algorithme peut ne pas retourner

le résultat exact.

3.2 Comportement du 2-BFS sur des familles de graphes particulières

3.2.1 Les chemins

Dans le cas du chemin, le 2-BFS retournait toujours le diamètre exact. En effet, quel que soit

le sommet de départ qu’on choisi, le sommet le plus éloigné est l’une des extrémités du

chemin. La deuxième exécution du BFS nous permet de conclure que la distance entre les

deux extrémités du chemin est la valeur exacte du diamètre.

Le schéma ci-dessous représente une exécution du 2-BFS sur un chemin. On choisit le

sommet 3 comme sommet de départ.

Figure 12 Simulation du 2-BFS sur un chemin- Diamètre exact = 5


3.2.2 Les étoiles

Dans le cas d’une étoile, il y a 2 cas à tester. Soit on choisit le centre comme sommet de

départ, soit on choisit l’extrémité d’une branche comme sommet de départ. Les expériences

que nous avons menées, nous ont permis de constater que le 2-BS retournait le bon

diamètre dans les deux cas

Cas 1 : on prend le centre de l’étoile comme sommet de départ

16


Figure 13 simulation du 2-BFS sur une étoile (départ du centre)- Diamètre exact = 2


Cas 2: on prend une extrémité (sommet C, par exemple) comme sommet de départ

Figure 14 simulation du 2-BFS sur une étoile (départ d'une extrémité)- Diamètre exact = 2


3.2.3 La grille

Soit n le nombre de colonnes de la grille et p le nombre de lignes. On sait que le diamètre

correspond à la distance entre deux sommets de la grille. Les sommets les plus éloignés sont

les deux extrémités de la diagonale de la grille. Le diamètre exact est donc donné par la

formule suivante : D = (n–1) + (p–1) = n + p - 2.

Voici un exemple d’exécution du 2-BFS sur une grille de 3 lignes et 3 colonnes.

17


Figure 15 simulation du 2-BFS sur une grille- Diamètre exact = 3 + 3 – 2 = 4


Etant donné que le diamètre exact correspond à la distance entre deux coins, si un BFS est

lancé à partir de n'importe quel coin alors la distance maximale retournée sera le diamètre

exact puisque pour tous les coins, il existe un chemin de distance maximale qui sera

considéré par le BFS. Donc si le point echo est un des coins, l'algorithme nous donnera

toujours le bon résultat. De plus, pour chaque sommet ne correspondant pas à un coin, le

sommet le plus éloigné correspond toujours à un coin. En conclusion, quel que soit le point

choisi on arrivera toujours au schéma nous renvoyant le diamètre exact. C'est pourquoi

l'algorithme est exact pour ce type de graphe

Remarque : Le chemin est un cas particulier de la grille. C’est une grille composée d’une

seule ligne.

3.2.4 Le graphe complet

Un graphe complet à n sommets est un graphe dont les sommets sont tous reliés deux à

deux par une arête. Ce graphe a 2

)1( −× nnarêtes.

Dans le cas d’un graphe complet, l’algorithme du 2-BFS, retourne toujours le diamètre exact.

En effet, tous les sommets sont deux à deux reliés par une arête, donc le distance entre

deux sommets différents est toujours égale à 1.

Voici un exemple qui permet d’illustrer cette propriété.

On prend A comme sommet de départ.

18


Figure 16 Simulation du 2-BFS sur un graphe complet



Conclusion: Il existe donc des familles de graphes où l’heuristique devient un algorithme

exact.

Remarque: A l’inverse, on pourrait se demander s’il existe des familles de graphes le 2-BFS

se tromperait systématiquement. Cela n’est pas possible car il existe toujours une

probabilité non nulle d’obtenir le diamètre exact. En effet, notons u et v deux sommets qui

sont les plus éloignés d’un graphe G. Si l’on exécute l’algorithme du 2-BFS en partant de u,

alors on est sûr qu’un des sommets échos sera v puisqu’il est le plus éloigné de u. En

effectuant le deuxième BFS on est alors sûr de retourner la valeur exacte du diamètre.

3.3 Comportement du 2-BFS sur des graphes connexes aléatoires

Objectif: Nous avons précédemment établi l’existence de graphes pour lesquels le 2-BFS ne

retourne pas le diamètre exact. Nous devons maintenant évaluer cette erreur. On note DG le

diamètre exact du graphe G, et on note DG’ la plus petite valeur retournée par le 2-BFS. On

veut montrer l’assertion suivante :

∀G, ∃k tel que DG - DG’ = k (*)

Pour prouver l’équation (*), il est nécessaire de rappeler la propriété ci-après qui permet

d’encadrer le nombre d’arêtes d’un graphe connexe donné :

n–1 ≤ nombre d’arêtes ≤ 2

)1( −× nn (**)

3.3.1 Description de la structure de données utilisée pour les calculs

Pour optimiser la phase d’expérimentation du 2-BFS, nous avons tenté de trouver une

19


structure de données adéquate. Le choix de cette structure doit permettre de réduire le

temps d’exécution de l’algorithme. Nous avons donc opté pour l’utilisation de deux

tableaux. Le premier tableau est de longueur n, où n est le nombre de sommet du graphe G

considéré. Chaque cellule d’indice u contient un pointeur vers un autre tableau contenant

les sommets les plus éloignés du sommet u du graphe G. Quant au second tableau, il est

également de longueur n et sera utilisé pour stocker l’excentricité de chaque sommet de G.

Entrée : Graphe G= (V,E)

V= {1,...,n}

1

n

Tableau contenant les sommets les plus éloignés de u

1

n

Ecc(u)

Tableau contenant les excentricités de chaque sommet

Tableau 1

Tableau 2

Tableau 3

Figure 17 Schématisation de la structure utilisée pour stocker les résultats

Exemple:

20


Figure 18 Graphe utilisé pour illustrer la structureSi nous prenons le graphe ci-dessus comme exemple, le contenu des deux tableau est

comme suit :

Figure 19: Tableau contenant tous les sommets échos dans le cas d'un graphe simple

Figure 20: Tableau contenant l'ensemble des excentricités pour un exemple

21


3.3.2 Etude de l’heuristique sur les bornes du nombre d’arêtes

3.3.2.1 Etude sur un graphe complet privé d’une arête

Dans le cas d’un graphe complet G que l’on prive d’une arête, le diamètre exact du graphe

G’ obtenu est égal à deux. L’exécution du 2-BFS sur G’ retourne donc 1 ou 2. Nous allons

mesurer la probabilité d’obtenir chacune de ces deux valeurs.

Exemple:

Figure 21 Graphe complet privé d'une arête

Démarche scientifique: Nous allons calculer l’espérance du diamètre retourné par

l’algorithme du 2-BFS car c’est un bon indicateur de la performance de l’algorithme. Par

conséquent plus l’espérance sera proche du diamètre exact, plus l’algorithme sera

performant.

Définition (Espérance):

Si X est une variable aléatoire qui prend un nombre fini de valeurs réelles x1, x2, …, xn avec

des probabilités respectives p1, p2, …pn alors l’espérance de X est donnée par:

E(X) =∑=

=

ni

i

iixp1

Remarque importante: Lorsque l’espérance du diamètre retourné par l’algorithme du 2-

BFS, on peut conclure que ce dernier retourne le bon diamètre. Dans le cas contraire, on

peut seulement avancer que le

2-BFS peut ne pas retourner le diamètre exact.

Analyse: Revenons au graphe G’ obtenu après la suppression d’une arête d’un graphe

complet G. Lors de l’exécution du premier BFS sur G, si nous choisissons comme sommet de

départ un des sommets de l’arête supprimée, alors l’algorithme retournera certainement 2.

22


Exemple 1: On choisit D comme sommet de départ

Figure 22 graphe complet privé d'une arête

SI nous choisissons D (ou C) comme sommet de départ, alors on est sûr que l'algorithme

retournera 2 comme résultat. En effet, le premier BFS nous retournera l'autre sommet

(c'est-à-dire C) comme étant le plus éloigné et le deuxième BFS nous retournera

l’excentricité de ces sommets qui vaut 2.

Exemple 2-a :

- Nous partons de A lors du premier BFS

- Nous partons de B lord du second BFS

- Le 2-BFS retourne la valeur 1

Figure 23 Cas où le 2-BFS retourne 1

23


Exemple 2-b :

- Nous partons de A lors du premier BFS

- Nous partons de C lors du second BFS

- Le 2-BFS retourne la valeur 2

Figure 24 Cas où le 2-BFS retourne la valeur 2

On note D’ le diamètre retourné par le 2-BFS. Nous pouvons déduire que:

p(D’ = 1) =)1(

)3()2(

−×−×−

nn

nn

or E(D’) = p(D’ = 1) ×1 + p(D’ = 2) × 2 et de plus p(D’ = 2) + p(D’ = 1) = 1

d’où :

Espérance = )1(

)3)(2()1(2

−×−−−−×

nn

nnnn

Illustrations des calculs:

24


Figure 25: Copies d'écran présentant quelques résultats du calcul de l'espérance

Remarque: On peut préciser que lorsque n augmente, l’espérance tend alors vers 1 ce qui

veut dire que l’on se trompe de plus en plus souvent.

3.3.3 Etude du cas particulier des arbres

Dans le cas où le graphe est un arbre nous avons conjecturé que l’algorithme

retournait systématiquement le résultat exact. En effet nos résultats numériques

confirment cette conjecture. Néanmoins nous n’avons pas réussir à le prouver. La figure 26

illustre quelques copies d’écrans des résultats obtenus pour des arbres de différentes tailles.

25


Figure 26: Copies d'écrans d'exécutions de l'algorithme pour des arbres de taille variant de 50 à 100

26


3.3.4 Evaluation de l’erreur entre le diamètre exact et celui calculé par le 2-BFS

Nous avons à-priori établi l’hypothèse suivante:

2

GD ≤ D’ ≤ DG. où D’ représente le diamètre retourné par le 2-BFS et DG le diamètre

exact du graphe G.Preuve de l'encadrement:

Nous allons d’abord montrer l’inégalité suivante: D’ ≤ DG.

On sait que le diamètre retourné par le BFS est l’excentricité du sommet écho. Or, par

définition, le diamètre exact est le maximum des excentricités des sommets du graphe.

D’où l’inégalité D’ ≤ DG.

Il nous reste à prouver que : 2

GD ≤ D’. Pour cela, considérons le schéma ci-dessous:

Figure 27 Schéma pour illustrer un chemin de diamètre égal au diamètre exact

On a d(s, r) ≤ Ecc(r) et d(r, t) ≤ Ecc(r) pour tous les sommets r du graphe G. En effet,

toutes les distances de s à r sont majorées par son excentricité.

D’où :

d(s, r) + d(r, t) ≤ 2×Ecc(r)

De plus d(s, t) ≤ d(s, r) + d(r, t) (inégalité triangulaire)

Cela implique que d(s, t) ≤ d(s, r) + d(r, t) ≤ 2×Ecc(r)

Dans le graphe que nous avons considéré, les sommets les plus éloignés sont s et t.

Donc, le diamètre exact est DG = d(s, t).

L’inégalité étant valable pour tous les sommets du graphe G, elle est donc valable pour

27


toutes les exécutions possibles du 2-BFS.

DG <= 2×D’ c’est à dire 2

GD ≤ D’.

On peut donc conclure la formule établi :

2

GD <= DG ≤ DG

Remarque: Il existe des graphes pour lesquels la valeur retourné par l’algorithme du 2-BFS

peut valoir exactement2

GD. Cf. cas du graphe complet privé d’une arête.

Expérimentation: Nous avons pris n=100 et nous sommes passés progressivement de

l’arbre à (n-1) arêtes au graphe complet à 2

)1( −× nn arêtes.

Justification: Nous avons confronté la propriété (* encadrement) à une expérimentation.

Pour cela, nous avons généré aléatoirement des graphes dont le nombre d’arêtes varie de

n-1 à 2

)1( −× nn où n= 100 est le nombre de sommets. A chaque itération (pas 10), on

calcule le diamètre exact avec l’algorithme glouton décrit dans le paragraphe.

Ensuite on récupère l’espérance en appliquant la méthode de calcul (cf. calcul de

l’espérance ci –dessus). Finalement on représente le rapport diamètre exact / espérance.

Ainsi, la figure 28 illustre graphiquement une exploration.

- lorsque Diamètre exact/espérance = 1 ⇒ Algorithme est exact.

- sinon il y a susceptibilité d’obtenir un résultat inexact.

28


Figure 28: Courbe présentant le rapport entre le diamètre exact et l'espérance des valeurs retournés avec un pas de 10

Remarque: On constate donc que l’inégalité est vérifiée. On remarque également deux

zones susceptibles de retourner un mauvais résultat aux extrémités du graphique. Nous

avons donc affiné les calculs en choisissant un pas de 1 et en calculant d’autres valeurs

numériques. Ainsi dans la figure ci-dessous, on représente dans la zone de perturbation

proche de l’arbre (entre 4000 et 4900 arêtes), l’espérance (en haut à gauche), l’écart

type(en bas) et le pourcentage de certitude absolue (pourcentage de cas où toutes les

exécutions retournent le diamètre exact).

29


Figure 29: Illustration de quelques valeurs statistiques dans le cas où le graphe est dense

Le fait que l’on puisse encadrer la valeur du diamètre retourné entre le diamètre

exacte divisé par 2 et le diamètre exacte est un premier début pour justifier que l’algorithme

ne se trompe pas de beaucoup. Cependant cet encadrement n’est plus pertinent lorsque le

diamètre du graphe devient trop important.

Il semblerait aussi que la différence entre le diamètre exact et la valeur retournée

n’excède que de très peu. Ci-après, une illustration numérique où l’on a représenté en

abscisse le nombre d’arêtes et en ordonnée la différence entre le diamètre exact et la plus

petite valeur susceptible d’être retourné par le 2-BFS. (On a choisi 40 sommets)

N.B. On retrouve de la même façon que dans la figure 28, une zone où il semblerait que l’on

retrouve constamment le bon résultat.

30


Figure 30: Illustration de la différence entre diamètre exacte et valeur de l'algorithme

3.3.5 Evaluation de la probabilité d’obtenir un résultat inexact

Nous avons vu précédemment que lorsque l’on se trompe, l’écart entre la valeur

retourné et le diamètre exact était peu élevé. La question que l’on se pose est de savoir si

on est capable de se tromper de beaucoup. Un des éléments de réponse réside dans le fait

que lorsque l’on explore l’ensemble des graphes connexes, il existe des graphes où lequel la

probabilité de se tromper avoisine les 95 % de pourcentage d’erreurs. On a donc

assurément l’existence de graphe où l’on peut se tromper très régulièrement. La figure ci-

dessous en illustre l’existence.

31


Figure 31 Evolution de la probabilité d'obtenir un résultat inexact en fonction du nombre d'arêtes pour un nombre de sommets égale à 40

32


3.3.6 Premières conclusions

Nous allons maintenant tenter de résumer, l’ensemble des résultats obtenus.

1. Il existe des familles de graphes pour lesquels l’algorithme retourne un diamètre

inexact,

2. Néanmoins, quel que soit le graphe la probabilité d’obtenir le diamètre exact résultat

est non nulle,

3. Il existe des familles de graphes pour lesquels l’algorithme retourne systématiquement

la valeur exacte.

4. Il semblerait que le 2-BFS se trompe de peu.

5. Il existe des graphes où la probabilité de se tromper est très élevé.

6. On a aussi remarqué la présence d’une zone pour lequel le 2-BFS retourne toujours le

bon diamètre. Comme on peut le voir sur la figure, ce domaine va de 1500 à 4500

arêtes. (dans cette zone on ne se trompe pas souvent)

7. Les bornes établis théoriquement sont relativement intéressante pour des petits

diamètres (pour des grands diamètres, l’écart entre les bornes devient important).

33


4 Prolongements et limites

Cette section présente les possibilités de prolongements nos calculs. Enfin nous

évoquerons dans une troisième partie les difficultés rencontrées tout au long du projet.

4.1 Prolongements et réflexions sur la suite des études à menées

A travers ce projet, nous avons répondu à certaines questions avec certitude.

Néanmoins, il est à noter que certains résultats n’ont pas des conclusions définitives et

doivent être soumises à des études plus complètes.

En premier lieu, nous avons évoqué dans nos résultats l’existence d’une zone de

palier, où l’algorithme renvoie systématiquement le diamètre exact. Il serait intéressant

d’étudier de manière plus précise cette zone de confiance, car elle a été constatée sur

certains tests (en particulier n = 100 sommets). La question à se poser serait :

Questions : Est-ce qu’il y a constamment présence d’une zone de confiance quel que soit

la taille du graphe ? Est-ce qu’elle évolue ? Est-elle périodique ?

En second lieu, nous avons montré dans les précédents résultats qu’il existait des

graphes où l’on pouvait se tromper souvent. Il serait donc intéressant de déterminer si ces

graphes ont une caractéristique particulière. On pourrait alors se poser les questions

suivantes :

Questions : Il y a-t-il plus de graphe où l’on se trompe souvent que de graphe où l’on se

trompe peu ? Peut-on borner dans certaines zones la probabilité que l’on obtient un

résultat inexact ?

Nous avons aussi évoqué le fait que l’inexactitude des valeurs de l’algorithme était

selon vraisemblance peu élevé. Néanmoins, il reste à démontrer de manière générique que

l’on peut affiner la borne qui minimise les valeurs retournées pour certains graphes. On

peut donc proposer comme question de prolongement :

Questions : Quels sont les familles de graphes où les erreurs de l’heuristique sont

marginales ?

Enfin, dans un souci d’apporter des résultats encore plus concrets, il aurait été

intéressant de s’intéresser au comportement de l’heuristique pour des graphes sociaux. 34


Faute de temps, nous n’avons pu étudier des graphes sociaux de grandes tailles. Nous avons

d’ailleurs récemment découvert qu’un groupe d’étudiants de deuxième année s’intéressait

plus particulièrement dans leur projet aux graphes sociaux. Même si ces graphes ne sont

pas connexes, il aurait été intéressant d’apporter des analyses complémentaires.

4.2 Limites différents résultats obtenus

Malgré nos résultats expérimentaux, nous tenons à être très prudent sur les

conclusions que nous pouvons déduire. En effet, pour certaines de nos conclusions, il s’agit

uniquement de constatations. Elles doivent donc pour être définitivement validées, être

sujettes à des démonstrations suffisamment rigoureuses. C’est pourquoi, il est nécessaire

d’effectuer des études plus approfondies pour justifier de leur pertinence.

4.3 Difficultés rencontrées lors de la réalisation du projet

Au cours de notre projet, nous avons confronté les programmes réalisés en Matlab et

en C++. De cette confrontation, nous avons conclu qu’il était plus judicieux de faire appel à

une libraire préalablement implémentée. Cela permet de pallier la réflexion concernant le

choix de la meilleure structure de données. Le programme réalisé en Matlab grâce à la

bibliothèque BGL, a donc été plus rapide et efficace que celui réalisé en C++. Le tableau ci-

dessous représente le temps d’exécution des deux programmes en fonction du nombre de

sommets des graphes. Plus le nombre de sommets est grand, plus le rapport entre les temps

d’exécution devient considérable.

En Matlab En C++

Graphe de 20 sommets 0.00124 secondes 0.01233 secondes

Graphe de 70 sommets 0.00241 secondes 2.4 secondes

Graphe de 100 sommets 0.012478 secondes 60 secondes

On a finalement décidé d’effectuer l’ensemble de nos calculs sur Matlab.

35


Conclusion

Notre projet de fin d’études nous a permis de déployer les techniques de

programmation que nous avons acquises en C++ et en Matlab. Il nous a également permis

d’approfondir nos connaissances en théorie des graphes Nous avons été confronté à une

étude sur des modèles de graphes de très grande taille. On retrouve ce type de graphes

dans des cas réels de l’informatique industrielle ou en télécommunications. Cette

expérience a été un enrichissement pour notre culture en recherche opérationnelle.

D’un point de vue humain, nous avons rencontré des difficultés de communication

liées au travail d’équipe puisqu’il a fallu régulièrement faire une comparaison entre les

résultats obtenus de chaque côté. Ces difficultés ont été surmontés car nous nous avions de

chaque côté la volonté que ce projet puisse aboutir.

36


Références

[1] Documentation de la librairie matlab_bgl http://www.stanford.edu/~dgleich/programs/matlab_bgl/matlab_bgl_v2.1.pdf)

[2] Daniel Broderick Arneson et piotr rudnicki Recognizing Chordal Graphs : Lex BFS and MCS http://www.mizar.org/fm/2006-14/pdf14-4/lexbfs.pdf

[3] Sylvie Hamel, Université de Montréal, 2009http://www.iro.umontreal.ca/~hamelsyl/parcoursA09_4.pdf

[4] Derek G .CORNEIL, Fredor F .DRAGAN, Michel HABIB et Christophe Paul, Diameter Determination on Restricted Graph Familieshttp://www.springerlink.com/content/yr3tg81ckgljgh4d/fulltext.pdf

37

http://www.iro.umontreal.ca/~hamelsyl/parcoursA09_4.pdf

http://www.mizar.org/fm/2006-14/pdf14-4/lexbfs.pdf

http://www.stanford.edu/~dgleich/programs/matlab_bgl/matlab_bgl_v2.1.pdf


Annexes : Présentation des codes sources

Matlab

Réalisation du programme en Matlab

Afin de réaliser la conception de l'algorithme, nous avons utilisé une librairie qui

permet de manipuler facilement les graphes. La toolbox utilisée s'appelle matlab_bgl et est

téléchargeable à cette adresse :http://www.stanford.edu/~dgleich/programs/matlab_bgl/

Structure des fichiers

La conception du programme est séparée en plusieurs fichiers. Certains fichier

permettent de construire des graphes en particulier (arbre.m pour la création d'un arbre),

d'autres se concentrent sur l'algorithme (exact.m pour l'algorithme retournant le diamètre

exact, deux_bfs pour l'implémentation de l'algorithme deux_bfs), enfin Statistiques.m est le

fichier d'exécution qui permet via un menu de choisir les tâches à effectuer. Il y a en plus de

cela des scripts permettant d’explorer un certain nombre de graphes en calculant

différentes données.

i


Arbre .m

%--------------------------------------------------------------------------% Fonction permettant de créer un arbre à partir d'un graphe complet%-------------------------------------------------------------------------- function [complet] = arbre(complet,n) %Pour avoir de bonnes valeures aléatoiresrand('twister',sum(100*clock)); nb_arete = n*(n-1)/2;test = 1; %--------------------------------------------------------------------------%Tant que l'on a pas obtenu un arbrewhile nb_arete > n-1 bool = 1; while bool==1 bool = 0; %---------------------------------------------------------------------- %On choisit une arête au hasard u = ceil(n*rand); v = ceil(n*rand); val = complet(u,v); %Si on peut enlever l'arête if (val==1) %On l'enlève... complet = retirer_arete(complet,u,v); %------------------------------------------------------------------------- %...En regardant la connexité!!! %On effectue un bfs sur un sommet au hasard r = ceil(n*rand); [d,dt,pred] = bfs(complet,r); %Si un des prédecesseurs(exceptés celui choisi) est nul cela veut dire %que ce n'est pas connexe for i=1:length(pred) if i~=r if pred(i)==0 test = 0; end end end % On remet l'arête si le graphe n'est plus connexe et on

ii


% recommence la recherche d'arête if test==0 complet(u,v) = 1; complet(v,u) = 1; bool = 1; test = 1; end % Dans le cas où l'arête n'existe pas on teste une autre arête else bool = 1; end end nb_arete = nb_arete - 1; endend

iii


Calcul.esperance.m

%-----------------------------------------------------------------------% Fonction qui permet de calculer numériquement l'espérance d'un graphe%----------------------------------------------------------------------- function esp = calcul_esperance(S,n,diametre,tab) %Initialisation du calcul de l'espéranceesp = 0; %On applique la formule de l'espérance dans le cas discret on va donc%évaluer à chaque fois la probabilité que le diamètre vaut k for k=1:diametre %Initialisation du calcul de la probabilité p = 0; for i=1:n %On récupère les sommets echos vec = S{1,i}; l = length(vec); %On évalue la probabilité en tenant compte de la taille du vecteur %contenant les sommets echos p = p + length(find(tab(vec)==k))/l; end % On n'oubli pas de diviser par n car le premier choix du sommet est % choisi de manière équiprobable p= p/n; % On met à jour la valeur de l'espérance esp = esp + k*p; end

iv


creation_graphe.m

% Fonction qui permet de générer un graphe à n sommet et m arêtes.% Pour cela on part du graphe complet à n sommet.% Puis on enleve des arêtes en gardant le graphe connexe. function [graphe] = creation_graphe(n,m,complet) %Pour avoir de bonnes valeures aléatoiresrand('twister',sum(100*clock)); cpt = n*(n-1)/2;test = 1; while cpt > m %---------------------------------------------------------------------- %On choisit une arête au hasard u = ceil(n*rand); v = ceil(n*rand); val = complet(u,v); %Si on peut enlever l'arête if (val==1) %On l'enlève... complet = retirer_arete(complet,u,v); %------------------------------------------------------------------------- %...En regardant la connexité!!! %On effectue un bfs sur un sommet au hasard r = ceil(n*rand); [d,dt,pred] = bfs(complet,r); %Si un des prédecesseurs(exceptés celui choisi) est nul cela veut dire %que ce n'est pas connexe for i=1:length(pred) if i~=r if pred(i)==0 test = 0; end end end % On remet l'arête si le graphe n'est plus connexe et on % recommence la recherche d'arête if test==0 complet(u,v) = 1; complet(v,u) = 1; test = 1; else cpt = cpt - 1;

v


end end endgraphe = complet; end

vi


deux_bfs.m

%--------------------------------------------------------------------------% Fichier M edité par Rachid dans le cadre du projet deux_bfs 2009-2010% Pour toute questions n'hésitez pas à nous contacter à l'adresse% [email protected]%-------------------------------------------------------------------------- function [diam]=deux_bfs(A) % Pour obtenir le nombre de sommetsn = size(A,1);% Pour avoir de bonnes valeurs aléatoires (la graine change régulièrement% d'où l'indépendance des résultats) rand('twister',sum(100*clock)); % Récupération d'un sommet aléatoirer = ceil(n*rand); % Exécution du premier BFS[d,dt,pred] = bfs(A,r); % Récupération des sommets les plus éloignés[y,L] = max(d);long = length(L); if long>=2 % Si on a plusieurs sommets echos on en choisit un aléatoirement s = ceil(long*rand); [d,dt,pred] = bfs(A,L(s)); diam = max(d);else % Si on en a qu'un seul [d,dt,pred] = bfs(A,L); diam = max(d);end end

vii


exact. m

%Fichier M edité par Rachid dans le cadre du projet deux_bfs 2009-2010%Pour toute questions n'hésitez pas à nous contacter à l'adresse%[email protected] [diam]=exact(A) %chdir('Projet ZZ3/matlab_bgl'); n = size(A,1); % Pour obtenir le nombre de sommetsdiam = 0; for i=1:n [d,dt,pred] = bfs(A,i); y = max(d); if y>=diam diam = y; endend end

exact_liste

%Fichier M edité par Rachid dans le cadre du projet deux_bfs 2009-2010%Pour toute questions n'hésitez pas à nous contacter à l'adresse%[email protected]%% S contient une structure contenant le sommet % tab est un tableau contenant les excentricités de chaque sommet%-------------------------------------------------------------------------- function [tab,S]=exact_liste(A) % Pour obtenir le nombre de sommetsn = size(A,1); for i=1:n [d,dt,pred] = bfs(A,i); y = max(d); vec = find(d==y); S{1,i}= vec; tab(i)=y;end end

viii


graphe_alea.m

%Fichier M edité par Rachid dans le cadre du projet deux_bfs 2009-2010%Pour toute questions n'hésitez pas à nous contacter à l'adresse%[email protected] function [res]=graphe_alea(n,p) %Génére un graphe aléatoire nombre de sommet n, probabilité p %On génere un graphe aléatoire de erdos_reynires = erdos_reyni(n,p);bool = 0;%On choisit un sommet au hasardr = ceil(n*rand); %Tant que l'on a pas trouvé un graphe connexewhile bool==0 bool=1; %On effectue un bfs sur le sommet chosii [d,dt,pred] = bfs(res,r); %Si un des prédecesseurs(execptés celui choisi) est nul cela veut dire %que ce n'est pas connexe for i=1:length(pred) if i~=r if pred(i)==0 bool = 0; end end end %Si ce n'est pas connexe on en regenère un autre et on va tester dans %la boucle suivante si ce nouveau graphe est connexe if bool==0 res = erdos_reyni(n,p); endend end

ix


grille .m

function [M]=grille(n,p) % n représente le nombre de colonnes% p représente le nombre de lignes % Initialisation de la matrice d'incidenceM=sparse(n*p,n*p); % On va s'occuper des arêtes sur les lignes err=n; for i=1:(n*p)-1 if i~=err M(i,i+1)=1; else err=err+n; endend % Puis on s'occupe de celle des colonnes for i=1:n*(p-1) M(i,i+n)=1; end % Pour obtenir la matrice symétrique désirée M=max(M,M'); end

x


retirer_arete_alea.m

%-----------------------------------------------------------------------% Fonction qui permet de retirer alétoirement une arête d'un graphe%----------------------------------------------------------------------- function [graphe]=retirer_arete_alea(graphe,n) val=0;while val~=1 u = ceil(n*rand); v = ceil(n*rand); val = graphe(u,v);endgraphe(u,v) = 0;graphe(v,u) = 0; end

xi


statistiques.m

%Fichier M edité par Rachid dans le cadre du projet deux_bfs 2009-2010%Pour toute questions n'hésitez pas à nous contacter à l'adresse%[email protected]%-------------------------------------------------------------------------- %--------------------------------------------------------------------------%Script pour faire des statistiques sur les graphesclear all;clc; n=100;p=10;q=1; choix = menu('Choix du Graphe et des donnnées','Graphe Aléatoire(Erdos_Reyni)','Grille','Graphe Complet - 1 arête','Arbre');if(choix==1) graphe = graphe_alea(n,0.3); taille = n;elseif(choix==2) graphe = grille(p,q); taille=p*q; elseif(choix==3) %-------------------------------------------------------------------------- % Création du graphe Complet taille = n; graphe = ones(n) - eye(n); graphe = sparse(graphe); %-------------------------------------------------------------------------- % Pour tester la formule de l'esperance on va enlever aléatoirement une % arete graphe = retirer_arete_alea(graphe,n); elseif(choix==4) %------------------------------------------------------------------------- %Créer un arbre en partant du graphe complet taille = n; %------------------------------------------------------------------------- %Création du graphe complet complet = ones(n) - eye(n); complet = sparse(complet); graphe = arbre(complet,n); end

xii


%--------------------------------------------------------------------------% Calcul a faire commun à tous les choix [tab,S] = exact_liste(graphe);diametre = max(tab);donnee = []; %--------------------------------------------------------------------------% Affichage des propriétés du graphe disp('********************************');disp('Nombre de sommets du Graphe :');disp(n);disp('Rayon du Graphe :');disp(min(tab));disp('Diametre du Graphe :');disp(max(tab));disp('********************************'); val = menu('Choix du type de Statistiques','Statistique sur un nombre d''essais','Statistiques à partir de l''ensemble des valeurs possibles du graphe'); if (val==1) [d,dt,pred]=bfs(graphe,1); %-------------------------------------------------------------------------- %Satistiques à partir d'un échantillon r = input('Combien voulez vous de tests : '); for i=1:r donnee = [donnee deux_bfs(graphe)]; end Dmoy=mean(donnee); disp('Valeur moyenne égale à');disp(Dmoy); %-------------------------------------------------------------------------- %Statistiques à partir de l'ensemble des valeurs possibles du grapheelse % Construction des données for i=1:taille temp = S{1,i}; vect = tab(temp); for j=1:length(temp) donnee = [donnee vect(j)]; end end if (choix==3) % Calcul des deux espérances proba_theo = (n-2)*(n-3)/(n*(n-1)); esperance_prat = calcul_esperance(S,n,diametre,tab); esperance_theo = proba_theo + (1-proba_theo) * 2;

xiii


disp('----------- Affichage des différents résultats-----------'); disp('Valeur theorique de l''esperance :');disp(esperance_theo); disp('Valeur calculée de l''esperance :');disp(esperance_prat); else for i=1:taille temp = S{1,i}; vect = tab(temp); for j=1:length(temp) donnee = [donnee vect(j)]; end end end Dmin=min(donnee); Dmax=max(donnee); Dmoy=mean(donnee); % disp('Valeur minimum égale à');disp(Dmin); % disp('Valeur moyenne égale à');disp(Dmoy); % disp('Valeur maximum égale à');disp(Dmax); chx=menu('Souhaitez vous un affichage graphique des résultats','Oui','Non'); if (chx==1) for i=1:length(donnee) y(i)=length(find(donnee==i)); end bar(y,0.1); text(Dmin,0,'Dmin'); text(Dmax,0,'Dmax'); xlabel('Valeur des diamètres retournés'); ylabel('Nombre de fois où on atteint la valeur'); end end

xiv


variation.m

% Script qui va permettre d'explorer le monde des graphes par intervalles% réguliers.% Pour cela :% -On génère au départ un graphe complet à 100 sommets.% -On retire m arêtes% -On calcul le rapport Diametre réel / Moyenne du diametre retourné% -On affiche le résultat graphiquement % Modifications 1 : On va "lisser" les résultats en effectuant une moyenne% sur l'ensemble des valeurs%%% Attributs du graphe clc;clear all; cd('Projet ZZ3/matlab_bgl'); n = 10;test = 1;pas = 1; donnee_temp =[];abs =[];ord_1 =[];ord_2 =[];ord_3 =[]; a = 1980;b = 2000;nb_moy = 10; fid = fopen('resultat_2.txt','wt'); % Création du graphe complet qui sera notre point de départ. complet = ones(n) - eye(n);complet = sparse(complet); for i=a:pas:b for x=1:nb_moy graphe = creation_graphe(n,i,complet); % Procédure de calcul du graphe pour effectuer les statistiques %---------------------------------------------------------------------- % Calcul a faire commun à tous les choix [tab,S] = exact_liste(graphe); diametre = max(tab); donnee = []; %------------------------------------------------------------------

xv


% Procédure de calcul de l'espérance for u=1:n temp = S{1,u}; vect = tab(temp); for j=1:length(temp) donnee = [donnee vect(j)]; end end %On souhaite calculer le pire des valeurs atteignables on cherche %donc le minimum des valeurs possibles valeur_min = min(donnee); donnee_temp = [donnee_temp (diametre / valeur_min)]; end % Calcul de l'espérance temp = mean(donnee_temp); % Calcul du pourcentage de certitude vec = find(donnee_temp == 1); pourcent = length(vec) * 10 ; % Calcul de l'écart type A = donnee_temp - temp; ecart_type = mean(A.*A); graphe_1 = [i temp]; graphe_2 = [i pourcent]; graphe_3 = [i ecart_type]; fprintf(fid,'%f %f %f %f \n',graphe_1,pourcent,ecart_type); ord_1 = [ord_1 temp]; ord_2 = [ord_2 pourcent]; ord_3 = [ord_3 ecart_type]; abs = [abs i]; % Affichage sur la ligne de commande des différents résults disp('--------------------------------------'); disp ('Iteration : ') ; disp(i-a+1); disp ('Rapport diam/ esp (moyenne de 10) ');disp(temp); disp ('Pourcentage de certitude absolue : ');disp(pourcent); disp ('Ecart type de : ');disp(ecart_type); % Réinitialisation des données donnee_temp = []; vec = []; endfclose(fid); % Dessin du premier graphesubplot(2,2,1);plot(abs,ord_1); axis([a b 0.7 2.2]);xlabel('Nombre d''aretes du graphe');ylabel('Diametre réel / Esperance des valeurs possibles retournée par

xvi


l''algo sur 10 valeurs'); % Dessin du deuxième graphesubplot(2,2,2);plot(abs,ord_2); axis([a b 0 100]);xlabel('Nombre d''aretes du graphe');ylabel('pourcentage où l''on est sûr du résultat'); % Dessin du troisième graphesubplot(2,2,3);plot(abs,ord_3); axis([a b 0 max(ord_3)+0.001]);xlabel('Nombre d''aretes du graphe');ylabel('Ecart type');

xvii


variation_ecart.m

% Procédure de calcul du graphe pour effectuer les statistiques %---------------------------------------------------------------------- % Calcul a faire commun à tous les choix [tab,S] = exact_liste(graphe); diametre = max(tab); donnee = []; %------------------------------------------------------------------ % Procédure de calcul des données for u=1:n temp = S{1,u}; vect = tab(temp); for j=1:length(temp) donnee = [donnee vect(j)]; end end %On souhaite calculer le pire des valeurs atteignables on cherche %donc le minimum des valeurs possibles valeur_min = min(donnee); % On calcule enfin l'écart res = diametre - valeur_min ; % Stockage des résultats sous fichier graphe_1 = [i res]; fprintf(fid,'%f %f n',graphe_1); % Stockage de l'abscisse et de l'ordonnée ord_1 = [ord_1 res]; abs = [abs i]; % Affichage sur la ligne de commande des différents résults disp('--------------------------------------'); disp ('Iteration : ') ; disp(i-a+1); disp ('Diametre exact ');disp(diametre); disp ('Ecart ');disp(res); end fclose(fid); % Dessin du grapheplot(abs,ord_1); axis([a b 0 4]);xlabel('Nombre d''aretes du graphe');ylabel('Diametre réel - plus petit diametre retourné par l''algorithme');

xviii


variation_probabilité.m % Script qui va permettre d'explorer le monde des graphes par intervalles% réguliers.% Pour cela :% -On génère au départ un graphe complet à 100 sommets.% -On retire m arêtes% -On calcul la probabilité que le graphe se trompe% -On affiche le résultat graphiquement% -On va stocker le résultat sous le fichier resultat.txt clc;clear all; n = 30;test = 1;pas = 1; donnee_temp =[];abs =[];ord_1 =[]; a = n-1;b = n*(n-1)/2;nb_moy = 10; fid = fopen('resultat_2.txt','wt'); % Création du graphe complet qui sera notre point de départ. complet = ones(n) - eye(n);complet = sparse(complet); for i=a:pas:b graphe = creation_graphe(n,i,complet); % Procédure de calcul du graphe pour effectuer les statistiques %---------------------------------------------------------------------- % Calcul a faire commun à tous les choix [tab,S] = exact_liste(graphe); diametre = max(tab); donnee = []; %------------------------------------------------------------------ % Procédure de calcul de la probabilité %Initialisation du calcul de la probabilité p = 0; for h=1:n %On récupère les sommets echos vec = S{1,h}; l = length(vec); %On évalue la probabilité en tenant compte de la taille du vecteur %contenant les sommets echos p = p + length(find(tab(vec)~=diametre))/l;

xix


end p = p/n; graphe_1 = [i p]; fprintf(fid,'%f %f\n',graphe_1); ord_1 = [ord_1 p]; abs = [abs i]; % Affichage sur la ligne de commande des différents résults disp('--------------------------------------'); disp ('Iteration : ') ; disp(i-a+1); disp ('Probabilité de se tromper ');disp(p); endfclose(fid); % Dessin du grapheplot(abs,ord_1); axis([a b 0 1]);xlabel('Nombre d''aretes du graphe');ylabel('probabilité de se tromper');

xx


C++

Fichier .hpp

xxi


xxii


Fichier .cpp

xxiii


xxiv


xxv


xxvi


xxvii


xxviii


xxix

Documents

Performances de l'algorithme 2-BFS - isima.fr · Remerciements A l’issue de notre projet de fin d’études, nous tenons à remercier chaleureusement Monsieur Christian LAFOREST,