TP3

Ce projet a été réalisé par Sarah Cherchem et Celia Arezki.

Algorithmes Réalisés :

Nous avons implémenté plusieurs algorithmes d'arbres couvrants aléatoires, dont certains sont présentés de manière similaire mais avec des variantes intéressantes. Voici les algorithmes que nous a vons traités dans ce projet :

3.1 Arbres couvrants de poids minimum aléatoire

Un algorithme simple pour obtenir un arbre couvrant aléatoire. L'idée est de :

1. Attribuer un poids aléatoire à chaque arête dans l'intervalle [0,1].
2. Retourner un arbre couvrant de poids minimum en utilisant l'algorithme de Prim ou Kruskal. (on a utilisé Prim)

3.2 Parcours aléatoire

Effectuer un parcours du graphe en partant d’un sommet aléatoire et choisir les arcs de la frontière au hasard pour définir un arbre couvrant.

3.3 Insertion aléatoire d’arêtes

Construire un arbre couvrant en insérant des arêtes aléatoires, en s'assurant que chaque insertion ne crée pas de cycle, à l'aide de structures de données Union-Find.

3.4 Algorithme d’Aldous-Broder

Cet algorithme consiste à effectuer une marche aléatoire sur le graphe, où l'arbre couvrant est constitué des arêtes qui ont permis d'atteindre chaque sommet pour la première fois.

3.5 Par contraction d’arêtes

Choisir une arête aléatoire, la contracter, puis chercher un arbre couvrant dans le graphe contracté. Cette méthode peut créer des boucles ou des arêtes parallèles, il est donc important de les gérer correctement.

3.6 Algorithme de Wilson

Construire un arbre couvrant en effectuant des marches aléatoires depuis des sommets extérieurs à l'arbre jusqu'à ce qu'ils atteignent un sommet de l'arbre. Ces chemins sont ajoutés à l'arbre.

3.8 Par suppression de cycles

Construire un arbre couvrant en choisissant aléatoirement des arêtes incidentes à chaque sommet et en supprimant les cycles qui peuvent apparaître. ### Pour cette algorithme nous avons commencé son implémentation cependant il reste quelque erreur lié à la logique.

Contenu du projet

Le projet contient les éléments suivants :

1. Classes principales

   • Graph : Structure de base pour représenter les graphes non orientés.
   • Edge et Arc : Représentent respectivement les arêtes et les arcs orientés.
   • RootedTree : Permet d’analyser un arbre enraciné (diamètre, centre, indice de Wiener, etc.).
   • UnionFind : Structure de données pour la gestion des ensembles disjoints, utile dans les algorithmes comme la contraction ou l’insertion aléatoire.

2. Algorithmes de génération d'arbres couvrants

   • Aldous-Broder : Utilise une marche aléatoire pour construire un arbre couvrant uniforme.
   • Prim : Génère un arbre de poids minimum avec des poids aléatoires.
   • Wilson : Marche aléatoire modifiée pour générer des arbres couvrants uniformément.
   • Insertion aléatoire : Ajoute des arêtes aléatoires sans former de cycles.
   • Contraction d'arêtes : Contracte des arêtes aléatoires tout en maintenant la connectivité.
   • Parcours aléatoire (RandomSearch) : Parcours aléatoire à partir d'un sommet pour construire l'arbre.
   • Suppression de cycles : Supprime les cycles formés par des arêtes aléatoirement choisies.

3. Types de graphes pour les tests

   • Grille : Graphe en forme de grille.
   • Complet : Graphe où tous les sommets sont connectés.
   • Erdős-Rényi : Graphe généré avec une probabilité de connexion entre les sommets.
   • Lollipop : Graphe combinant un cycle et un chemin.

4. Visualisation et statistiques

   • Labyrinth : Visualisation des arbres couvrants sous forme de labyrinthe.
   • Stats : Calcul de métriques telles que le diamètre moyen, l’indice de Wiener, et le nombre de feuilles.

1 - AbstractArbreCouvrant (Classe abstraite) :

La classe AbstractArbreCouvrant sert de base pour toutes les implémentations d'algorithmes d'arbres couvrants. Elle contient les éléments communs qui seront utilisés par toutes les classes qui en héritent. Voici ses principales caractéristiques :

Attributs :

protected final Graph graph: Il s'agit d'un objet Graph qui représente le graphe sur lequel l'algorithme doit être exécuté. Ce graphe est passé en paramètre lors de la création de l'objet AbstractArbreCouvrant.

