Discussion :

[clement1010]

Bonjour,

J'ai un petit exercice que je n'arrive pas a résoudre. Je dois représenter des graphes afin de réaliser différents algorithmes de coloration.

Voici ma structure :

Code :

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

1
2
3
4
5
6
7
8
9
10
type couleur = 
    | Vierge
    | Couleur of int;;
 
type sommet = 
    {id : int;
     mutable couleur : couleur;
     mutable voisins : sommet list};;
 
type graphe = sommet list;;

Je souhaiterais construire une liste des sommets de mon graphe par dégré décroissant.

Pour cela j'ai la méthode suivante :

Code :

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

1
2
3
let rec listeSommet l = match l with 
|[] -> [] 
|[t::q] -> (t.id,degre_sommet t)::(listeSommet q);;

La fonction "degre_sommet" fonctionne et retourne bien le degré du sommet.


Mon probleme est que ma fonction listeSommet ne fonctionne pas et me retourne : "This expression has type sommet list but is here used with type
sommet list list"


En espérant trouver un peu d'aide,

Clément.

[Ptival]

Code :

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

1
2
3
let rec listeSommet l = match l with 
|[] -> [] 
|[t::q] -> (t.id,degre_sommet t)::(listeSommet q);;

Ton second motif ici correspond à :

Code :

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

1
2
3
4
5
6
7
 
[t::q]
^    ^ une liste contenant un unique élément
  ^^ cet élément est une liste
 ^ dont la tête sera référée via le nom t
    ^ et la queue sera référée via le nom q
(* Grrr! Pourquoi la balise code n'affiche pas en monospace ? >:( *)

Le motif que tu souhaites est le suivant :

Code :

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

1
2
3
let rec listeSommet l = match l with 
|[] -> [] 
|t::q -> (t.id,degre_sommet t)::(listeSommet q);;

C'est à dire une liste dont la tête s'appellera t et la queue s'appellera q.

[clement1010]

Merci beaucoup, j'ai compris mon erreur.

Merci pour ton explication claire et rapide !

[clement1010]

Je voudrais maintenant trier ma liste par ordre de degré décroissant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
let rec listeSommetDecroissant l = match l with
|[] -> [] 
 
|(s1,d1)::[] -> [(s1,d1)]
 
|t::(s1,d1)::(s2,d2)::[] -> if d2 > d1 
then t::(s2,d2)::(s1,d1)::[] 
else t::(s1,d1)::(s2,d2)::[]
 
|t::(s1,d1)::(s2,d2)::q -> if d2 > d1 
then (listeSommetDecroissant (t::(s2,d2)::(s1,d1)::q)) 
else (listeSommetDecroissant ((s1,d1)::(s2,d2)::q));;

Le problème est que lorsque j'arrive a mes deux derniers couple (cas n°3 du 'with') je n'arrive pas a conserver l'intégralité de ma liste triée précédemment, mais uniquement le précédent..

[prgasp77]

Code :

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

1
2
3
4
let listeSommetDecroissant =
   let pair_compare a b = compare (snd b) (snd a) in
   List.sort pair_compare
;;

Pourquoi réinventer la roue ?

[clement1010]

Je ne comprends pas tellement ta réponse...

Voici ce que me rend ma fonction listeSommet :

Code :

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

1
2
# listeSommet gtest;;
- : (int * int) list = [1, 1; 2, 1; 3, 3; 4, 2; 5, 2; 6, 3; 7, 1; 8, 1]

Il s'agit d'une liste de couples (numero sommet,degré sommet).

Je voudrais simplement trier cette liste par degré décroissant.

[prgasp77]

Tu as du mal recopier ma proposition. Quant à son fonctionnement, je te renvoie vers la documentation de la fonction List.sort.

Cdlt,

[clement1010]

Merci, je ne comprenais pas la signification de snd. Maintenant j'ai réussi. Je clos le topic.

Merci à vous deux.

[prgasp77]

Super, maintenant que tu as lu la doc, n'hésite pas à poser des questions . Et pense à ce joli bouton qui s'ennuie dans son coin.