#include <stdlib.h>
#include <stdio.h>
#include <time.h>




//--------------------------------------Structures Karger---------------------------------------------------






/* Définit une structure pour représenter une arête dans un graphe non pondéré. */
struct Arete {
    int source, destination; // Contient les identifiants des sommets source et destination de l'arête.
};

/* Définit une structure pour représenter un graphe comme une collection d'arêtes. */
struct Graphe {
    int nbSommets, nbAretes; // Stocke le nombre de sommets et d'arêtes dans le graphe.
    struct Arete* arete; // Pointeur vers un tableau d'arêtes.
};

/* Structure pour gérer les sous-ensembles dans l'algorithme union-trouver. */
struct SousEnsemble {
    int parent; // Identifiant du parent dans l'ensemble.
    int rang; // Profondeur de l'arbre de l'ensemble.
};


//-----------------------------Déclarattion fonctions globales---------------------------------------


void Cree_graphe_a_partir_de_fichier(struct Graphe* G, const char* nomFichierGraphe);

//---------------------------Déclaration des fonctions Karger -------------------------------------------



struct Graphe* creerGraphe(int nbSommets, int nbAretes);
int trouverRacine(struct SousEnsemble sousEnsembles[], int i);
void Union(struct SousEnsemble sousEnsembles[], int x, int y);
int coupeMinKarger(struct Graphe* graphe) ;

//-------------------------------Fonctions----------------------------------------------------------


//Fonction pour créer un nouveau graphe avec un nombre spécifié de sommets et d'arêtes


struct Graphe* creerGraphe(int nbSommets, int nbAretes)
{
    // Alloue dynamiquement de la mémoire pour une nouvelle structure Graphe
    struct Graphe* graphe = (struct Graphe*)malloc(sizeof(struct Graphe));
    
  
    graphe->nbSommets = nbSommets;  // Initialise le nombre de sommets du graphe avec la valeur fournie
   
    graphe->nbAretes = nbAretes; // Initialise le nombre d'arêtes du graphe avec la valeur fournie
   
    graphe->arete = (struct Arete*)malloc(nbAretes * sizeof(struct Arete)); // Alloue dynamiquement de la mémoire pour un tableau d'arêtes basé sur le nombre d'arêtes spécifié
   
    return graphe; // Retourne un pointeur vers le graphe nouvellement créé
}








// Fonction qui trouve la racine d'un ensemble noeud 


int trouverRacine(struct SousEnsemble sousEnsembles[], int i) // Définit la fonction trouverRacine, qui trouve la racine de l'ensemble contenant i.

{ 
    if (sousEnsembles[i].parent != i) // Si i n'est pas son propre parent, i n'est pas la racine.
    
    { 
        
        sousEnsembles[i].parent = trouverRacine(sousEnsembles, sousEnsembles[i].parent); // Recherche récursivement la racine de i et applique la compression de chemin.
    }
    return sousEnsembles[i].parent; // Retourne la racine de l'ensemble contenant i.
}



// Fonction qui fait l'union de deux sous ensembles x et y 


void Union(struct SousEnsemble sousEnsembles[], int x, int y)

{
    // Trouve la racine de l'ensemble contenant l'élément x
    int racineX = trouverRacine(sousEnsembles, x);
    // Trouve la racine de l'ensemble contenant l'élément y
    int racineY = trouverRacine(sousEnsembles, y);

    // Compare les rangs des racines des deux éléments
    if (sousEnsembles[racineX].rang < sousEnsembles[racineY].rang) // Si le rang de racineX est inférieur à celui de racineY, fait de racineY le parent de racineX
    {
       
        sousEnsembles[racineX].parent = racineY;
    } else if (sousEnsembles[racineX].rang > sousEnsembles[racineY].rang) // Si le rang de racineX est supérieur à celui de racineY, fait de racineX le parent de racineY
    {
        
        sousEnsembles[racineY].parent = racineX;
    } else  // Si les rangs sont égaux, choisit racineX comme parent de racineY
    {
       
        sousEnsembles[racineY].parent = racineX;
        // Et augmente le rang de racineX puisqu'il a maintenant un sous-arbre supplémentaire
        sousEnsembles[racineX].rang++;
    }
}







