Implémentation de l'algorithme de Karger et de Karger-Stein
Afin de compiler le programme il faut utiliser la commande : $ make
puis lancer l'exécutable en utilisant la commande :
$ ./main [-s la taille du graphe]
Une fois le programme lancé, il suffit de suivre les étapes indiqués.
Par exemple :
$ ./main -s 100
L'algorithme que vous souhaitez tester :
1 - Contraction - Structure Matrice
2 - Contraction - Structure Liste
3 - Algorithme de Karger - Structure Matrice
4 - Algorithme de Karger - Structure Liste
5 - Création d'un graphe - Structure Matrice
6 - Création d'un graphe - Structure Liste
$ > 3
1 - Matrice cyclique
2 - Matrice complete
3 - Matrice biparti
4 - Matrice aleatoire
5 - Matrice etoile
$ > 2
1 - Karger
2 - Karger itere
3 - Karger-Stein
$ > 1
Et un graphe montrant l'évolution du temps d'exécution par rapport à la taille du graphe sera affiché, cependant la courbe bleu ne sera pas bon, il ne faut pas en tenir compte.
Il faut le modifier manuellement dans le fichier graph.py à la ligne 31