L3 Informatique I6S3 Graphes

Projet 2017 : Coloration gloutone itérée

Le sujet.

Inscription pour le projet : avant le 10 avril par mél, sujet "inscription projet graphes" et indiquer le binome. Après quelques jours, vérifiez que vous apparaissez sur le tableau ci-dessous.

Le rapport et la démonstration du projet :

• démos le mercredi 3 mai et jeudi 4 mai
• La démonstration dure 10 minutes: 5 minutes de présentation + 5 minutes de questions.
• Vous devez être prêt quelques minutes avant l'heure de passage (vérifiez que votre application fonctionne sur les PC de la salle auparavant !).
• synthèse de 4 pages maximum à rendre au moment de la soutenance et comprenant :
  • bref rappel de la problématique et des enjeux
  • structures et algorithmes mis en oeuvre (ne détailler que les plus pertinents)
  • résultats produits : par exemple sous forme de tableau avec les valeurs trouvées
  • limitations de la version actuelle et possibilités d'extension/amélioration

Questions/Réponses :

Q : On lit le fichier avec le graphe.On applique DSATUR qui nous retournent une certaine coloration. On applique Glouton avec le nombre de couleur que DSATUR nous a retourné. Jusque là je pense que je suis ok par contre je ne comprends pas l'histoire des inversion de couleurs.

R : Oui c'est bien ça jusqu'à DSATUR. Ensuite si le tableau de couleurs obtenu est par exemple : 3 1 2 2 1 3 3 4 2 1 1 3 1 Pour permuter les couleurs 1 et 2, il faut tester s'il y a un sommet x de couleur 1 qui n'a pas de voisins de couleur 2. Si c'est le cas, on inverse les couleurs 1 et 2, c'est à dire que l'on relance l'algo glouton en lui donnant comme ordre des sommets d'abord les sommets coloriés 2, ensuite ceux coloriés 1 (donc le sommet x sera colorié 1), puis les sommets des autres couleurs dans l'ordre des couleurs ensuite. Sur cet exemple (avec les sommets numérotés entre 0 et 12) on pourra lui donner l'ordre 2, 3, 8, 1, 4, 9, 10, 12, 0, 5, 6, 11, 7

Q : Est-il possible d'utiliser le C# pour réaliser notre projet ?

R : Oui vous pouvez

Q : - Quand vous dites "On se propose donc de partir d’une coloration obtenue par DSATUR et d’effectuer plusieurs itérations en permutant `a chaque fois deux couleurs." Si mon graphes est en 2 parties de cette forme :image sur wikipedia qui est le plus petit graphe à tromper DSATUR sur son nombre chromatique. Alors Glouton itéré ne trouverais pas le bon nombre non plus car il faudrait faire le changement nécessaire sur les 2 parties.

- Deuxième question, alors que mon algo semblait bien fonctionnait notamment avec le graphe précédent puisque lorsque que DSAT trouve 4 couleurs, mon algo en trouve 3 comme color exact, or dès que j'ai tenté de balancer un graphe des liens que vous nous avez passé dans le sujet, j'ai eu des résultats hallucinant. Comme DSAT qui trouve 38, et glouton qui trouve 40 et color exact qui confirme 40 mais met énormément de temps (j'ai jamais attendu assez) pour tester 39. Une idée de la provenance de ce genre de bug ?

R : Oui, je rappelle qu'à priori il n'y a aucun algorithme capable de trouver une coloration optimale en temps raisonnable pour des graphes relativement grands comme celui que tu as testé. Donc c'est normal que le glouton itéré ne donne pas l'optimal et que colorExact tourne pendant trop longtemps (pour tester si le graphe est coloriable en 39 couleurs, cela peut faire 250^39 configurations, c'est très très grand !). Dsatur est souvent pas mauvais. Pour faire d'autres tests, tu peux prendre les exemples pour lesquel on connait le nombre chromatique (colonne "best K/X" dans les tableaux, je ne sais pas ce que représente le K, mais le X est le nb chromatique).

Q : Est-il possible que Glouton itéré trouve plus de couleur que DSAT ?

R : oui, glouton itéré n'est pas forcément toujours meilleur que DSATUR, cela dépend d'ailleurs de la façon d'itérer (choix des permutations, nombre d'itérations)

Q : Glouton itéré doit-il trouvé la meilleure coloration (pour des petits graphes) ou juste pareil ou mieux que DSAT ? (par rapport à colorexact)

R : le projet doit vous permettre de vous faire une idée de l'efficacité de glouton itéré en terme de compromis entre temps d'exécution et optimalité de la solution trouvé et par rapport à DSATUR qui est un des meilleurs algorithmes de coloration rapide.

Q : Nous avons un problème pour finir le projet de graphe : Pour la dernière question il faut permettre à l'utilisateur de sauvegarder la meilleur coloration en cours d'exécution. Le problème que nous avons est que nous n'arrivons pas à récupérer ce que l'utilisateur écrit dans le terminal sans stopper l'exécution. Pourriez-vous nous dire comment faire ?

''R : Il y a plusieurs solutions, par ex : - utiliser les signaux (vous avez du voir leur utilisation en SR) - utiliser des threads - sauver périodiquement toutes les x itérations - demander à l'utilisateur à chaque meilleure solution trouvée''