//Fonction pour  l'algorithme de Karger.


int coupeMinKarger(struct Graphe* graphe) 

{
   
    int nbSommets = graphe->nbSommets, nbAretes = graphe->nbAretes; // Récupère le nombre de sommets et d'arêtes du graphe donné.
    
    struct Arete* arete = graphe->arete;
   
    struct SousEnsemble* sousEnsembles = (struct SousEnsemble*)malloc(nbSommets * sizeof(struct SousEnsemble)); // Alloue la mémoire pour les sous-ensembles correspondant à chaque sommet.
    
   
    for (int v = 0; v < nbSommets; ++v) // Initialise chaque sous-ensemble pour qu'il soit auto-referent avec un rang initial de 0.
        
    {
        sousEnsembles[v].parent = v;
        sousEnsembles[v].rang = 0;
    }
   
    int nbSommetsRestants = nbSommets; // Initialise le nombre de sommets restants à être contractés.
    
    while (nbSommetsRestants > 2) // Continue de contracter les arêtes tant qu'il reste plus de deux sommets.
    
    {
       
        int i = rand() % nbAretes; // Sélectionne une arête aléatoirement.
       
        int sousEnsemble1 = trouverRacine(sousEnsembles, arete[i].source); // Trouve les racines des sous-ensembles des sommets de l'arête sélectionnée.
        int sousEnsemble2 = trouverRacine(sousEnsembles, arete[i].destination);
      
        if (sousEnsemble1 != sousEnsemble2)   // Contracte l'arête si elle connecte deux sous-ensembles différents.
        {
          
            printf("Contration de l'arête %d-%d\n", arete[i].source, arete[i].destination);  // Affiche l'arête contractée pour information.
            
            nbSommetsRestants--;// Réduit le compteur de sommets restants après la contraction.
           
            Union(sousEnsembles, sousEnsemble1, sousEnsemble2); // Fusionne les deux sous-ensembles en un seul.
        }
    }
    // Compte le nombre total d'arêtes coupées.
    int aretesCoupees = 0;
    for (int i = 0; i < nbAretes; i++) {
        // Vérifie si l'arête actuelle est une coupe entre deux sous-ensembles.
       int sousEnsemble1 = trouverRacine(sousEnsembles, arete[i].source); // Trouve et stocke la racine (ou le représentant) du sous-ensemble contenant le sommet source de l'arête courante.
       int sousEnsemble2 = trouverRacine(sousEnsembles, arete[i].destination); // Trouve et stocke la racine (ou le représentant) du sous-ensemble contenant le sommet destination de l'arête courante.

        if (sousEnsemble1 != sousEnsemble2)
        {
            // Incrémente le compteur d'arêtes coupées.
            aretesCoupees++;
        }
    }
    // Libère la mémoire allouée aux sous-ensembles.
    free(sousEnsembles);
    
    return aretesCoupees; // Retourne le nombre d'arêtes coupées, indiquant la taille de la coupe minimale.
}






int main() 
{

     int nbSommets = 6;  // Nombre de sommets dans le graphe
    int nbAretes = 7;   // Nombre d'arêtes dans le graphe
    struct Graphe* graphe = creerGraphe(nbSommets, nbAretes);

    // Ajout des arêtes. Exemple : (0, 2) représente une arête entre le sommet A et C
    graphe->arete[0].source = 0; graphe->arete[0].destination = 2;
    graphe->arete[1].source = 0; graphe->arete[1].destination = 1;
    graphe->arete[2].source = 1; graphe->arete[2].destination = 2;
    graphe->arete[3].source = 1; graphe->arete[3].destination = 3;
    graphe->arete[4].source = 3; graphe->arete[4].destination = 4;
    graphe->arete[5].source = 4; graphe->arete[5].destination = 5;
    graphe->arete[6].source = 5; graphe->arete[6].destination = 3;

    srand(time(NULL));
    printf("\nLa coupe minimale trouvée par l'algorithme aléatoire de Karger est %d\n", coupeMinKarger(graphe));

    free(graphe->arete);
    free(graphe);

   
    return 0;
}