composantes_MC.cpp

#include <stdio.h>
#include <time.h>
#include <conio.h>
#include <malloc.h>
#include <iostream>
#include <list>
#include <stack>
using namespace std;

//  Définition de la classe Classes_FC pour le calcul
// de la forme canonique de la matrice de transition
class Classes_FC{
    public:
    //Les donées
    int nbr_etats;          // Nombre d'états
    int nc; //numero de la classe
    float MTr[100][100];    // Matrice de transition
    float MFC[100][100];    // Matrice sous form canonique
    int index, indd, indf;              //Pour l'ordre de visite des sommets
    list <int> *Successeurs;//Liste des successeurs
    list <int> *CFC;        //Liste des classes Fortement connect
    int *OFC;      //Tableau pour L'ordre des etats dans FC
    int *rang;              //Tableau pour L'ordre de visite dans la recherche en profondeur
    int *ret;               //Tableau pour Le plus petit retour au sommet precedent
    int *Num_CFC;           //Tableau pour Le numéro de la classe Fortement connect
    bool *visite;           //Tableau pour indiquer si un sommet est visité ou non
    bool *dans_pile;        //Tableau pour indiquer si un sommet est dans la pile ou non
    stack <int> *pile_CFC;      //variable de type pile

    //Constructeur
    Classes_FC( int n );

    //**************************************
    //   Méthodes de la classe
    //**************************************
    //Affichage de la matrice de transition
    void Afficher_MTr( );
    void Afficher_MFC( );

    //Lecture de la matrice de transition a partir du clavier
    void lire_MTr_clavier( );

    //Lecture de la matrice de transition a partir d'un fichier
    void lire_MTr_fichier(  char *nom_fichier, int n );

    // charge de la liste des successeur a partir de la matrice de transition
    void charge_liste_successeurs();

    // Affichage de la liste des successeur
    void affiche_liste_successeurs();

    //Recherche de tous les composantes FCF
    void Tarjan();

    //Recherche en profondeur des CFC accessible par le sommet s0
    bool DFS_Tarjan( int s0);

    void Enleve_CFC( int s0, bool Tr_s);
    void Calcul_MFC();
};

//*********** Constructeur ***************
//   Allocation dynamique des donnees   **
//****************************************
Classes_FC::Classes_FC( int n ){
    nbr_etats=n;
    indd=0; indf=n-1;
    Successeurs = new list<int>[n];
    rang= new int[n];
    OFC= new int[n];
    ret= new int[n];
    Num_CFC= new int[n];
    visite= new bool[n];
    dans_pile= new bool[n];
    pile_CFC = new stack<int>();
}

//****************************************************
// Affichage au clavier de la matrice de transition **
//****************************************************
void Classes_FC::Afficher_MTr( ){
    for( int i=0; i<nbr_etats; i++){
        for( int j=0; j<nbr_etats; j++){
            printf("%5.2f ", MTr[i][j]);
        }
        printf("\n");
    }
}

//****************************************************
// Affichage au clavier de la matrice de transition **
//****************************************************
void Classes_FC::Afficher_MFC( ){
    for( int i=0; i<nbr_etats; i++){
        for( int j=0; j<nbr_etats; j++){
            printf("%5.2f ", MFC[i][j]);
        }
        printf("\n");
    }
}

//**************************************************
// Lecture au clavier de la matrice de transition **
//**************************************************
void Classes_FC::lire_MTr_clavier(){
    for( int i=0; i<nbr_etats; i++){
        for( int j=0; j<nbr_etats; j++){
            printf( "entrer P(%d,%d):", i+1,j+1);
            scanf("%f", &MTr[i][j]);
        }
    }
}

//****************************************************************
// Lecture de la matrice de transition a partir d'un fichier    **
//  *Les données sont sous format texte, separées par un espace **
//****************************************************************
void Classes_FC::lire_MTr_fichier(char *nom_fichier, int n){
    FILE *p;
    p=fopen(nom_fichier, "rt");
    for( int i=0; i<n; i++){
        for( int j=0; j<n; j++){
            fscanf(p,"%f ", &MTr[i][j]);
        }
        fscanf(p,"\n");
    }
    fclose(p);
}

