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

#define NB_INSTANCES 20

int long_max_spf, long_max_spf_tmp, tps_spf_partiel, val_spf_partielle;

typedef struct {//definit une arete (sommet1,sommet2) valuee par poids
	int sommet1;//numero sommet1
	int sommet2;//numero sommet2
	int poids;
} arete;

typedef struct {
	int source;//source < puits
	int puits;
	int longueur_chemin;//longueur d'un chemin reliant la source au puits
	int *sommets_chemin;//liste des sommets de ce chemin
} liaison;

typedef struct {
	int nb_sommets;//nb sommets du graphe
	int nb_liaisons;//nb liaisons du graphe
	int *liste_adjacence;//l'element i*nb_sommets+j contient le poids de l'arete entre le sommet i+1 et le sommet j+1, 0 si l'arete a ete saturee, -1 si elle n'existe pas
	liaison *liste_liaisons;
} graphe;

//fin declaration types

int alea(int x) {//generateur de nb pseudo-aleatoires
	return ((int) ((rand() % x)+1));
}

int sp_segmentation(arete *tab, int inf, int sup) {
	int pivot, i, j;
	arete tmp;
	pivot=tab[inf].poids;
	i=inf+1;
	j=sup;
	while(i<=j) {
		if(tab[i].poids>=pivot)
			i++;
		else {
			if(tab[j].poids<pivot)
				j--;
			else {
				if(i<j) {
					tmp=tab[i];
					tab[i]=tab[j];
					tab[j]=tmp;
					i++;
					j--;
				}
			}
		}
	}
	tmp=tab[inf];
	tab[inf]=tab[j];
	tab[j]=tmp;
	return j;
}

void quicksort(arete *tab, int inf, int sup) {
	int place;
	if(inf<sup) {
		place=sp_segmentation(tab,inf,sup);
		quicksort(tab,inf,place-1);
		quicksort(tab,place+1,sup);
	}
}

arete *tri_par_quick_sort(graphe G) {//effectue un tri par segmentation (ordre decroissant des poids) sur les aretes de G
	int i, j, taille, extremite;
	arete tmp;
	arete *tab_tmp;
	taille=G.nb_sommets*G.nb_sommets;
	tab_tmp=(arete *)malloc(taille*sizeof(arete));
	for(i=0;i<G.nb_sommets;i++) {
		for(j=0;j<G.nb_sommets;j++) {
			tab_tmp[i*G.nb_sommets+j].sommet1=i+1;
			tab_tmp[i*G.nb_sommets+j].sommet2=j+1;
			tab_tmp[i*G.nb_sommets+j].poids=G.liste_adjacence[i*G.nb_sommets+j];
		}
	}
	extremite=taille-1;
	for(i=0;i<extremite;i++) {
		while(extremite>=0&&tab_tmp[extremite].poids==-1)
			extremite--;
		if(i<extremite&&tab_tmp[i].poids==-1) {//traitement preliminaire : on met toutes les aretes de poids -1 a la fin du vecteur
			tmp=tab_tmp[i];
			tab_tmp[i]=tab_tmp[extremite];
			tab_tmp[extremite]=tmp;
		}
	}
	quicksort(tab_tmp,0,extremite);
	return tab_tmp;
}

int test_arete(int *liste_sommets, int taille, arete ar) {//teste si arete peut etre ajoutee, etant donnees les composantes connexes donnees par le tableau liste_sommets de taille "taille"
	int i, old_cc;
	if(liste_sommets[ar.sommet1-1]!=liste_sommets[ar.sommet2-1]) {//sommet1 et sommet2 ne sont pas dans la meme composante connexe
		old_cc=liste_sommets[ar.sommet2-1];
		for(i=0;i<taille;i++)//pour tout sommet i
			if(liste_sommets[i]==old_cc)//si i etait dans la meme composante connexe que sommet2
				liste_sommets[i]=liste_sommets[ar.sommet1-1];//il est maintenant dans la meme composante connexe que sommet1
		return 1;
	}
	else
		return 0;
}