protected final Random generator: Un générateur de nombres aléatoires utilisé dans certaines implémentations d'algorithmes (comme pour l'initialisation des poids dans l'algorithme de Prim). protected final Set arbre: Un ensemble qui contient les arêtes de l'arbre couvrant. Ce set est commun à toutes les implémentations d'algorithmes, et les arêtes de l'arbre sont ajoutées au fur et à mesure de l'exécution de l'algorithme.

2. ArbreCouvrant (Interface) Cette interface définit le contrat que toutes les implémentations d'algorithmes d'arbres couvrants doivent respecter. Elle contient une seule méthode :

• Set arbreCouvrant() : Cette méthode doit être implémentée par toutes les classes dérivées pour générer un arbre couvrant du graphe. Elle retourne un ensemble d'arêtes qui composent l'arbre couvrant.

3. Prim (Algorithme de Prim) La classe Prim hérite de AbstractArbreCouvrant et implémente l'algorithme de Prim pour générer un arbre couvrant minimum dans un graphe. Voici les éléments clés de l'implémentation :

Attributs :

private final Map<Edge, Double> poids: Une carte qui associe à chaque arête du graphe un poids aléatoire. Ces poids sont utilisés pour choisir l'arête de poids minimal à chaque étape de l'algorithme de Prim. private final PriorityQueue queue: Une file de priorité qui contient les arêtes du graphe, triées par leur poids. Cela permet de toujours récupérer l'arête de poids minimal de manière efficace.

Méthodes :

• genererPoidsAleatoires() : Cette méthode attribue un poids aléatoire à chaque arête du graphe. Elle génère un nombre aléatoire entre 0 et 1 pour chaque arête. Le poids est stocké dans la carte poids. Le poids des arêtes est normalisé pour qu'il soit dans l'intervalle [0, 1]. Si le nombre d'arêtes est supérieur à 500, un calcul basé sur le cube du nombre d'arêtes est utilisé pour définir une borne supérieure au poids aléatoire.
• arbreCouvrant() : Cette méthode implémente l'algorithme de Prim pour générer un arbre couvrant. Voici les étapes de l'algorithme :
• Choisir un sommet de départ : L'algorithme commence avec un sommet arbitraire (dans ce cas, le sommet 0). Ajouter les arêtes sortantes du sommet au queue : Toutes les arêtes connectées au sommet de départ sont ajoutées à la file de priorité. Boucle principale : Tant que la queue n'est pas vide, l'algorithme extrait l'arête de poids minimal et vérifie si le sommet de destination de cette arête a déjà été visité. Si ce n'est pas le cas, l'arête est ajoutée à l'arbre couvrant, et toutes les arêtes sortantes du sommet de destination sont ajoutées à la file de priorité. Retourner l'arbre couvrant : Une fois que l'arbre couvrant a été généré, il est retourné sous forme d'un ensemble d'arêtes.

2- Insertion La classe Insertion implémente un algorithme de génération d'arbre couvrant en utilisant une approche de type Kruskal avec un tirage aléatoire des arêtes. Elle évite la formation de cycles grâce à la structure de données Union-Find. L'algorithme procède comme suit :

Mélange aléatoirement les arêtes du graphe. Ajoute une arête à l'arbre couvrant si elle ne forme pas de cycle, en vérifiant la connectivité des sommets avec Union-Find. Répète ce processus jusqu'à ce que l'arbre couvrant contienne 𝑉 − 1 arêtes, où V est le nombre de sommets du graphe. Cette approche est simple et efficace pour la génération d'arbres couvrants dans des graphes non orientés.

3- AldousBroder La classe AldousBroder implémente un algorithme de génération d'arbre couvrant basé sur la marche aléatoire. L'algorithme fonctionne de la manière suivante :

Un sommet initial est choisi aléatoirement. L'algorithme effectue une marche aléatoire en sélectionnant des arcs sortants du sommet actuel jusqu'à ce que tous les sommets aient été visités. Lorsqu'un nouveau sommet est visité pour la première fois, l'arête menant à ce sommet est ajoutée à l'arbre couvrant. L'algorithme continue cette marche jusqu'à ce que l'arbre couvrant contienne tous les sommets du graphe. Cet algorithme est basé sur la marche aléatoire de type Aldous-Broder et garantit la construction d'un arbre couvrant. Il est particulièrement efficace dans les graphes aléatoires.

4- Wilson : La classe Wilson implémente un algorithme de génération d'arbre couvrant appelé algorithme de Wilson. Cet algorithme est basé sur la marche aléatoire, et il est plus spécifique que d'autres algorithmes comme celui de Prim ou Kruskal. Voici une explication détaillée du fonctionnement de cet algorithme :

