Discussion :

[Nemerle]

Bon, je me lance pour la culture dans Haskell, et j'aimerais tout d'abord modéliser un graphe non orienté et non connexe. Et bien sûr, je bute: j'ai pensé à

Code :

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

data Arbre a = Noeud a [Arbre a]

Mais cela ne gère que des arbres connexes. Quelqu'un m'aide?

Ensuite, j'essaierai de mettre en place la détermination de cycles hamiltoniens...

[Nemerle]

Je tente le mécanisme standard, mais il n'y a rien de mieux?

Code :

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

1
2
3
type Id = Int
type Fleche = (Id,Id)
type Graphe = [(Fleche)]

(NB: c'est con d'appeler le chemin qui relie 2 sommets "fleche", mais bon...)

[DrTopos]

Mathématiquement, un graphe est fait des choses suivantes:

- un ensemble, dont les éléments sont appelés sommets,
- un ensemble dont les éléments sont appelés arêtes (ou flèches),
- deux applications du premier ensemble vers le deuxième, qui s'appelle respectivement 'source' et 'but'.

Par conséquent, tu crées deux tables dans une base de données, une pour les sommets et une pour les arêtes, et dans la table des arêtes, tu prévois une colonne 'source' et une colonne 'but'.

Après cela, rechercher les cycles en SQL, ça va peut-être être du sport.... mais il faut voir.

[Jedai]

Pourquoi pas simplement une liste d'Arbre pour représenter un graphe non-connexe ? Par contre avoir un identifiant (par exemple un entier) associé aux noeuds peut-être intéressant pour les distinguer les uns des autres.

As-tu regardé la bibliothèque Data.Graph ? Tu peux lire le source pour voir comment ça a été fait.

--
Jedaï

[Nemerle]

Merci pour la bibliothèque Jedai. Effectivement je peux opter pour une liste de Noeud a [Arbre a], je ne sais pas encore.

L'objectif "ludique" (que je comparerai avec une version .net ), pour appréhender mieux Haskell, c'est le topic

http://www.developpez.net/forums/sho...d.php?t=405083

J'aurais donc

1. A produire la liste des graphes connexes à partir de ma matrice d'équivalence,

2. A générer les cycles hamiltoniens

3. A générer "aléatoirement" d'autres cycles.

Je me demandais juste si quelqu'un avait déjà produit quelque-chose sous Haskell concernant les cycles Hamiltoniens. Encore une fois, mon objectif est de voir la puissance d'Haskell...