void connexifier(graphe *G, int nb_l, int dens, int num_inst, int cm) {//ajoute des aretes au graphe cree par Rudy pour le rendre connexe. Les aretes ajoutees (de capa max cm) sont stockees dans un fichier
	int *liste_sommets;
	arete *liste_aretes;
	int i, j, old_cc, taille, poids;
	char filename[2000];
	FILE *f;
	taille=G->nb_sommets*G->nb_sommets;
	liste_sommets = (int *)malloc((G->nb_sommets)*sizeof(int));
	liste_aretes=tri_par_quick_sort(*G);//on trie les aretes de G
	sprintf(filename,"aretes_pour_connexifier_n%d_L%d_d%d_%d.txt", G->nb_sommets, nb_l, dens, num_inst);
	f=fopen(filename,"w");
	for(i=0;i<G->nb_sommets;i++)
		liste_sommets[i]=i;//initialement, chaque sommet a sa propre composante connexe
	for(i=0;i<taille;i++) {//pour chaque arete dans liste_aretes
		if(liste_aretes[i].poids>0) {//si c'est une arete deja existante : on la laisse
			old_cc=liste_sommets[liste_aretes[i].sommet2-1];
			for(j=0;j<G->nb_sommets;j++)//pour tout sommet j
				if(liste_sommets[j]==old_cc)//si j etait dans la meme composante connexe que sommet2
					liste_sommets[j]=liste_sommets[liste_aretes[i].sommet1-1];//il est maintenant dans la meme composante connexe que sommet1
		}
		else {
			if(test_arete(liste_sommets, G->nb_sommets, liste_aretes[i])) {
				poids=alea(cm);
				G->liste_adjacence[(liste_aretes[i].sommet1-1)*G->nb_sommets+liste_aretes[i].sommet2-1]=poids;
				G->liste_adjacence[(liste_aretes[i].sommet2-1)*G->nb_sommets+liste_aretes[i].sommet1-1]=poids;
				fprintf(f,"%d %d %d\n",liste_aretes[i].sommet1,liste_aretes[i].sommet2,poids);
			}
		}
	}
	free(liste_sommets);
	free(liste_aretes);
	fclose(f);
}

void kruskal(graphe G, graphe *MST) {//prend un graphe et renvoie un MST. Le graphe doit être connexe !
	int i, j, taille, nb_aretes_ajoutees=0;
	int *liste_sommets;
	arete *liste_aretes;
	liste_sommets = (int *)malloc((G.nb_sommets)*sizeof(int));
	taille=G.nb_sommets*G.nb_sommets;

	for(i=0;i<taille;i++)
		MST->liste_adjacence[i]=-1;//initialement, aucune arete dans MST
	for(i=0;i<G.nb_sommets;i++)
		liste_sommets[i]=i;//initialement, chaque sommet a sa propre composante connexe
	liste_aretes=tri_par_quick_sort(G);//on trie les aretes de G
	for(i=0;(i<taille)&&(nb_aretes_ajoutees<G.nb_sommets-1);i++) {//on doit ajouter exactement n-1 aretes
		if(test_arete(liste_sommets, G.nb_sommets, liste_aretes[i])) {//la ieme arete peut etre ajoutee, car elle ne cree pas de cycle
			MST->liste_adjacence[(liste_aretes[i].sommet1-1)*G.nb_sommets+(liste_aretes[i].sommet2-1)]=liste_aretes[i].poids;//on ajoute l'arete dans MST
			MST->liste_adjacence[(liste_aretes[i].sommet2-1)*G.nb_sommets+(liste_aretes[i].sommet1-1)]=liste_aretes[i].poids;//on ajoute l'arete dans MST
			nb_aretes_ajoutees++;
		}
	}
	free(liste_sommets);
	free(liste_aretes);
}

