Flujo máximo - algoritmo Push-relabel

El algoritmo Push-relabel (también conocido como algoritmo preflow-push) es un algoritmo para calcular el flujo máximo de una red de flujo. La definición exacta del problema que queremos resolver se encuentra en el artículo Flujo máximo - Ford-Fulkerson y Edmonds-Karp.

En este artículo consideraremos resolver el problema empujando un preflujo (preflow) a través de la red, lo que se ejecutará en $O(V^4)$, o más precisamente en $O(V^2 E)$. El algoritmo fue diseñado por Andrew Goldberg y Robert Tarjan en 1985.

Definiciones

Durante el algoritmo tendremos que manejar un preflujo (preflow) - es decir, una función $f$ que es similar a la función de flujo, pero que no necesariamente satisface la restricción de conservación de flujo. Para ella solo tienen que cumplirse las restricciones

$$0 \le f(e) \le c(e)$$

y

$$\sum_{(v, u) \in E} f((v, u)) \ge \sum_{(u, v) \in E} f((u, v))$$

Así, es posible que algún vértice reciba más flujo del que distribuye. Decimos que este vértice tiene cierto flujo en exceso, y definimos su cantidad con la función de exceso $x(u) =\sum_{(v, u) \in E} f((v, u)) - \sum_{(u, v) \in E} f((u, v))$.

De la misma forma que con la función de flujo, podemos definir las capacidades residuales y el grafo residual con la función de preflujo.

El algoritmo empezará con un preflujo inicial (algunos vértices con exceso), y durante la ejecución el preflujo se manejará y se modificará. Anticipando algunos detalles, el algoritmo elegirá un vértice con exceso y empujará el exceso hacia los vértices vecinos. Repetirá esto hasta que todos los vértices, excepto la fuente y el sumidero, estén libres de exceso. Es fácil ver que un preflujo sin exceso es un flujo válido. Esto hace que el algoritmo termine con un flujo real.

Todavía hay dos problemas con los que hay que lidiar. Primero, ¿cómo garantizamos que esto realmente termina? Y segundo, ¿cómo garantizamos que esto realmente nos dará un flujo máximo, y no solo un flujo cualquiera?

Para resolver estos problemas necesitamos la ayuda de otra función, a saber la función de etiquetado $h$, a menudo también llamada función de altura, que asigna a cada vértice un entero. Decimos que un etiquetado es válido si $h(s) = |V|$, $h(t) = 0$, y $h(u) \le h(v) + 1$ si hay una arista $(u, v)$ en el grafo residual - es decir, la arista $(u, v)$ tiene capacidad positiva en el grafo residual. En otras palabras, si es posible aumentar el flujo de $u$ a $v$, entonces la altura de $v$ puede ser a lo sumo una unidad menor que la altura de $u$, pero puede ser igual o incluso mayor.

Es importante notar que, si existe una función de etiquetado válida, entonces no existe un camino aumentante de $s$ a $t$ en el grafo residual. Porque un camino de ese tipo tendrá una longitud de a lo sumo $|V| - 1$ aristas, y cada arista puede disminuir la altura a lo sumo en uno, lo cual es imposible si la primera altura es $h(s) = |V|$ y la última altura es $h(t) = 0$.

Usando esta función de etiquetado podemos enunciar la estrategia del algoritmo Push-relabel: Empezamos con un preflujo válido y una función de etiquetado válida. En cada paso empujamos algo de exceso entre vértices y actualizamos las etiquetas de los vértices. Hay que asegurarse de que después de cada paso el preflujo y el etiquetado sigan siendo válidos. Si entonces el algoritmo termina, el preflujo es un flujo válido. Y como también tenemos un etiquetado válido, no existe un camino entre $s$ y $t$ en el grafo residual, lo que significa que el flujo es de hecho un flujo máximo.

Si comparamos el algoritmo de Ford-Fulkerson con el algoritmo Push-relabel, parece que los algoritmos son duales entre sí. El algoritmo de Ford-Fulkerson mantiene un flujo válido en todo momento y lo mejora hasta que ya no existe un camino aumentante, mientras que en el algoritmo Push-relabel no existe un camino aumentante en ningún momento, y mejoraremos el preflujo hasta que sea un flujo válido.

