Sélectionner une révision Git
TP2.c 7,01 Kio
#include "./implems.c"
#include "./struct_tp2.h"
#include "./plotout.h"
#include <stdio.h>
#include <stdlib.h>
// g une liste d'adjacence décrivant le graphe
// out res un tableau de taille g->n
// ensures
// out res [i] contient le degré du noeud i
void calc_deg(adjlist *g, unsigned long *out_res) {
unsigned long i;
for (i = 0; i < g->n; i += 1) {
out_res[i] = g->cd[i+1] - g->cd[i];
}
return;
}
// g une liste d'adjacence décrivant le graphe
// eta_tab un tableau d'entiers de taille g->n (initialisé à zero)
// c_tab un tableau d'entiers de taille g-> n (initialisé à zero)
// eta_tab contient l'orde du k-orderind :
// eta[0] = noe1
// eta[1] = noe2 etc
void core_decomposition(adjlist *g, unsigned long *eta_tab, int *c_tab) {
// mise à zero des tableaux
for (unsigned long iter = 0; iter < g->n; iter+=1) {
eta_tab[iter] = 0;
c_tab[iter] = 0;
}
unsigned long v;
tp2_t deg_track;
int i, c;
i = g->n;
c = 0;
// initialise la structure
deg_track = new_tp2(g->n);
for (unsigned long k = 0; k < g->n; k += 1) {
int tmp_deg = (g->cd[k+1]) - (g->cd[k]);
if (set_deg(deg_track, k, tmp_deg) == 0) {
printf("error initialisation deg_struct\n");
return;
}
}
for (unsigned long k = 0; k < g->n; k += 1) {
int tmp_deg = (g->cd[k+1]) - (g->cd[k]);
if (get_deg(deg_track, k) != tmp_deg) {
printf("samuh à merdé\n");
return;
}
}
printf("initialisation terminée\n");
// itère jusqu'à avoir traité tous les noeuds
while (i > 0) {
// trouver un élément de degré min dans le graphe
v = elem_min_deg(deg_track);
int tmp_deg = get_deg(deg_track, v);
if (tmp_deg < 0) {
printf("error elem_min_deg est de degré -1 (tous les noeuds ont été retirés)\n");
for (unsigned long k = 0; k < g->n; k += 1) {
if (get_deg(deg_track, k) != -1) { printf("%lu est de degré %i\n", k, get_deg(deg_track, k));
printf("samuh à merdé\n");
}
}
return;
}
c = (c>tmp_deg) ? c : tmp_deg;
// mettre à jour les degrés par "retrait" du noeud v
// retrait de v
if (remove_elem(deg_track, v) == 0) {
printf("error en retirant le noeud v\n");
return;
}
// mise à jour du degré des voisins
unsigned long i_find_vois;
for (i_find_vois = g->cd[v]; i_find_vois < g->cd[v+1]; i_find_vois += 1) {
if (decrease_deg(deg_track, g->adj[i_find_vois]) == 0) {
printf("error pour dec deg d'un noeud\n");
return;
}
}
// sauvegarde des valeurs pour le k-ordering et la core value du noeud
eta_tab[i - 1] = v;
c_tab[v] = c;
i -= 1;
// printf("c = %i\nnoeuds retirés = %lu\n", c, g->n - i);
}
// destruction de la structure
if (destruct_tp2(deg_track) == 0) {
printf("error destruction de la structure tp2\n");
return;
}
return;
}
int max_c_val(int* tabl, int size) {
int max = tabl[0];
for(int i = 0; i < size; i +=1) {
// printf("|%i|", tabl[0]);
if (tabl[i] > max) {
max = tabl[i];
}
}
return max;
}
// retourne l'indice de noeud dans eta correspondant au densest core ordering prefix
unsigned long compute_densest_core_ordering_prefix(adjlist *g, unsigned long *eta, long double *res_av_deg_dens, long double *res_edge_dens) {
unsigned long i,j,tmp_noeud;
unsigned long *eta_inv;
eta_inv = (unsigned long*) malloc((g->n)*sizeof(unsigned long));
// clacul etainv (chaque entrée eta_inv[v] correspond à l'indice auquel le noeud v est ajouté dans le préfixe)
for (i = 0; i < g->n; i+=1) {
eta_inv[eta[i]] = i;
}
unsigned long grand_n, grand_m;
grand_n = g->n; grand_m = g->e;
long double max_dense = ((long double) grand_m)/((long double) grand_n); //densité du graphe complet
unsigned long max_prefix = (g->n) - 1; // préfixe où tous les noeuds de éta sont pris
// itère pour tous les préfixes (partant du plus grand)
i = (g->n)-1;
while (i > 0) {
tmp_noeud = eta[i]; //le noeud à retirer à cette étape
i -= 1;
// actualise les valeurs de grand_n et grand_m
grand_n -= 1;
for (j = g->cd[tmp_noeud]; j < g->cd[tmp_noeud + 1]; j += 1) {
// si son voisin a été ajouté avant lui dans l'ordre préfixe, alors on décrémente le nombre d'arrêtes
if (eta_inv[tmp_noeud] > eta_inv[g->adj[j]]) {
grand_m -= 1;
}
}
// calcul la nouvelle densité
long double new_density = ((long double) grand_m)/((long double) grand_n);
if (max_dense < new_density) {
max_dense = new_density;
max_prefix = i;
// mise à jour des résultats
*res_av_deg_dens = new_density;
*res_edge_dens = ((long double) grand_m)/((((long double) grand_n)*(((long double) grand_n) - 1))/2.);
}
}
return max_prefix;
}
int main(int argc, char **argv) {
if (argc < 2) {
printf("un argument est attendu\n");
return 1;
}
adjlist *g;
time_t t1, t2, t3;
// PARSING
t1=time(NULL);
printf("Reading edgelist from file %s\n",argv[1]);
g=al_readedgelist(argv[1]);
t3 = time(NULL);
printf("- edge list time = %ldh%ldm%lds\n",(t3-t1)/3600,((t3-t1)%3600)/60,((t3-t1)%60));
// printf("- edge list time = %I64dh%I64dm%I64ds\n",(t3-t1)/3600,((t3-t1)%3600)/60,((t3-t1)%60));
printf("Number of nodes: %lu\n",g->n);
printf("Number of edges: %lu\n",g->e);
printf("Building the adjacency list\n");
mkadjlist(g);
t2=time(NULL);
printf("- Overall time = %ldh%ldm%lds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
// printf("- Overall time = %I64dh%I64dm%I64ds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
// calcul du core ordering et des core value
printf("compiting core ordering and core decomposition...\n");
unsigned long* eta;
int* c;
c = (int*) malloc((g->n)*sizeof(int));
eta = (unsigned long*) malloc((g->n)*sizeof(unsigned long));
t1=time(NULL);
core_decomposition(g, eta, c);
t2=time(NULL);
printf("- Overall time = %ldh%ldm%lds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
// printf("- Overall time = %I64dh%I64dm%I64ds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
printf("core value du graphe : %i\n", max_c_val(c, g->n));
// calcul du densest prefix graph
printf("computing densest prefix graph...\n");
unsigned long indix_densest;
long double densest_cop_av_deg_dens;
long double densest_cop_edge_dens;
t1=time(NULL);
indix_densest = compute_densest_core_ordering_prefix(g, eta, &densest_cop_av_deg_dens, &densest_cop_edge_dens);
t2=time(NULL);
printf("- Overall time = %ldh%ldm%lds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
// printf("- Overall time = %I64dh%I64dm%I64ds\n",(t2-t1)/3600,((t2-t1)%3600)/60,((t2-t1)%60));
printf("densest core prefix :\n\taverage degre density : %Lf\n\tedge density : %Lf\n\tsize : %lu\n", densest_cop_av_deg_dens, densest_cop_edge_dens, indix_densest+1);
// printf("densest core prefix :\n\taverage degre density : %f\n\tedge density : %f\n\tsize : %lu\n", (double) densest_cop_av_deg_dens, (double) densest_cop_edge_dens, indix_densest+1);
// EXERCICE 2
// Calcul des degrés des noeuds pour plot
unsigned long *deg_tabl = (unsigned long*) malloc((g->n)*sizeof(unsigned long));
calc_deg(g, deg_tabl);
plot_out_2D_i_ul("scholar.csv", g->n, c, deg_tabl);
free_adjlist(g);
free(deg_tabl);
free(eta);
free(c);
return 0;
}