void bfs(graphe G, int *file_sommets, int *niveaux_sommets) {//effectue une bfs : on gère la file à l'aide d'un tableau ayant un nb de cases égal au nb de sommets. file_sommets contient les sommets dans l'ordre d'ajout dans la file, et niveaux_sommets les niveaux des sommets par rapport a la racine. On ne gère pas les graphes non connexes !!!
	int *sommets_marques;//tableau ou l'element i vaut 0 si le sommet i n'a pas encore ete visite, 1 sinon
	int sommet_courant;//contient le no du sommet courant
	int indice_sommet_courant=0;//contient l'indice dans la file du sommet courant examine
	int i, premiere_case_libre;//contient l'indice de la premiere place libre dans la file

	sommets_marques = (int *)malloc((G.nb_sommets)*sizeof(int));
	file_sommets[0]=alea(G.nb_sommets);//on commence le parcours a partir d'un sommet tire au hasard (sinon, on peut mettre "file_sommets[0]=1")
	for(i=0;i<G.nb_sommets;i++)//tous les autres sommets sont non marqués
		sommets_marques[i]=0;
	sommets_marques[file_sommets[0]-1]=1;//le 1er sommet dans la file est marque (sinon, on peut mettre "sommets_marques[0]=1")
	premiere_case_libre=1;//la premiere case libre est la no 1 (i.e., la 2e)
	niveaux_sommets[file_sommets[0]-1]=0;//le premier sommet dans la file est à distance 0 de lui-même (sinon, on peut mettre "niveaux_sommets[0]=0")
	while(premiere_case_libre<G.nb_sommets) {//tant qu'on n'a pas examine tous les sommets
		sommet_courant=file_sommets[indice_sommet_courant];
		for(i=0;i<G.nb_sommets;i++) {//pour l'ensemble des aretes issues du sommet courant
			if(G.liste_adjacence[(sommet_courant-1)*G.nb_sommets+i]>-1) {//il y a une arete entre sommet_courant et i
				if(sommets_marques[i]==0) {//i est visite et ne l'avait pas deja ete
					sommets_marques[i]=1;//il est a present marque
					niveaux_sommets[i]=niveaux_sommets[sommet_courant-1]+1;//le niveau de sommet2 est 1 de plus que celui du sommet courant
					file_sommets[premiere_case_libre]=i+1;//on l'ajoute dans la file
					premiere_case_libre++;
				}
			}
		}
		indice_sommet_courant++;//ok car le graphe est connexe
	}
	free(sommets_marques);
}

int chemin_source_vers_puits_via_bfs(graphe G, liaison liaison_courante, int *predecesseurs_sommets) {//bfs commencee a partir de la source de liaison, et poursuivie jusqu'au puits. Retourne 0 si il n'y a pas de chemin entre source et puits, 1 sinon.
	int *file_sommets;//contient les sommets dans l'ordre d'ajout dans la file
	int *sommets_marques;//tableau ou l'element i vaut 0 si le sommet i n'a pas encore ete visite, 1 sinon
	int sommet_courant;//contient le no du sommet courant
	int indice_sommet_courant=0;//contient l'indice dans la file du sommet courant examiné
	int i, premiere_case_libre;//contient l'indice de la premiere place libre dans la file

	file_sommets = (int *)malloc((G.nb_sommets)*sizeof(int));
	sommets_marques = (int *)malloc((G.nb_sommets)*sizeof(int));
	for(i=0;i<G.nb_sommets;i++)//tous les sommets sont non marqués
		sommets_marques[i]=0;
	for(i=0;i<G.nb_sommets;i++)//aucun sommet dans la file
		file_sommets[i]=-1;
	for(i=0;i<G.nb_sommets;i++)//aucun sommet n'a de predecesseur
		predecesseurs_sommets[i]=-1;
	file_sommets[0]=liaison_courante.source;//on commence le parcours a partir de la source
	sommets_marques[liaison_courante.source-1]=1;//le sommet 1 (dans la case 0) est marqué (c-a-d mis a 1)
	premiere_case_libre=1;//la premiere case libre est la no 1
	while(predecesseurs_sommets[liaison_courante.puits-1]==-1) {//tant qu'on n'a pas examine le puits de liaison
		sommet_courant=file_sommets[indice_sommet_courant];
		for(i=0;i<G.nb_sommets;i++) {//pour l'ensemble des aretes issues du sommet courant
			if(G.liste_adjacence[(sommet_courant-1)*G.nb_sommets+i]>0) {//on a une arete (sommet_courant,i)
				if(sommets_marques[i]==0) {//i+1 est visite et ne l'avait pas deja ete
					sommets_marques[i]=1;//il est a present marque
					file_sommets[premiere_case_libre]=i+1;//on l'ajoute dans la file
					predecesseurs_sommets[i]=sommet_courant;//sommet_courant est le predecesseur de i
					premiere_case_libre++;
					if(i==liaison_courante.puits-1)
						return 1;
				}
			}
		}
		if(indice_sommet_courant==G.nb_sommets-1||file_sommets[indice_sommet_courant+1]==-1)//il n'y a plus de sommet a visiter dans la file, donc on a echoue (les 2 sommets ne sont pas dans la meme composante connexe)
			return 0;
		indice_sommet_courant++;
	}
	free(file_sommets);
	free(sommets_marques);
	return 1;
}

