clarkez / karger-algo

Implémentation de l'algorithme de Karger et de Karger-Stein

Karger-Algo

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