//****************************************************
//  Chargement de la liste des successeurs a partir **
// de la matrice de transition                      **
//****************************************************
void Classes_FC::charge_liste_successeurs(){
    for( int i=0; i<nbr_etats; i++){
        for( int j=0; j<nbr_etats; j++){
            if( MTr[i][j] !=0 ){
                Successeurs[i].push_back(j);
            }
        }
    }
}

//*****************************************
// Affichage de la liste des successeurs **
//*****************************************
void Classes_FC::affiche_liste_successeurs(){
    list<int>::iterator p; //pointeur sur une liste simplement chainee
    for( int i=0; i<nbr_etats; i++){
        printf("Successeurs(%d)=",i);
        for(  p=Successeurs[i].begin(); p!=Successeurs[i].end(); p++){
            printf( "%d ", (*p+1));
        }
        printf("\n");
    }
}

//*********************************************************
// Recherche en profondeur de toutes les CFCs            **
//  1. Initialisation des données                        **
//  2. Parcourt des tous les sommets                     **
//  3. Appel de la fonction récursif DFS_Tarjan(int s0)  **
//*********************************************************
void Classes_FC::Tarjan(){
  // Fonction à completé
  for( int i=0; i<nbr_etats; i++){
    visite[i]=false;
    dans_pile[i]=false;
  }
  index=1; nc=0;
  for( int i=0; i<nbr_etats; i++){
    if( visite[i] == false){
        DFS_Tarjan(i);
    }
  }

}

//****************************************************************
// Recherche en profondeur des CFCs accéssibles a partir de s0  **
//  Recherche basé sur la liste des successeurs                 **
//****************************************************************
bool Classes_FC::DFS_Tarjan(int s0){
  // Fonction à completé
  rang[s0]=index; ret[s0]=index;
  index++;
  pile_CFC->push(s0);
  bool Tr_s=false;
  visite[s0]=true;
  dans_pile[s0]=true;
  list<int>::iterator p; //pointeur sur une liste simplement chainee
  for(p=Successeurs[s0].begin(); p!=Successeurs[s0].end(); p++){
    int x=*p;
    if( visite[x]==false){
      bool Tr_x=DFS_Tarjan(x);
      if( Tr_x==true ) Tr_s=true;
      if(ret[x]<ret[s0]) ret[s0]=ret[x];
    }
    else if ( dans_pile[x]==true){
      if(rang[x]<ret[s0]) ret[s0]=rang[x];
    }
    else {  Tr_s=true; }
  }
  if ( ret[s0]==rang[s0]){ Enleve_CFC(s0, Tr_s); return true; }

  return Tr_s;
}

//depilement de la CFC
void Classes_FC::Enleve_CFC( int s0, bool Tr_s){
     if( Tr_s ==true ) printf("\n Classe transitoire: ");
     else              printf("\n Classe recurente : ");
     int si;
     do{
      si=(int)pile_CFC->top();
      printf("%d ", si+1);
      if( Tr_s ==true ){ OFC[indf]=si; indf--;}
      else            { OFC[indd]=si; indd++;}
      pile_CFC->pop();
      Num_CFC[si]=nc;
      dans_pile[si]=false;
     }while( si != s0);
     nc++;
}
// Calcul de la matrice de transition dans
// sa forme canonique à partir de l'ordre
// des états (OFC[]) dans cette forme
void Classes_FC::Calcul_MFC(){
    for( int i=0; i<nbr_etats; i++){
        for(int j=0;j<nbr_etats; j++){
            MFC[i][j]=MTr[OFC[i]][OFC[j]];
        }
    }
}

int main (){
    int nbr_etats;
    printf("entrer n:");
    scanf("%d",&nbr_etats);
    Classes_FC SCC(nbr_etats);

    //SCC.lire_MTr_clavier();
    SCC.lire_MTr_fichier("test1.txt",nbr_etats );
    printf(" Matrice de transition:\n");
    SCC.Afficher_MTr();
    SCC.charge_liste_successeurs();
    //SCC.affiche_liste_successeurs();
    SCC.Tarjan();
    SCC.Calcul_MFC();
    printf(" \n Ordre dans CF:");
    for(int i=0;i<nbr_etats; i++){
        printf("%d ", SCC.OFC[i]+1);
    }
//  printf(" \n indd=%d  et indf=%d\n", SCC.indd, SCC.indf);
    printf(" \nMatrice de transition sous forme canonique:\n");
    SCC.Afficher_MFC();
    //SCC.Tarjan();



    getch();
}