int longueur_chemin(int *predecesseurs, liaison l) {//renvoie la longueur (en nb de sommets) du chemin reliant la source de l a son puits, et contenu (au milieu d'autres infos) dans le tableau predecesseurs
	int sommet_courant, i, longueur_chemin=1;
	sommet_courant=l.puits;
	while(sommet_courant!=l.source) {//tant qu'on n'est pas arrive a la source de l
		sommet_courant=predecesseurs[sommet_courant-1];
		longueur_chemin++;
	}
	return longueur_chemin;
}

int sommets_chemin(int *predecesseurs, liaison *l, int *niveaux) {//renvoie le no du lca ("least common ancestor") de la source et du puits de l
	int sommet_courant, lca, nb_sommets_ajoutes=0;
	sommet_courant=l->puits;//on part du puits
	lca=l->puits;//on part du puits
	while(sommet_courant!=l->source) {//tant qu'on n'est pas arrive a la source de l
		l->sommets_chemin[nb_sommets_ajoutes]=sommet_courant;
		sommet_courant=predecesseurs[sommet_courant-1];
		if(niveaux!=NULL&&niveaux[sommet_courant-1]<niveaux[lca-1])
			lca=sommet_courant;
		nb_sommets_ajoutes++;
	}
	l->sommets_chemin[nb_sommets_ajoutes]=l->source;//on ajoute la source en dernier
	return lca;
}

int diminuer_capacites(graphe *G, int *chemin, int longueur) {//longueur en nb de sommets. On met G a jour en diminuant toutes les aretes de chemin de la plus petite capacite rencontree
	int i, min;
	min=G->liste_adjacence[(chemin[0]-1)*G->nb_sommets+(chemin[1]-1)];
	for(i=0;i<longueur-1;i++)//on calcule le min des capacites sur chemin
		{if(min>G->liste_adjacence[(chemin[i]-1)*G->nb_sommets+(chemin[i+1]-1)])
			min=G->liste_adjacence[(chemin[i]-1)*G->nb_sommets+(chemin[i+1]-1)];}
	for(i=0;i<longueur-1;i++) {//on met a jour
		G->liste_adjacence[(chemin[i]-1)*G->nb_sommets+(chemin[i+1]-1)]-=min;
		G->liste_adjacence[(chemin[i+1]-1)*G->nb_sommets+(chemin[i]-1)]-=min;
	}
	return min;
}

int algo_H1(graphe *G) {//renvoie la valeur du multiflot calculé par l'algo. H1. Il suffit d'appeler cette fonction tant que cette valeur n'est pas nulle !
	graphe *Arbre;
	int i, j, gain, indice_courant, max_niveau=0, valeur_flot=0;
	int *liste_lca;
	int *niveaux;
	int *file;
	int *predecesseurs;
	liste_lca=(int *)malloc(G->nb_liaisons*sizeof(int));
	file = (int *)malloc((G->nb_sommets)*sizeof(int));
	niveaux = (int *)malloc((G->nb_sommets)*sizeof(int));
	predecesseurs = (int *)malloc((G->nb_sommets)*sizeof(int));
	Arbre = (graphe *)malloc(sizeof(graphe));
	Arbre->liste_adjacence = (int *)malloc((G->nb_sommets*G->nb_sommets)*sizeof(int));
	Arbre->liste_liaisons = G->liste_liaisons;
	Arbre->nb_liaisons = G->nb_liaisons;
	Arbre->nb_sommets = G->nb_sommets;

	kruskal(*G,Arbre);
	bfs(*Arbre, file, niveaux);//on enracine l'arbre (MST)
	for(i=0;i<G->nb_liaisons;i++)//on initialise les lca
		liste_lca[i]=-1;
	for(i=0;i<G->nb_sommets;i++) {//on calcule le niveau max de l'arbre enracine
		if(niveaux[i]>max_niveau)
			max_niveau=niveaux[i];
	}
	for(i=0;i<G->nb_liaisons;i++) {//on calcule les chemins de chacune des liaisons
		if(chemin_source_vers_puits_via_bfs(*Arbre, Arbre->liste_liaisons[i], predecesseurs)) {//si le chemin existe (via une bfs issue de chaque source, jusqu'au puits), on calcule le lca
			Arbre->liste_liaisons[i].longueur_chemin=longueur_chemin(predecesseurs, Arbre->liste_liaisons[i]);
			Arbre->liste_liaisons[i].sommets_chemin=(int *)malloc(Arbre->liste_liaisons[i].longueur_chemin*sizeof(int));
			liste_lca[i]=sommets_chemin(predecesseurs, &(Arbre->liste_liaisons[i]), niveaux);//on calcule le chemin de chaque liaison dans Arbre
		}
	}
	indice_courant=G->nb_sommets-1;//on parcourt les sommets dans l'ordre inverse de leur ajout dans la file lors de la bfs
	for(i=max_niveau;i>=0;i--) {//on parcourt niveau par niveau
		while(indice_courant>=0&&niveaux[file[indice_courant]-1]==i) {//tant que c'est un sommet du niveau i (et qu'il reste des sommets)
			for(j=0;j<G->nb_liaisons;j++) {//pour chaque liaison
				if(liste_lca[j]==file[indice_courant]) {//le lca de la liaison j est le sommet courant de la file, au niveau i
					gain=diminuer_capacites(G,Arbre->liste_liaisons[j].sommets_chemin,Arbre->liste_liaisons[j].longueur_chemin);//on met a jour les aretes du chemin de la liaison j
					diminuer_capacites(Arbre,Arbre->liste_liaisons[j].sommets_chemin,Arbre->liste_liaisons[j].longueur_chemin);
					valeur_flot+=gain;//on met a jour le flot
				}
			}
			indice_courant--;
		}
	}
	free(liste_lca);
	free(niveaux);
	free(file);
	free(predecesseurs);
	free(Arbre->liste_adjacence);
	free(Arbre);
	return valeur_flot;
}

