graphe.cpp

#include "graphe.h"
#include "tas.h"
#include <stdio.h>


//Structure pour la gestion interne de la fonction djik…
Res::Res()
{
 taille = 0 ;
}

Res::~Res()
{
 delete [] parcours ;
 delete [] distances ;
}

void Res::Affiche(FILE * f)
{
 fprintf(f,"Source : %d\n",source) ;
 int i;
 for (i = 0 ; i<taille ; i++)
 {
  if (i!=source)
  {
   fprintf(f,"Parcours a l’envers de %d a %d :\n",source,i) ;
   for(int j=i ; j!=source ; j=parcours[j])
    fprintf(f,"\t%d",j) ;
   fprintf(f,"\t%d\nDistance : %d\n",source,distances[i]) ;
  }
 }
}

Fleche::Fleche()
{}

Fleche::Fleche(Sommet s, int p)
{
 extrem= s ;
 poids=p ;
}

/* Crée une liste de flêches (utile pour la création de rayons)*/
Rayons::Rayons(Fleche f, Rayons * lien)
{
 fleche = f;
 suivant = lien ;
}

Element::Element()
{}

/* Crée une liste d’étoiles (construction du graphe) */
Element::Element(Etoile e, Element * lien)
{
 sommet = e ;
 suivant = lien ;
}

MatriceDouble::MatriceDouble(int * * r, Element * * a)
{
 rep = r ;
 adresse = a;
}

MatriceDouble::~MatriceDouble()
{
 delete [] rep ;
 delete [] adresse ;
}

Bool Graphe::inf_str(int i, int j)
{
 return (((i<j && i>0 && j>0) || (i>0 && j<0)) ? vrai : faux) ;
}

int Graphe::somme(int i, int j)
{
 return ((i>0 && j>0) ? i+j : -1) ;
}

MatriceDouble * Graphe::matricialisation()
{
 int ** rep = new int * [taille] ;
 for (int i=0 ; i<taille ; i++)
  rep[i]=new int [taille] ;
 Element ** adresse = new Element *[taille] ;

 // Initialisation
 for (i=0 ; i<taille ; i++)
 {
  for (int j=0 ; j<taille ; j++)
  {
   if (i!=j)
    rep [i][j] = -1 ;
   else rep [i][i] = 0 ;
  }
 }
 for (Element * l = premier ; l!=NULL ; l=l->suivant)
 {
  /* Parcours des arêtes liées à chaque sommet */
  for (Rayons * s=l->sommet.liste ; s!=NULL ; s=s->suivant)
  {
   rep [l->sommet.sommet] [s->fleche.extrem]=s->fleche.poids ;
  }
  adresse[l->sommet.sommet]= l ;
 }
 return (new MatriceDouble(rep, adresse)) ;
}


Graphe::Graphe(int * * tab, int n)
{
 Element * g = NULL ;
 for(int i = 0 ; i<n ; i++)
 {
  Rayons * r = NULL ;
  Etoile e ;
  for (int j=0 ; j<n ; j++)
  {
   Fleche * f = new Fleche(j,tab[i][j]) ;
   r = new Rayons((*f), r) ;
  }
  e.sommet = i ;
  e.liste = r ;
  g = new Element(e, g) ;
 }
 premier = g ;
 taille = n ;
}

Graphe::Graphe(int * donnees, int n)
{
 Element * g = NULL ;
 int i, k;
 for (i=0,k=0 ; k<n ; k++)
 {
  Rayons * r = NULL ;
  int offset = 2*donnees[i] ;
  Etoile e ;
  int j;
  for (j=1 ; j<offset+1 ; j+=2)
  {
   Fleche f ;
   f.extrem = donnees[i+j] ;
   f.poids = donnees[i+j+1] ;
   r = new Rayons(f,r) ;
  }
  e.sommet = k ;
  e.liste = r ;
  g = new Element(e, g) ;
  i+=j ;
 }
 premier = g ;
 taille = n ;
}

Graphe::~Graphe ()
{
 for (Element * l = premier ; l!=NULL ;)
 {
  Element * temp = l->suivant ;
  for (Rayons * r = (l->sommet).liste ; r!=NULL ; )
  {
   Rayons * tmp = r->suivant ;
   delete r ;
   r = tmp ;
  }
  delete l ;
  l = temp ;
 }
}

Res * Graphe::Djikstra(int source)
{
 Res * resultat = new Res ;
 int * distances = new int [taille] ;
 Sommet * parcours = new int [taille] ;
 Sommet * C = new int [taille-1] ;
 MatriceDouble * m =matricialisation() ;
 for (int k=0 ; k<taille ; k++)
 {
  distances[k]=m->rep[source][k] ;
  parcours[k]=source ;
 }
 // Initialisation de C
 Sommet i, j;
 for (i=0, j=0 ; i<taille ; i++)
 {
  if (i!=source)
  {
   C[j]=i ;
   j++ ;
  }
 }
 Tas * T = new Tas(C, taille-1, (fptr) inf_str, distances, vrai) ;
 T->Tri() ;
 for (i=0 ; i<taille -2; i++)
 {
  Sommet mini = T->ExtrMinimum() ;
  for (Rayons * l = m->adresse[mini]->sommet.liste ; l!=NULL ; l=l->suivant)
  {
   Sommet s = l->fleche.extrem ;
   if (inf_str(somme(m->rep[mini][s] , distances[mini]),distances[s]))
   {
    distances[s]=somme(m->rep[mini][s] , distances[mini]) ;
    parcours[s] = mini ;
    T->Percolation (T->Inverse(s)) ;
   }
  }
 }
 delete m ;
 delete T ;
 delete [] C ;
 resultat->distances = distances ;
 resultat->parcours = parcours ;
 resultat->taille = taille ;
 resultat->source = source ;
 return resultat ;
}

void Graphe::Affiche(FILE * f)
{
 fprintf(f,"Taille : %d\n", taille) ;
 for (Element * l = premier ; l!=NULL ; l=l->suivant)
 {
  fprintf(f,"Sommet : %d\n", (l->sommet).sommet) ;
  for (Rayons * r = (l->sommet).liste ; r!=NULL ; r=r->suivant)
  {
   if (r->fleche.poids!=-1 && r->fleche.extrem!=(l->sommet).sommet)
    fprintf(f,"\tExtremite : %d \n\tPoids : %d \n", r->fleche.extrem, r->fleche.poids) ;
  }
 }
}