Vous trouverez dans cette page trois implémentation de mes algorithmes. Le programme de décomposition modulaire est publié sous license GPL. Les programmes de décomposition bi-modulaire sont libres pour un usage non-commercial, pour peu que vous mentionnez l'auteur.

Décomposition modulaire des graphes non-orientés

Vous trouverez ici une implémentation, en langage C, de l'algorithme de décomposition modulaire de Capelle - Habib - Montgolfier - Paul par permutation factorisante. Il est très rapide  ; vous verrez que les graphes de plusieurs millions d'arêtes ne lui font pas peur... pourvu qu'ils tiennent en mémoire vive ! L'algorithme est construit autour d'une unique fonction, decomposition_modulaire. Elle prend en entrée un graphe, codé sous forme de liste d'adjacence, et retourne un pointeur sur la racine de l'arbre de décomposition modulaire du graphe. On peut donc très facilement l'interfacer dans un programme. Un main() d'exemple, décomposition d'un graphe aléatoire G(n,p), est fourni.

Le programme est propre : il n'utilise que malloc comme appel systeme, et libere toutes ses mémoires de travail.
Le mode d'utilisation exact est décrit dans dm.h

L'algorithme est en deux temps : calcul d'une permutation factorisante, puis de l'arbre de décomposition.

Il existe aussi une applet java, non-maintenue et apparament buggée, mais expliquant graphiquement l'algorithme.

Décomposition bimodulaire

Il s'agit d'une nouvelle décomposition de graphes qui adapte la décomposition modulaire aux graphes bipartis.

Plus d'informations

Deux implémentations différentes :

la recherche exhaustive de 2-modules (en temps exponentiel...)

la décomposition canonique, calculée récursivement (en temps polynomial)

La comparaison des deux algorithmes (nombreux fichiers d'exemple en *.bip fournis) permet de constater à quel point la décomposition canonique capture "presque tous" les bimodules du graphe.