int iterer_H1(graphe *G) {//implemente H'1 : itere H1 jusqu'a ce que plus aucune unite de flot ne puisse etre routee. Retourne le flot total.
	int flot_total=0, augmentation=1;
	while(augmentation) {
		augmentation=algo_H1(G);
		flot_total+=augmentation;
	}
	return flot_total;
}

int spf(graphe *G, int nb_l, int dens, int num_inst, int long_ref, int chemins_courts, int temps_reference, int temps_debut, int val_flot_ref) {//implemente l'algo. approche SPF. Renvoie la valeur du flot calcule. long_ref est la longueur max pour les chemins que l'on considère : on la prend égale à log en base 10 de nb_sommets (soit 2 pour nb_sommets=50, et 3 pour nb_sommets=150,300 ou 500)
	int i, j, long_min, liaison_courante, gain=1, valeur_flot=0, comparer_val_ref=1, comparer_tps_ref=1, initialise=0;
	long temps_actuel;
	int *predecesseurs;
	char filename[2000];
	predecesseurs = (int *)malloc((G->nb_sommets)*sizeof(int));

	while(gain>0) {
		gain=0;
		long_min=G->nb_sommets+1;
		liaison_courante=-1;
		if(initialise&&comparer_val_ref&&val_flot_ref&&valeur_flot>=val_flot_ref) {//si on a depasse la valeur du flot obtenu par H2, on note le temps ecoule
			tps_spf_partiel+=temps_actuel-temps_debut;
			comparer_val_ref=0;
		}
		if(initialise&&comparer_tps_ref&&temps_reference&&(temps_actuel-temps_debut >= temps_reference)) {//si on a depasse le temps mis par H2, on note la valeur de la solution courante
			val_spf_partielle+=valeur_flot;
			comparer_tps_ref=0;
		}
		for(i=0;i<G->nb_liaisons;i++) {//on calcule le chemin de chacune des liaisons
			if(chemin_source_vers_puits_via_bfs(*G, G->liste_liaisons[i], predecesseurs)) {//si le chemin existe, on le calcule
				G->liste_liaisons[i].longueur_chemin=longueur_chemin(predecesseurs, G->liste_liaisons[i]);
				G->liste_liaisons[i].sommets_chemin=(int *)malloc(G->liste_liaisons[i].longueur_chemin*sizeof(int));
				sommets_chemin(predecesseurs, &(G->liste_liaisons[i]), NULL);//on calcule le chemin de chaque liaison dans G
				if(long_min>G->liste_liaisons[i].longueur_chemin) {//on trouve la liaison avec le plus court chemin
					long_min=G->liste_liaisons[i].longueur_chemin;
					liaison_courante=i;
				}
			}
		}
		if(liaison_courante!=-1&&((!chemins_courts)||long_min<=long_ref)) {
			gain=diminuer_capacites(G,G->liste_liaisons[liaison_courante].sommets_chemin,G->liste_liaisons[liaison_courante].longueur_chemin);
			valeur_flot+=gain;//on met a jour le flot (et les capacites)
			if(G->liste_liaisons[liaison_courante].longueur_chemin > long_max_spf_tmp) {
				long_max_spf_tmp=G->liste_liaisons[liaison_courante].longueur_chemin;
			}
		}
		if(!initialise)
			initialise=1;
		time(&temps_actuel);
	}
	if(comparer_tps_ref&&temps_reference)// si SPF est plus rapide que H2, il faut neanmoins garder en memoire la valeur de la solution qu'il renvoie
		val_spf_partielle+=valeur_flot;
	free(predecesseurs);
	return valeur_flot;
}

