Discussion :

[clement1010]

Je suis face à un problème que je n'arrive pas à résoudre, celui de faire la coloration des sommets d'un graphe avec dsatur.

Mon problème est que je n'arrive pas a le programmer récursivement car l'ordre des sommets à colorier est modifiée après chaque coloration d'un sommet. Or je ne sais pas comment faire pour avoir de la récursivité.

J'espère avoir été clair dans l'explication de mon problème, en espérant trouver de l'aide..

[Yo Eight]

Pourquoi pas passer par un catamorphisme ?

[clement1010]

Ne connaissant pas le catamorphisme, j'ai essayé de comprendre un petit peu, mais je t'avouerai que ce n'est pas facile à comprendre...

Voici ce que j'ai fais pour le moment :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let dsatur g = 
	let l = listeCouple3Decroissant (listeSommetDegre g) in 
		let rec boucle l = match l with
		|[] -> []
		|t::q -> colorierSommet (fst3(t)) (minCouleur (fst3(t))) AND boucle (supprimerTripletListe t l)

Dans 'l', j'ai une liste de sommet ordonnée ainsi [(3,2,2);(2,2,1);(5,1,2)] avec dans l'ordre (id sommet,dsat sommet,degré sommet). Ainsi je connais le premier sommet que je dois colorier.

Aussi, fst3 (a,b,c) -> a

Et enfin supprimerTripletListe (a,b,c) liste -> supprimer le triplet de la liste.


Donc mon problème est de boucler sur une liste qui doit être recalculée à chaque fois pour prendre en compte les colorations effectuées précédemment.

[Yo Eight]

Je ne connais pas la syntaxe OCaml mais voila l'idée:

Un catamorphisme est un pattern de récursivité qui enchaine ces étapes:

destruction -> récursivité -> construction

on va définir un type qui représentera notre catamorphisme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
type Cata x a = (a, x -> a -> a)

maintenant implémentons une fonction qui accepte un catamorphisme et l'applique sur une liste:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
cata_liste :: Cata x a -> [x] -> a
cata_liste (a, f) = cata where
  cata [] = a
  cata (x:xs) = f x (cata xs)

cette fonction nous permet par exemple de ne pas avoir à gérer la récursivité directement et prend
une fonction en paramètre pour l'appliquer à chaque élément de la liste. Ce qui en fait une fonction d'ordre supérieur.

Un cas trivial serait par exemple de faire la somme d'une liste comme suit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
cata_liste (0, (+)) [1,2,3]
res = 6

Ta fonction de coloriage pour être de type x -> a -> a ou x serait un sommet et "a" une information qui pourrait être utile

[clement1010]

Merci bien pour ton explication, cela me semble plus clair maintenant.

Cependant, j'ai quelques soucis pour mettre tout cela en ocaml...

J'ai essayé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

type cata x a = (a, x -> a -> a);;

mais j'ai une erreur de syntaxe au niveau du premier 'x'.

J'espère que quelqu'un pourra m'aider concernant la déclaration du type, ainsi que de la fonction cata_liste.

[prgasp77]

Les paramètre de type se notent 'typeparam et se placent avant le nom du type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

type ('x, 'a) cata = 'a * 'x -> 'a -> 'a

Bonne continuation.

[gasche]

prgasp77 > étant donné que le conseil de Yo Eight est essentiellement inutile, je ne vois pas trop l'intérêt de pousser le débutant dans cette voie. Je comprends que tu n'aies pas le temps de rédiger une vraie explication à partir du problème de départ, mais le pousser dans un cul de sac pédagogique me semble aggravant plutôt qu'aidant.

clement1010 > je ne comprends pas ce qui te pose problème et franchement ta question n'est pas très bien formulée / compréhensible. Dans le code que tu montres, la liste 'l' est bien changée à chaque itération puisque tu lui appliques supprimerTripletListe avant l'appel récursif. Est-ce que tu veux juste ajouter un appel à listeCouple3Decroissant à cet endroit ?

Au passage en Caml on évite lesNomsDeVariableEcritsCommeCa, on trouve que les_noms_de_variables_ecrits_comme_ca c'est plus lisible.

[Yo Eight]

@gasche

Il y a une erreur dans ce que j'ai écrit ? Pourrais-tu (au moins) dire en quoi mon intervention était inutile sachant quelle n'oblige à rien, d'où le "pourquoi pas" au début ?

[gasche]