Description de l'algorithme de Wilson :

Initialisation :

L'algorithme commence avec un ensemble de sommets visités (sommetVisite) qui est initialement vide. Il crée une map (outArc) pour stocker les arêtes rencontrées lors des marches aléatoires. Itérations sur les sommets :

L'algorithme traite les sommets du graphe un par un, en choisissant d'abord un sommet de départ (ici, les sommets sont triés en fonction de leur degré, du plus grand au plus petit). Si un sommet n'a pas encore été visité, il commence une marche aléatoire depuis ce sommet pour rejoindre un sommet déjà visité.

Marche aléatoire :

À chaque étape de la marche, un sommet est choisi au hasard parmi les voisins du sommet courant. L'algorithme enregistre les arêtes empruntées dans une map (outArc) pour pouvoir retracer le chemin lorsque la marche atteint un sommet déjà visité.

Retour sur le chemin parcouru :

Une fois qu'une marche atteint un sommet déjà visité, l'algorithme commence à retracer le chemin parcouru en marquant chaque sommet comme visité et en ajoutant chaque arête à l'arbre couvrant (arbre).

Terminaison :

Ce processus continue jusqu'à ce que tous les sommets aient été visités, ce qui garantit que l'arbre couvrant contient tous les sommets du graphe. Points importants : Marche aléatoire : La caractéristique de l'algorithme de Wilson repose sur la marche aléatoire qui démarre à un sommet choisi au hasard et avance jusqu'à ce qu'elle atteigne un sommet déjà visité. Complexité : L'algorithme de Wilson est un peu plus complexe que les algorithmes de Prim ou Kruskal, mais il garantit un arbre couvrant de manière probabiliste.

5- Recherche Aléatoire : La classe RandomSearch implémente un algorithme de recherche aléatoire pour générer un arbre couvrant. Voici une explication détaillée du fonctionnement de cet algorithme :

Description générale de l'algorithme : L'algorithme RandomSearch fonctionne en explorant le graphe de manière aléatoire. Voici les étapes principales :

Initialisation :

Un sommet de départ est choisi aléatoirement parmi les sommets du graphe. Ce sommet est ajouté à l'ensemble des sommets visités. La liste des arcs à explorer (frontier) est initialement vide, mais elle est remplie avec les arcs sortants du sommet de départ.

Exploration aléatoire :

L'algorithme fonctionne tant qu'il reste des arcs dans la liste frontier à explorer. À chaque itération, un arc est choisi au hasard parmi ceux disponibles dans frontier (la liste est mélangée aléatoirement avec Collections.shuffle). Si l'arc mène à un sommet qui n'a pas encore été visité, cet arc est ajouté à l'arbre couvrant, et ce sommet est marqué comme visité. Tous les arcs sortants du sommet destination de l'arc choisi sont ajoutés à la liste frontier pour être explorés plus tard.

Terminaison :

L'algorithme continue jusqu'à ce que tous les sommets aient été visités. Cela garantit que l'arbre couvrant contient tous les sommets du graphe, mais peut contenir un nombre d'arêtes supérieur au minimum nécessaire.

6- Contraction :

1. ContractionGraph : Cette classe est responsable de la gestion du graphe après la contraction des arêtes. Lorsqu'une arête est contractée, elle relie deux sommets ensemble en une seule entité (un sommet "combiné"), supprimant ainsi l'arête contractée et réarrangeant le graphe.

Attributs principaux :

incidence : Une liste de listes (LinkedList). Chaque liste correspond à un sommet et contient les indices des arêtes incidentes à ce sommet. extrimite1 et extrimite2 : Listes qui contiennent respectivement les sommets de départ et d'arrivée pour chaque arête dans le graphe. initialEdges : Liste des arêtes initiales du graphe. Méthodes principales : ContractionGraph(Graph graph) : Le constructeur initialise les listes incidence, extrimite1, extrimite2 et initialEdges en parcourant toutes les arêtes du graphe. Il ajoute chaque arête à ces listes et associe les indices des arêtes aux sommets correspondants dans incidence.