void creer_liaisons_graphe(graphe *g, int nb_l, int dens, int num_inst){//va lire dans "liaisons.txt" la liste des liaisons creee par "initialiser_liaisons_graphes"
	int i, s, t;
	FILE *f;
	char filename[2000];

	sprintf(filename, "liaisons_n%d_L%d_d%d_%d.txt", g->nb_sommets, nb_l, dens, num_inst);
	f=fopen(filename,"r");

	fscanf(f,"%d\n",&i);//la premiere ligne contient uniquement le nb de liaisons
	for(i=0;i<g->nb_liaisons;i++)
		g->liste_liaisons[i].longueur_chemin=-1;
	i=0;
	while(fscanf(f,"%d %d\n",&s,&t)==2) {//format lignes suivantes : faire une boucle while
		g->liste_liaisons[i].source=s;//stocker ces infos dans liste_liaisons
		g->liste_liaisons[i].puits=t;
		i++;
	}
	fclose(f);
}

void initialiser_liaisons_graphes(int nb_sommets, int nb_liaisons, int dens, int num_inst) {//utilise alea pour creer la liste des liaisons
	int i=0, s, t;
	FILE *f;
	char filename[2000];

	sprintf(filename, "liaisons_n%d_L%d_d%d_%d.txt", nb_sommets, nb_liaisons, dens, num_inst);
	f=fopen(filename,"w");

	fprintf(f,"%d\n",nb_liaisons);
	while(i<nb_liaisons) {
		s=alea(nb_sommets);
		t=alea(nb_sommets);
		if(s!=t) {
			if(s<t)
				fprintf(f,"%d %d\n",s,t);
			else//t<s
				fprintf(f,"%d %d\n",t,s);
			i++;
		}
	}
	fclose(f);
}

void creer_graphe(graphe *g, int nb_sommets, int nb_l, int dens, int num_inst, int a_connexifier) {//cree une instance de graphe ayant nb_l liaisons. Contient les instructions pour aller lire le graphe cree par Rudy (sans les liaisons), et initialiser la structure graphe.
	FILE *f;
	int i, j, poids;
	char filename[2000];

	sprintf(filename, "graphe_n%d_L%d_d%d_%d.txt", nb_sommets, nb_l, dens, num_inst);
	f=fopen(filename,"r");

	fscanf(f,"%d %d\n",&i,&j);//format premiere ligne
	g->nb_sommets=i;
	g->nb_liaisons=nb_l;
	g->liste_adjacence = (int *)malloc(i * i * sizeof(int));//on cree une matrice de taille nb_sommets*nb_sommets
	for(i=0;i<g->nb_sommets;i++)
		for(j=0;j<g->nb_sommets;j++)
			g->liste_adjacence[i+g->nb_sommets*j]=-1;
	while(fscanf(f,"%d %d %d\n",&i,&j,&poids)==3) {//format lignes suivantes : faire une boucle while
		g->liste_adjacence[(i-1)+g->nb_sommets*(j-1)]=poids;//stocker ces infos dans la bonne case de liste_adjacence
		g->liste_adjacence[(j-1)+g->nb_sommets*(i-1)]=poids;//stocker ces infos dans la bonne case de liste_adjacence
	}
	fclose(f);
	if(a_connexifier) {//si la liste des aretes necessaires pour connexifier le graphe est deja disponible dans un fichier, on utilise ces infos
		sprintf(filename, "aretes_pour_connexifier_n%d_L%d_d%d_%d.txt", g->nb_sommets, nb_l, dens, num_inst);
		f=fopen(filename,"r");
		while(fscanf(f,"%d %d %d\n",&i,&j,&poids)==3) {//format lignes suivantes : faire une boucle while
			g->liste_adjacence[(i-1)+g->nb_sommets*(j-1)]=poids;//stocker ces infos dans la bonne case de liste_adjacence
			g->liste_adjacence[(j-1)+g->nb_sommets*(i-1)]=poids;//stocker ces infos dans la bonne case de liste_adjacence
		}
		fclose(f);
	}
	g->liste_liaisons = (liaison *)malloc(g->nb_liaisons*sizeof(liaison));
}

