daily pastebin goal
53%
SHARE
TWEET

Untitled

a guest Feb 14th, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void check(Graph g, int *sol, int n, TS vnames, int *ok, int *best_sol, float *best_diam){
  2.     int i, j, k = 0, n_archi = (g->V)*(g->V - 1)/2;
  3.     float dim;
  4.    
  5.     for (i = 0; i < g->V; i++){
  6.         for (j = 0; j < g->V; j++){
  7.             g->archi[i][j] = g->matj[i][j];
  8.         }
  9.     }
  10.    
  11.     for (i = 0; i < g->V-1; i++){
  12.         for (j = i+1; j < g->V; j++){
  13.             if (sol[k++]){
  14.                 g->archi[i][j] = g->archi[j][i] = calcoladist(g, i, j);
  15.             }
  16.         }
  17.     }
  18.    
  19.     if (GRAPHcc(g) == 1){
  20.         dim = diam (g);
  21.         if (dim < *best_diam){
  22.             *best_diam = dim;
  23.             (*ok) = 1;
  24.             for (i = 0; i < n_archi; i++){
  25.                 best_sol[i] = sol[i];
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. void powerset_r (Graph g, int *sol, int *best_sol, float *best_diam, int pos, int n, int start, int *ok, TS vnames){
  32.     int i, n_archi = (g->V)*(g->V - 1)/2;
  33.    
  34.     if (pos == n){
  35.         check(g, sol, n, vnames, ok, best_sol, best_diam);
  36.         return;
  37.     }
  38.    
  39.     for (i = start; i < n_archi; i++){
  40.         sol[i] = 0;
  41.         powerset_r(g, sol, best_sol, best_diam, pos+1, n, i+1, ok, vnames);
  42.     }
  43.     return;
  44. }
  45.  
  46. void risolvicardmin (Graph g, TS vnames){
  47.    
  48.     int ok = 0, *sol, n, *best_sol, i, j, k = 0;
  49.     float best_diam = (float)INT32_MAX;
  50.     int n_archi = (g->V)*(g->V - 1)/2; //considero l'insieme di archi massimo dato un grafo non orientato
  51.    
  52.     sol = malloc(n_archi * sizeof(int));
  53.     best_sol = calloc(n_archi, sizeof(int));
  54.    
  55.     //powerset di archi da aggiungere con terminazione al numero di archi massimo
  56.     for (n = 1; n <= n_archi && ok == 0; n++){
  57.        
  58.         powerset_r(g, sol, best_sol, &best_diam, 0, n, 0, &ok, vnames);
  59.         if (ok == 1){
  60.            
  61.             //ho dimenticato di aggiungere la stampa
  62.            
  63.             for (i = 0; i < n_archi; i++){
  64.                 printf("%d ", best_sol[i]);
  65.             }
  66.            
  67.             printf("\nArchi aggiunti:\n");
  68.            
  69.             for (i = 0; i < g->V-1; i++){
  70.                 for (j = i+1; j < g->V; j++){
  71.                     if (best_sol[k++]){
  72.                         printf("%s - %s\n", TSleggiIndice(vnames, i), TSleggiIndice(vnames, j));
  73.                     }
  74.                 }
  75.             }
  76.             printf("Di diametro minimo: %f\n", best_diam);
  77.             return;
  78.         }
  79.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top