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), c_f(u, v)}
f(u, v) = f(u, v) + x, f(v, u) = -f(u, v)
e(u) = e(u)-x, e(v)+x
c_f(u, v) = c_f(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) ∈ E_f}

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 G_f 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 G_f 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);
}

Corso di Ottimizzazione Combinatoria (IN440)

Esercizi e sorgenti dei programmi

Algoritmo Push-Relabel