On a un débutant qui a du mal avec les bases et tu lui balances des mots grecs compliqués, du code abstrait dans un langage qu'il ne connaît pas, et une approche qui ne va probablement pas l'aider (s'il ne sait pas coder la version récursive directe je ne vois pas pourquoi il aurait plus de facilités à écrire le catamorphisme...) en plus d'être déjà disponible dans la bibliothèque standard :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

val List.fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

Par ailleurs vu la tête du problème il n'est pas du tout clair qu'un catamorphisme soit la bonne approche puisqu'à chaque étape on a besoin d'accéder au graphe complet.

[clement1010]

Merci gasche de m'aider, en effet je suis débutant en caml donc cette histoire de catamorphisme m'a fait un peu peur !

Est-ce que tu veux juste ajouter un appel à listeCouple3Decroissant à cet endroit ?

Oui c'est exactement ce que je veux faire, j'ai essayé ça, mais j'ai une erreur de syntaxe à la fin du programme au niveau des doubles points virgule.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
let dsatur (g:graphe) =
	let l = listeCouple3Decroissant (listeSommetDegre g) in
	let rec boucle l = match l with
	|[] -> []
	|t::q -> 
		let t = fst3(List.hd l) in
		let s = Hashtbl.find tableSommets ("s" ^ (string_of_int(t))) in 
		colorierSommet s (minCouleur s);
		boucle (listeCouple3Decroissant(supprimerTripletListe t l ));;

Ma syntaxe est donc incorrecte, mais je ne sais de quel côté chercher...

[gasche]

Tu as oublié terminer la déclaration de "boucle" et de l'utiliser.

Tu as écrit

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let truc =
  let rec boucle =
    ... ;;

Ce n'est pas correct. Il faut écrire (en ignorant les commentaires) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let truc =
  let rec boucle = 
    ...
  in (* fin de la déclaration locale de "boucle" *)
  ... (* code qui utilise 'boucle' *)
;; (* fin de la phrase qui déclare globalement 'truc' *)

[Yo Eight]

On a un débutant qui a du mal avec les bases et tu lui balances des mots grecs compliqués, du code abstrait dans un langage qu'il ne connaît pas.

Je suis d'accord avec toi sur ce point, bien que je ne considère pas un catamorphisme réservé aux 'expérimentés' (j'ai pris soin de l'expliquer), mais j'ai bien annoncé que je ne connaissais pas la syntaxe OCaml, donc rien ne justifiait une critique aussi lapidaire.

Par ailleurs vu la tête du problème il n'est pas du tout clair qu'un catamorphisme soit la bonne approche puisqu'à chaque étape on a besoin d'accéder au graphe complet.

Je ne suis pas d'accord, enfin pas totalement. c'est possible si la fonction ('a -> 'b -> 'b) est récursive. Mais c'est vrai qu'un paramorphisme serait plus adapté.

(s'il ne sait pas coder la version récursive directe je ne vois pas pourquoi il aurait plus de facilités à écrire le catamorphisme...)

justement non, car il n'aurait pas à ce soucier du premier niveau de récursivité (le parcours de la liste), juste à se concentrer sur la méthode de dessin.

Bref, tes arguments sont parfaitement recevables mais rien ne justifiait ton impolitesse.

[gasche]

Un paramorphisme ne sert à rien ici puisqu'on n'utilise jamais le calcul `boucle q` directement, le rappel récursif est toujours précédé d'un traitement.

Bref, tes arguments sont parfaitement recevables mais rien ne justifiait ton impolitesse.

J'ai été agacé par le fait de voir quelqu'un répondre à un débutant d'une façon qui empire sa situation au lieu de l'aider.

Je te présente mes excuses pour la rudesse de mes propos, tout en profitant pour te mettre, métaphoriquement parlant, un bon coup de pied au cul : si tu considères vraiment que parler de catamorphisme ou paramorphisme ou zygofuturomorphisme peut aider un débutant qui a du mal à coder une fonction de premier ordre avec récursion directe, il faut que tu revoies ta méthode pédagogique. Prends ça comme un bon conseil plutôt qu'une attaque.

clement1010 > il reste des maladresses dans ton code : ta définition `let t = List.hd l` est inutile juste après le motif `t::q`, puisque `t` vaut déjà la tête de `l` et `q` sa queue (du coup tu n'as pas forcément besoin non plus de l'appel à supprimer_triplet_liste, `q` convient peut-être non ?).

Par ailleurs, comme je ne sais pas ce que font colorier_sommet et liste_couples_decroissant, je n'ai aucune idée de si ton code est correct. On peut t'aider avec les problèmes de syntaxe mais tu vas devoir t'occuper de tester le code.

[clement1010]

Merci à vous deux tout de même, je viens de finir et j'ai réussi !

Pour le peu de gens a qui ca pourrait servir, voici le résultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
let rec colorationDsatur l = match l with
	|[] -> []
	|t::q -> 
		let f = fst3(t) in
		let s = Hashtbl.find tableSommets ("s" ^ (string_of_int(f))) in 
		colorierSommet s (minCouleur s);
		colorationDsatur (listeCouple3Decroissant(supprimerTripletListe f l ));;	
 
 
let dsatur (g:graphe) =
	let l = listeCouple3Decroissant (listeSommetDsatDegre g) in
	colorationDsatur l;;