Algoritmo

Primero hay que inicializar el grafo con un preflujo válido y una función de etiquetado.

Usar el preflujo vacío - como se hace en el algoritmo de Ford-Fulkerson - no es posible, porque entonces habrá un camino aumentante y esto implica que no existe un etiquetado válido. Por lo tanto inicializaremos cada arista saliente de $s$ con su capacidad máxima: $f((s, u)) = c((s, u))$. Y todas las demás aristas con cero. En este caso existe un etiquetado válido, a saber $h(s) = |V|$ para el vértice fuente y $h(u) = 0$ para todos los demás.

Ahora describamos las dos operaciones con más detalle.

Con la operación push intentamos empujar tanto flujo en exceso como sea posible de un vértice $u$ a un vértice vecino $v$. Tenemos una regla: solo se permite empujar flujo de $u$ a $v$ si $h(u) = h(v) + 1$. En términos simples, el flujo en exceso tiene que fluir hacia abajo, pero no de forma demasiado pronunciada. Por supuesto solo podemos empujar $\min(x(u), c((u, v)) - f((u, v)))$ de flujo.

Si un vértice tiene exceso, pero no es posible empujar el exceso a ningún vértice adyacente, entonces hay que aumentar la altura de este vértice. Llamamos a esta operación relabel. La aumentaremos tanto como sea posible, manteniendo todavía la validez del etiquetado.

Para recapitular, el algoritmo en pocas palabras es: Inicializamos un preflujo válido y un etiquetado válido. Mientras podamos realizar operaciones push o relabel, las realizamos. Después el preflujo es de hecho un flujo y lo devolvemos.

Complejidad

Es fácil mostrar que la etiqueta máxima de un vértice es $2|V| - 1$. En ese punto todo el exceso restante puede y será empujado de vuelta a la fuente. Esto da a lo sumo $O(V^2)$ operaciones relabel.

También se puede mostrar que se realizarán a lo sumo $O(V E)$ pushes saturantes (un push en el que se usa la capacidad total de la arista) y a lo sumo $O(V^2 E)$ pushes no saturantes (un push en el que la capacidad de una arista no se usa por completo). Si elegimos una estructura de datos que nos permita encontrar el siguiente vértice con exceso en tiempo $O(1)$, entonces la complejidad total del algoritmo es $O(V^2 E)$.

Implementación

const int inf = 1000000000;

int n;
vector<vector<int>> capacity, flow;
vector<int> height, excess, seen;
queue<int> excess_vertices;

void push(int u, int v) {
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if (d && excess[v] == d)
        excess_vertices.push(v);
}

void relabel(int u) {
    int d = inf;
    for (int i = 0; i < n; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

void discharge(int u) {
    while (excess[u] > 0) {
        if (seen[u] < n) {
            int v = seen[u];
            if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
                push(u, v);
            else 
                seen[u]++;
        } else {
            relabel(u);
            seen[u] = 0;
        }
    }
}

int max_flow(int s, int t) {
    height.assign(n, 0);
    height[s] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[s] = inf;
    for (int i = 0; i < n; i++) {
    	if (i != s)
	        push(s, i);
    }
    seen.assign(n, 0);

    while (!excess_vertices.empty()) {
        int u = excess_vertices.front();
        excess_vertices.pop();
        if (u != s && u != t)
            discharge(u);
    }

    int max_flow = 0;
    for (int i = 0; i < n; i++)
        max_flow += flow[i][t];
    return max_flow;
}

Aquí usamos la cola excess_vertices para guardar todos los vértices que actualmente tienen exceso. De esa forma podemos elegir el siguiente vértice para una operación push o relabel en tiempo constante.

Y para asegurarnos de no gastar demasiado tiempo encontrando el vértice adyacente al que podemos empujar, usamos una estructura de datos llamada arco actual (current-arc). Básicamente iteraremos sobre las aristas en orden circular y siempre guardaremos la última arista que usamos. De esta forma, para un cierto valor de etiquetado, cambiaremos la arista actual solo $O(n)$ veces. Y como el reetiquetado ya toma tiempo $O(n)$, no empeoramos la complejidad.