void generer_fichiers_dat_et_run_ampl(graphe *G, int nb_l, int dens, int num_inst) {
	FILE *f;
	char filename[2000];
	int i, j;

	sprintf(filename, "graphe_n%d_L%d_d%d_%d.dat", G->nb_sommets, nb_l, dens, num_inst);
	f=fopen(filename,"w");
	fprintf(f,"set nodes :=");
	for(i=1;i<=G->nb_sommets;i++)
		fprintf(f," %d", i);
	fprintf(f,";\n");
	fprintf(f,"param K := %d;\n", nb_l);
	fprintf(f,"param orig :=");
	for(i=0;i<nb_l;i++)
		fprintf(f," %d %d", i+1, G->liste_liaisons[i].source);
	fprintf(f,";\n");
	fprintf(f,"param dest :=");
	for(i=0;i<nb_l;i++)
		fprintf(f," %d %d", i+1, G->liste_liaisons[i].puits);
	fprintf(f,";\n");
	fprintf(f,"param : arcs: capa:=\n");
	for(i=0;i<G->nb_sommets-1;i++)
			for(j=i+1;j<G->nb_sommets;j++)
				if(G->liste_adjacence[i*G->nb_sommets+j]>0) {
						fprintf(f,"%d %d %d\n", i+1, j+1, G->liste_adjacence[i*G->nb_sommets+j]);
						fprintf(f,"%d %d %d\n", j+1, i+1, G->liste_adjacence[i*G->nb_sommets+j]);
				}
	fprintf(f,";\n");
	fclose(f);

	sprintf(filename, "graphe_%d_%d_%d_%d.run", G->nb_sommets, nb_l, dens, num_inst);
	f=fopen(filename,"w");
        fprintf(f,"reset;\nmodel MFEM_non_oriente.mod;\ndata graphe_n%d_L%d_d%d_%d.dat;\noption cplex_options 'timing=1';\nsolve;\ndisplay flot_total_route > resultat_n%d_L%d_d%d_%d.txt;\n", G->nb_sommets, nb_l, dens, num_inst, G->nb_sommets, nb_l, dens, num_inst);
	fclose(f);
}

double db(int i) {
	double res, tmp=NB_INSTANCES;
	res = (double) i / tmp;
	return res;
}