boucle(int indexEdge) : Cette méthode vérifie si une arête est une boucle (c'est-à-dire si elle relie un sommet à lui-même). Elle retourne true si les deux extrémités de l'arête sont le même sommet.

contract(int edgeIndex) : Cette méthode contracte une arête spécifiée par edgeIndex. Si l'arête n'est pas une boucle, elle relie les deux sommets qu'elle connecte. Tous les arcs incident au deuxième sommet sont réajustés pour pointer vers le premier sommet, et les arêtes sont modifiées en conséquence pour refléter cette contraction dans la structure de données du graphe.

getInitialEdges(), getExtrimite1(), getExtrimite2() : Ces méthodes retournent respectivement les listes des arêtes initiales et des extrémités des arêtes. Elles sont utilisées pour obtenir des informations sur le graphe initial après la contraction.

2. Contraction : Cette classe implémente l'algorithme de contraction d'arêtes pour créer un arbre couvrant. Elle utilise
3. ContractionGraph pour gérer les contractions des arêtes et UnionFind pour détecter et éviter les cycles
4. lors de la construction de l'arbre couvrant.

Attributs principaux : contractionGraph : Instance de la classe ContractionGraph utilisée pour gérer le graphe après contraction des arêtes. unionFind : Instance de l'algorithme Union-Find (ou Disjoint Set Union), utilisée pour suivre et gérer les connexions entre les sommets et éviter de former des cycles dans l'arbre couvrant. nodes : Un tableau de Node, où chaque Node contient des informations sur la profondeur et la hauteur de chaque sommet. Cependant, ces informations ne sont pas utilisées dans cette version du code. Méthodes principales : Contraction(Graph graph) : Le constructeur initialise les objets contractionGraph (pour la gestion des contractions) et unionFind (pour suivre les connexions entre les sommets). Il initialise également le tableau nodes, bien qu'il ne soit pas utilisé dans cette version du code.

arbreCouvrant() : Cette méthode implémente l'algorithme de contraction pour générer un arbre couvrant. Les étapes sont les suivantes :

Initialisation des arêtes : Une liste edges est remplie avec les indices des arêtes du graphe. Mélange des arêtes : Les arêtes sont mélangées de manière aléatoire pour assurer que l'algorithme ne suit pas un ordre fixe. Parcours des arêtes : Pour chaque arête, si l'arête est une boucle, elle est ignorée. Si les sommets reliés par l'arête sont déjà connectés dans l'arbre (vérifié par unionFind.find()), l'arête est ignorée pour éviter les cycles. Ajout de l'arête à l'arbre couvrant : Si l'arête relie deux sommets non connectés, elle est ajoutée à l'arbre couvrant. Union des sommets : Les sommets reliés par l'arête sont unis (avec unionFind.union()). Contraction de l'arête : L'arête est contractée dans le graphe (avec contractionGraph.contract()). À la fin, l'algorithme retourne l'ensemble arbre, qui contient les arêtes de l'arbre couvrant généré.

Classe interne Node : Cette classe représente un sommet avec deux propriétés :

depth : La profondeur du sommet dans l'arbre. Cependant, dans ce code, elle reste à 0 et n'est pas utilisée. height : La hauteur du sommet. Comme la profondeur, elle n'est pas utilisée ici. Interaction entre les classes : ContractionGraph gère la structure interne du graphe après chaque contraction d'arête. Elle suit les modifications des arêtes et des sommets, en ajustant les indices et en évitant de créer des boucles.

Contraction utilise ContractionGraph pour manipuler le graphe en cours et pour générer l'arbre couvrant. Elle se repose également sur UnionFind pour garantir que l'algorithme ne crée pas de cycles en ajoutant des arêtes.

Comparaison des résultats pour chaque algorithme :

1. Algorithme Prim : Excentricité moyenne : 70.30 Indice de Wiener moyen : 1,599,399,905 Diamètre moyen : 263 Nombre moyen de feuilles : 1,228 Nombre moyen de sommets de degré 2 : 2,729 Temps de calcul moyen : 38,686,424 ms

2. Algorithme Aldous :

   Excentricité moyenne : 112.54 Indice de Wiener moyen : 2,219,478,278 Diamètre moyen : 424 Nombre moyen de feuilles : 1,514 Nombre moyen de sommets de degré 2 : 2,330 Temps de calcul moyen : 38,690,744 ms

3. Algorithme Insertion : Excentricité moyenne : 104.01 Indice de Wiener moyen : 2,038,044,944 Diamètre moyen : 387 Nombre moyen de feuilles : 1,583 Nombre moyen de sommets de degré 2 : 2,226 Temps de calcul moyen : 38,694,069 ms

4. Recherche Aléatoire : Excentricité moyenne : 53.80 Indice de Wiener moyen : 1,193,672,822 Diamètre moyen : 207 Nombre moyen de feuilles : 1,670 Nombre moyen de sommets de degré 2 : 2,084 Temps de calcul moyen : 38,698,474 ms

   

5. Algorithme Contraction :

   Excentricité moyenne : 106.99 Indice de Wiener moyen : 2,081,870,127 Diamètre moyen : 424 Nombre moyen de feuilles : 1,577 Nombre moyen de sommets de degré 2 : 2,234 Temps de calcul moyen : 38,704,749 ms

6. Algorithme Wilson : Excentricité moyenne : 127.26 Indice de Wiener moyen : 2,487,683,163 Diamètre moyen : 500 Nombre moyen de feuilles : 1,515 Nombre moyen de sommets de degré 2 : 2,340 Temps de calcul moyen : 38,709,040 ms

Analyse des résultats : Excentricité :

• L'algorithme Recherche aléatoire reste celui avec la plus basse excentricité moyenne (53.80), indiquant une meilleure uniformité dans la distribution des sommets. Wilson génère l'arbre avec la plus grande excentricité (127.26), suggérant des arbres plus "étendus"
• Indice de Wiener : Wilson a l'indice de Wiener le plus élevé (2,487,683,163), ce qui montre que les arbres générés par Wilson ont des distances plus longues entre certaines paires de sommets. L'algorithme Recherche aléatoire a l'indice de Wiener le plus bas (1,193,672,822), indiquant des arbres avec des distances plus courtes en moyenne.

-Diamètre : Wilson génère des arbres avec le diamètre le plus élevé (500), ce qui correspond à l'excentricité et à l'indice de Wiener élevés. Recherche aléatoire a le diamètre le plus bas (207), correspondant à sa faible excentricité et indice de Wiener

-Nombre de feuilles : L'algorithme Recherche aléatoire génère le plus grand nombre de feuilles (1,670), suggérant des arbres plus ramifiés. Aldous a le nombre de feuilles le plus faible (1,514), indiquant des arbres plus concentrés. -Nombre de sommets de degré 2 : Prim a le plus grand nombre de sommets de degré 2 (2,729), ce qui pourrait refléter des arbres plus équilibrés. Wilson et Contraction ont des résultats similaires (2,340 et 2,234), avec un nombre modéré de sommets de degré 2.

-Temps de calcul : Les temps de calcul pour tous les algorithmes sont relativement proches (environ 38.7 millions de millisecondes en moyenne), avec une légère variation qui pourrait être influencée par les spécificités des algorithmes et de l'implémentation.

Conclusion :

Recherche aléatoire semble générer des arbres avec des caractéristiques plus équilibrées (faible excentricité, faible indice de Wiener et diamètre), et un plus grand nombre de feuilles. Wilson génère des arbres plus étendus avec un diamètre plus élevé, une excentricité plus grande et un indice de Wiener élevé. Contraction et Aldous génèrent des arbres plus proches en termes de métriques, mais Wilson et Prim se distinguent par des arbres ayant un diamètre plus large et une plus grande dispersion des sommets. Les algorithmes comme Prim et Aldous semblent produire des arbres plus réguliers tandis que Wilson et Contraction génèrent des arbres plus "étendus", avec des métriques plus élevées.

Comparaison des algorithmes

Métriques évaluées

• Diamètre moyen : Distance maximale entre deux sommets.
• Indice de Wiener : Somme des distances entre toutes les paires de sommets.
• Distribution des degrés : Proportion des sommets ayant un degré donné.

Observations

• Aldous-Broder : Produit des arbres couvrants uniformément mais peut être lent sur de grands graphes.
• Prim : Rapide pour les graphes denses, mais les poids aléatoires influencent les résultats.
• Wilson : Garantit une distribution uniforme tout en étant plus efficace qu'Aldous-Broder.
• Insertion aléatoire : Simple à implémenter mais sensible à l'ordre des arêtes.
• Contraction : Efficace mais plus complexe à coder.
• Suppression de cycles : Produit des arbres non uniformes avec un bon compromis entre qualité et performance.

---

Limitations

• Certains algorithmes (par ex. contraction d'arêtes) peuvent être inefficaces pour les très grands graphes.
• Les visualisations sont limitées à certains types de graphes comme les grilles.

Ressources utilisées

• PDF - Math.ENS.PSL
• Site d'Olivier Pons - Aldous-Broder
• • Consigne du TP : [Lien vers le document fourni]
• Documentation Java officielle : [https://docs.oracle.com/en/java/]
• Structure Union-Find : [https://en.wikipedia.org/wiki/Disjoint-set_data_structure]