Sortie de color si pas de coloriage

[yhamoudi]

D'après ce que j'ai compris, il faut une "vraie" sortie lorsqu'un graphe est coloriable, càd produire un fichier au format graphviz qui contient un graphe colorié (avec des vraies couleurs).

Le prof à mis ces 2 trucs en exemple :

• http://www.graphviz.org/Documentation/dotguide.pdf
• http://perso.ens-lyon.fr/daniel.hirschkoff/P2/code/Graphviz/ (un exemple)

Je pense que pour une k coloration, on pourrait générer k couleurs au hasard (s'assurer qu'elles soient bien distinguables : ne pas générer que des nuances de vert) puis colorier le graphe grâce à l'algo. Quelques infos ici :

• http://stackoverflow.com/questions/17657768/how-to-automate-the-edge-colors-coming-out-of-a-node-in-graphviz

[yhamoudi]

j'ai réussi à obtenir le format voulu, mais un problème subsiste : dans print_answer (dans color.ml), on a besoin d'afficher toutes les arêtes du graphes (avec le format dot ça donne des trucs de la forme : a -- b). Le pb c'est qu'il n'est pas facile de récupérer les arêtes : l'idéal c'est à la sortie du parser où on a exactement la liste des arêtes ; après il y a plein de clauses ajoutées.

Du coup je vois 2 manières de faire :

• on retrouve les arêtes à partir de la cnf. Il faut parcourir bcp de clauses (les clauses de la forme (x1_1, x1_2, x1_3 ...x1_k), et les clauses (non xi_1, non xj_1)...(non xi_k, non xj_k)) alors que juste les clauses (non xi_1, non xj_1) permettent de savoir qu'il y a une arête entre xi et xj.
• ma proposition : on ajoute un champs "ancetre" dans l'objet renommage qui permet de stocker une int list list. Concrètement, ancetre permet de garder une liste qui nous intéresse (pas forcèment une cnf). Ainsi, on stockera en sortie de parser la liste des arêtes, et on s'en sert dans print_answer

Est-ce que la 2ème manière te convient ?

[ilsordo]

Est ce que ça coûte vraiment très cher de tout parcourir? Sinon on peut intégrer une méthode print_answer à renommage (Du coup le module mériterait d'être renommé lui même) qui n'attend que answer. Je peux l'écrire demain si tu veux.

[yhamoudi]

j'essaye de tout re-parcourir et je regarde la vitesse (pour n sommets, m arêtes et k couleurs, il y a n+k*m clauses). on améliorera éventuellement, ça me permet déjà de tester si ma distribution des couleurs est bonne

[yhamoudi]

et voilà : maintenant ça fait des jolis graphes colorés :)

Pour utiliser le prg :

Commande habituelle (ça donne "s Pas de coloriage à %d couleurs" ou une coloriage au format dot) ./resol -color 5 tests/color/myciel3.col

Pour visualiser le graphe colorié : ./resol -color 5 tests/color/myciel3.col > col.dot dot -Tpdf col.dot -o col.pdf Puis ouvrir le pdf

Remarques :

• les couleurs sont aléatoires dont une même exécution du prg va colorier avec des couleurs différentes (mais c'est identique à renommage des couleurs près)

Améliorations ?

• il faudra demander si c'est bien le format attendu (faut-il générer le pdf directement ? que faire qd pas satisfiable ...)
• pour l'instant les fonctions d'affichages ne sont pas super propre (voir fichier color.ml) et j'ai fait une modif dans le main : maintenant print_answer (dans main.ml) prend aussi en argument cnf (pour le donner à print_answer de color). J'ai signalé par (***) l'emplacement des changements

[ilsordo]

Je pense que tout est bon. On pourra éventuellement automatiser la partie affichage dans le script shell par un

./resol -color $@ | dot -Tpdf > tmp
evince tmp
rm tmp

[yhamoudi]

les qqs corrections à apporter encore :

• pb si coloration impossible
• afficher dans le terminal s SAT/UNSAT (suivant la solution) + ouvrir le graphe (colorié ou blanc si impossible)
• possibilité d'enregistrer le graphe dans un fichier ?

[ilsordo]

Je suis en train de regarder à quel point on peut déléguer ça à un script.

[ilsordo]

C'est bon, il s'appelle colorie et fait tout le travail