Esercizi e sorgenti dei programmi
Algoritmo Push-Relabel
L'algoritmo PUSHRELABEL risolve il problema del massimo flusso su una rete G=(V, E, s, t, c), dove s ∈ V è la sorgente della rete di flusso, t ∈ V è il pozzo e c:V × V → R è la capacità non negativa di ciascuno spigolo della rete (c(u,v)=0 se (u,v) ∉ E). La pseudo-codifica dell'algoritmo è la seguente:
PUSH(G, u, v)
- Input: la rete di flusso G e due vertici u e v
- Output: un incremento del flusso f passante sullo spigolo (u, v)
- x = min{e(u), cf(u, v)}
- f(u, v) = f(u, v) + x, f(v, u) = -f(u, v)
- e(u) = e(u)-x, e(v)+x
- cf(u, v) = cf(u, v) - x
RELABEL(G, u)
- Input: un vertice u della rete di flusso
- Output: l'altezza h(u) di u incrementata di 1 rispetto al vertice adiacente più basso nella rete residua
- h(u) = 1 + min{h(v): (u, v) ∈ Ef}
PUSHRELABEL(G, s, t, c)
- Input: una rete di flusso G con sorgente s, pozzo t e capacità c
- Output: il valore del flusso massimo |f*|
- per ogni vertice u ∈ V(G) ripeti:
- h(u) = 0, e(u) = 0
- fine-ciclo
- per ogni spigolo (u,v) ∈ E(G) ripeti:
- f(u,v) = f(v,u) = 0
- fine-ciclo
- h(s) = |V|
- per ogni v ∈ N(s) ripeti:
- f(s, v) = c(s, v), f(v, s) = -f(s, v)
- e(v) = c(s, v), e(s) = e(s) - c(s, v)
- c(s, v) = 0
- fine-ciclo
- ripeti:
- flag=0
- per ogni u ∈ V(G) ripeti:
- se e(u) > 0 allora
- se esiste v ∈ N(u) in Gf tale che h(u) = h(v)+1 allora PUSH(G, u, v), flag=1
- altrimenti se h(u) ≤ h(v) per ogni v ∈ N(u) in Gf allora RELABEL(G, u), flag=1
- fine-condizione
- fine-ciclo
- fintanto che flag=1
- il flusso massimo è |f*| = e(t)
La compilazione del programma richiede l'uso della libreria grafi.c.
/* ** pushRelabel.c ** ** Algoritmo Push-Relabel per la soluzione del problema del ** massimo flusso su una rete G=(V,E,s,t,c). ** ** #(@)20120503(liverani@mat.uniroma3.it) */ #include <stdlib.h> #include <stdio.h> #include <limits.h> #include "grafi.h" /* * flowPush(G, e, f, u, v) * * Invia del flusso lungo lo spigolo (u,v) sulla rete residua */ void flowPush(grafoPesato G, int *e, int **f, int u, int v) { int x; if (e[u] < G.W[u][v]) x = e[u]; else x = G.W[u][v]; f[u][v] = f[u][v] + x; f[v][u] = -f[u][v]; e[u] = e[u] - x; e[v] = e[v] + x; G.W[u][v] = G.W[u][v] - x; return; } /* * relabel(G, h, u) * * Innalza il vertice u alla minima altezza necessaria per * inviare del flusso in eccesso ad un vertice adiacente */ void relabel(grafoPesato G, int *h, int u) { int v, min=-1; for (v=1; v <= G.n; v++) if (G.W[u][v]>0 && (min==-1 || h[v]<min)) min = h[v]; h[u] = min + 1; return; } /* * pushRelabel(G, s, t) * * Algoritmo Push-Relabel per il calcolo del massimo flusso * sulla rete G con sorgente s e pozzo t */ int pushRelabel(grafoPesato G, int s, int t) { int *h, *e, **f, flag, i, j; elementoLista *p; /* * acquisizione input e dimensionamento array */ h = malloc(sizeof(int) * (G.n+1)); e = malloc(sizeof(int) * (G.n+1)); f = malloc(sizeof(int *) * (G.n+1)); for (i=1; i <= G.n; i++) f[i] = malloc(sizeof(int) * (G.n+1)); /* * inizializzazione preflusso */ for (i=1; i <= G.n; i++) { h[i] = 0; e[i] = 0; for (j=1; j <= G.n; j++) { f[i][j] = 0; f[j][i] = 0; if (G.W[i][j] == INFINITO) G.W[i][j] = 0; } } h[s] = G.n; p = G.V[s]; while (p != NULL) { f[s][p->info] = G.W[s][p->info]; f[p->info][s] = -f[s][p->info]; e[p->info] = G.W[s][p->info]; e[s] = e[s] - G.W[s][p->info]; G.W[s][p->info] = 0; p = p->next; } /* * Push-Relabel */ do { flag = 0; for (i=1; i<=G.n; i++) { if (e[i] > 0) { for (j=1; j <= G.n && flag == 0; j++) { if (G.W[i][j] > 0 && h[i] == h[j]+1) { flowPush(G, e, f, i, j); flag = 1; } } if (flag == 0) { for (j=1; j <= G.n && flag == 0; j++) { if (G.W[i][j] > 0) { flag = 1; if (h[i] > h[j]) flag = 2; } } if (flag == 1) { relabel(G, h, i); } } } } } while (flag == 1); return(e[t]); } /* * Funzione principale */ int main(void) { grafoPesato G; int f, s, t; leggiGrafoPesato(&G); printf("Vertice sorgente (s) e pozzo (t): "); scanf("%d %d", &s, &t); f = pushRelabel(G, s, t); printf("\nIl flusso massimo e' |f*|=%d\n", f); return(0); }