int main(void) {
	long temps, start, temps2, start2;
	long init, end;
	int flot, nb_liaisons, nb_sommets=0, densite, seed1, seed2, capa_min=1, capa_max, long_ref;
	// nb sommets = 50, 150, 175, 200
	// nb liaisons = nb sommets/10 et nb sommets/5 pour chaque valeur de nb sommets
	// densite = 5, 15, 25, 50
	// long_ref=2 si nb sommets=50, et 3 sinon
	// capa_max=10+alea(nb_sommets/10);
	int i, j, k, l;
	int val_lp_tmp;
	int tps_lp, val_lp, tps_spf, val_spf, tps_H1, val_H1, tps_H2, val_H2;
	graphe *G;
	FILE *f;
	char chaine_commande[2000];
	char filename[2000];
	G=(graphe *) malloc (sizeof(graphe));//on va mettre dans G l'instance creee par Rudy
	srand(time(NULL));
	seed1=alea(10000000);
	seed2=alea(10000000);

	for(i=1;i<=4;i++) {//pour 4 valeurs de nb_sommets : 50, 150, 175 et 200
		if(i==1)
			nb_sommets=50;
		else
			nb_sommets=100+25*i;
		capa_max=10+alea(nb_sommets/10);
		if(nb_sommets==50)
			long_ref=2;
		else
			long_ref=3;
		for(j=0;j<4;j++) {//pour 4 valeurs de densite : 5, 15, 25 et 50
			if(j==3)
				densite=50;
			else
				densite=5+10*j;
			for(k=1;k<3;k++) {//pour 2 valeurs de nb_liaisons
				nb_liaisons=nb_sommets/(k*5);
				tps_spf_partiel=0;
				val_spf_partielle=0;
				long_max_spf=0;
				tps_lp=0;
				val_lp=0;
				tps_spf=0;
				val_spf=0;
				tps_H1=0;
				val_H1=0;
				tps_H2=0;
				val_H2=0;
				for(l=0;l<NB_INSTANCES;l++) {//pour 20 instances différentes
					sprintf(chaine_commande, "./rudy -rnd_graph %d %d %d -random %d %d %d > graphe_n%d_L%d_d%d_%d.txt", nb_sommets, densite, seed1, capa_min, capa_max, seed2, nb_sommets, nb_liaisons, densite, l+1);
					//sous windows, utiliser : sprintf(chaine_commande, "rudy -rnd_graph %d %d %d -random %d %d %d > graphe_n%d_L%d_d%d_%d.txt", nb_sommets, densite, seed1, capa_min, capa_max, seed2, nb_sommets, nb_liaisons, densite, l+1);
					system(chaine_commande);
					creer_graphe(G,nb_sommets,nb_liaisons,densite,l+1,0);//on crée G
					connexifier(G,nb_liaisons,densite,l+1,capa_max);
					initialiser_liaisons_graphes(nb_sommets, nb_liaisons, densite, l+1);//ensuite on ajoute les liaisons
					creer_liaisons_graphe(G,nb_liaisons,densite,l+1);//ensuite on ajoute les liaisons a G
					generer_fichiers_dat_et_run_ampl(G,nb_liaisons,densite,l+1);

					time(&start);
					long_max_spf_tmp=0;
					//on commence par appliquer H2
					flot=spf(G,nb_liaisons,densite,l+1,long_ref,1,0,0,0);//d'abord on execute SPF, en n'utilisant que des chemins de longueur au plus long_ref
					flot+=iterer_H1(G);//ensuite on execute H'1
					val_H2+=flot;
					time(&temps);
					tps_H2+=temps-start;
					free(G->liste_liaisons);
					free(G->liste_adjacence);

					creer_graphe(G,nb_sommets,nb_liaisons,densite,l+1,1);//on réinitialise G
					creer_liaisons_graphe(G,nb_liaisons,densite,l+1);//ensuite on rajoute les liaisons a G
					time(&start2);
					long_max_spf_tmp=0;
					//ensuite on applique SPF
					val_spf+=spf(G,nb_liaisons,densite,l+1,0,0,temps-start,start2,flot);
					time(&temps2);
					long_max_spf+=long_max_spf_tmp;
					tps_spf+=temps2-start2;
					free(G->liste_liaisons);
					free(G->liste_adjacence);

					creer_graphe(G,nb_sommets,nb_liaisons,densite,l+1,1);//on réinitialise G
					creer_liaisons_graphe(G,nb_liaisons,densite,l+1);//ensuite on rajoute les liaisons a G
					time(&start2);
					//enfin on applique H1
					val_H1+=algo_H1(G);
					time(&temps2);
					tps_H1+=temps2-start2;
					free(G->liste_liaisons);
					free(G->liste_adjacence);

					//a present on calcule l'optimum de la relaxation continue a l'aide de AMPL (et CPLEX)
					sprintf(chaine_commande, "ampl graphe_%d_%d_%d_%d.run", nb_sommets, nb_liaisons, densite, l+1);
					time(&start);
					system(chaine_commande);
					time(&temps);
					tps_lp+=temps-start;
					sprintf(filename, "resultat_n%d_L%d_d%d_%d.txt", nb_sommets,nb_liaisons,densite,l+1);
					f=fopen(filename,"r");//on va lire le resultat de la PL
					fscanf(f,"flot_total_route = %d",&val_lp_tmp);
					fclose(f);
					val_lp+=val_lp_tmp;
				}//fin for sur l
				// on ecrit ensuite le fichier contenant les moyennes des 11 indicateurs sur les 20 dernieres instances
				sprintf(filename, "moyenne_n%d_L%d_d%d.txt", nb_sommets, nb_liaisons, densite);
				f=fopen(filename,"w");
				fprintf(f,"1/ %lf 2/ %lf 3/ %lf 4/ %lf 5/ %lf 6/ %lf 7/ %lf 8/ %lf 9/ %lf 10/ %lf 11/ %lf\n", db(tps_lp), db(val_lp), db(tps_spf), db(val_spf), db(long_max_spf), db(tps_H1), db(val_H1), db(tps_H2), db(val_H2), db(tps_spf_partiel), db(val_spf_partielle));
				fprintf(f,"1/ tps_lp 2/ val_lp 3/ tps_spf 4/ val_spf 5/ long_max_spf 6/ tps_H1 7/ val_H1 8/ tps_H2 9/ val_H2 10/ tps_spf_partiel 11/ val_spf_partielle");
				fclose(f);
			}//fin for sur k
		}//fin for sur j
	}//fin for sur i
	free(G);
	return(1);
}