ocamlgraph

ocamlgraph est une bibliothèque de graphes pour Objective Caml. Elle présente trois aspects différents:

Elle fournit un module Graph.Pack regroupant une structure de données pour des graphes et de nombreux opérations et algorithmes sur ces graphes.
Il est conseillé de jeter un oeil à ce module en premier lieu pour comprendre le genre de choses fournies par ocamlgraph. Voir aussi le fichier demo.ml.
Ensuite, ocamlgraph fournit plusieurs autres structrures de données pour les graphes, pour ceux qui ne se satisferaient pas de la précédente. Certaines sont persistentes et d'autre impératives. Certaines correspondent à des graphes orientés et d'autres à des graphes non-orientés. Certaines étiquettent les noeuds, d'autres les arêtes, d'autres les deux. etc.
L'interface Sig décrit les signatures des structures de données pour les graphes et les modules Persistent et Imperative fournissent des implantations.
Ces implantations sont écrites sous la forme de foncteurs : on spécifie le type des sommets, des arêtes, de leurs labels, etc. et on récupère alors une structure de données.
Enfin, ocamlgraph fournit plusieurs opérations et algorithmes classiques sur les graphes. Ils sont également écrits comme des foncteurs, c'est-à-dire indépendamment de la structure de données pour les graphes. En conséquence, vous pouvez définir votre propre structure de données et réutiliser tous les algorithmes de cette bibliothèque -- il suffit de fournir quelques opérations telles que l'itération sur tous les sommets, sur tous les successeurs d'un noeud, etc. Voir par exmple le module Path.

Documentation

Parcourir l'API. Note : Tous les modules sont regroupés à l'intérieur d'un unique module Graph. .

FAQ

Articles présentant ocamlgraph :

Exemples de code :

sudoku.ml : résolution du Sudoku en utilisant le module de coloration Coloring
demo_planar.ml : dessine un graphe planaire aléatoire et illustre les parcours en profondeur et en largeur et l'algorithme de Dijkstra
color.ml : dessine un graphe planaire aléatoire et le colorie avec 4 couleurs

Distribution

ocamlgraph est distribué librement, sous la licence GNU Library General Public License version 2, avec une exception concernant l'édition de lien décrite dans le fichier LICENSE.
Il est disponible sous forme de sources :

ocamlgraph-1.3.tar.gz

Vous pouvez accéder à la zone de téléchargement directement. Voici les derniers changements.

Crédits

Auteurs

Contributeurs extérieurs :

Nicolas Ayache
Pierre-Loïc Garoche
Ted Kremenek
Marc Lasson
François Pottier
Vincent Simonet
Matthieu Sozeau
Boris Yakobowski