Flujo máximo

Las dos últimas semanas calculamos caminos mínimos con programación dinámica: Bellman-Ford con aristas negativas, y Floyd-Warshall entre todos los pares. En todos esos problemas, un grafo con números en las aristas respondía una pregunta sobre un recorrido: cuál es el camino más barato.

Esta semana abre la última parte del curso con otra pregunta sobre el mismo tipo de objeto. Los números ya no son costos, son capacidades. Una red de tuberías, de enlaces o de carreteras tiene un límite en cada tramo, y lo que queremos saber es cuánto puede pasar en total de un punto a otro, repartido entre todos los caminos a la vez.

Es un problema en el que las dos técnicas que conocemos se quedan cortas. Un greedy que empuja por un camino y sigue adelante se atasca, y lo vamos a ver con un contraejemplo de cuatro nodos. La programación dinámica tampoco ayuda: no hay un subproblema pequeño a la vista, porque lo que se manda por un camino afecta a todos los que comparten sus aristas. La idea nueva es una tercera: dejar que un greedy se equivoque, y darle una forma de deshacer lo que hizo. Esa forma es la red residual.

La primera sesión define el problema, muestra por qué falla el greedy, construye la red residual y llega a Ford-Fulkerson, con su costo y su peor caso. La segunda sesión responde lo que queda abierto: cuando el algoritmo se detiene, ¿el flujo es de verdad máximo? La respuesta es uno de los teoremas centrales del curso, el de flujo máximo y corte mínimo, y de él sale también cómo encontrar el cuello de botella de una red. Al final, Edmonds-Karp arregla el peor caso con un cambio de una línea.

La próxima semana usaremos todo esto como herramienta: muchos problemas que no parecen de flujo se pueden convertir en flujo. Por eso el código de esta semana está escrito para reutilizarlo.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, El problema, Un greedy que falla y Cortes: un techo para todo flujo.

En clase: Sesión A, de La red residual a El peor caso: el diamante. Sesión B, de Cortes: un techo para todo flujo a Edmonds-Karp.

Después de clase: Comprobar una respuesta sin confiar en el programa, Casos de borde, el Resumen y los Ejercicios, para repasar, y los resúmenes de las semanas 7, 9 y 10 para la Práctica 3. Opcional: En C++: aristas en pares, El código de la semana y su problema. Para ampliar, En la práctica: otros algoritmos y las lecturas de apoyo del recuadro siguiente.

Lectura. Sesión A: Erickson, secs. 10.1 (Flows), 10.2 (Cuts) y 10.4 (Ford and Fulkerson’s augmenting-path algorithm). CLRS, capítulo Maximum Flow, 4.ª edición. Sesión B: Erickson, secs. 10.3 (The Maxflow-Mincut Theorem) y 10.6 (Edmonds and Karp’s Algorithms). CLRS, capítulo Maximum Flow, 4.ª edición. Estos apuntes se pueden estudiar sin ellos.

Código. Los programas de este capítulo están en code/week-11. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. El problema opcional de laboratorio está en lab/network_capacity y tiene su propio make test.

El problema

Una red de flujo (flow network) es un grafo dirigido con estos datos:

• Cada arista e tiene una capacidad c(e) ≥ 0: lo máximo que puede pasar por ella.
• Hay dos nodos distinguidos y distintos: la fuente s (source), de donde sale lo que se envía, y el sumidero t (sink), adonde llega.

Un flujo (flow) le asigna a cada arista e un número f(e), lo que pasa por ella, con dos condiciones:

1. Capacidad. 0 ≤ f(e) ≤ c(e) en toda arista.
2. Conservación. En todo nodo distinto de s y de t, lo que entra es igual a lo que sale. Los nodos intermedios no guardan ni producen nada.

El valor de un flujo, que se escribe |f|, es lo que sale de la fuente neto:

|f| = (suma de f(e) en las aristas que salen de s) - (suma de f(e) en las aristas que entran a s)

La resta importa. Nada prohíbe que una arista entre a s: lo que vuelve a la fuente no se envió de verdad.

El problema de flujo máximo (maximum flow) es encontrar un flujo de valor máximo. Dicho en palabras, responder cuánto puede pasar de s a t respetando las capacidades y la conservación.

Esta es la red que nos va a acompañar en todo el capítulo. Tiene cuatro nodos y cinco aristas. A la izquierda, cada número es una capacidad:

Es decir: s → a de 3, s → b de 2, a → b de 2, a → t de 2 y b → t de 3. Un flujo posible es mandar 2 por s → a → t y 2 por s → b → t. Revisemos la definición. Las capacidades se respetan. En a entran 2 y salen 2, en b entran 2 y salen 2. El valor es 2 + 2 = 4. ¿Se puede más? De s solo salen capacidades 3 + 2 = 5, así que nunca se podrá pasar de 5. Veremos que 5 se puede.

Antes de seguir, dos aclaraciones que evitan confusiones más adelante.

Las aristas son dirigidas. Una tubería con válvula, un enlace de un solo sentido. Si un tramo va en los dos sentidos, se escribe con dos aristas, una en cada sentido.

Se permiten aristas antiparalelas y paralelas. Dos aristas son antiparalelas si una va de u a v y la otra de v a u. Algunos libros las prohíben para simplificar la notación, y CLRS las evita agregando un nodo intermedio. Aquí no hace falta ninguna transformación: cada arista de la entrada es un objeto propio, con su propia capacidad y su propio flujo, aunque otra arista una los mismos nodos. Lo mismo para dos aristas paralelas, del mismo u al mismo v. Más abajo se ve que eso solo tiene una consecuencia: la red residual puede tener varios arcos entre dos nodos, y no molesta.

Las aristas que entran a s o que salen de t también se permiten. La definición de valor ya las contempla. Una arista de un nodo a sí mismo no aporta nada y no la vamos a considerar.

En la práctica. El lenguaje es de tuberías, pero lo que fluye puede ser cualquier cosa divisible que se conserve al pasar: datos en una red, camiones por carreteras, electricidad, personas asignadas a turnos. La semana que viene fluirán unidades que representan decisiones, como “este estudiante va a esta sección”.

Un greedy que falla

La primera idea es la de siempre: buscar un camino de s a t que todavía tenga espacio, empujar por él todo lo que se pueda, y repetir hasta que no quede ningún camino. Lo que se puede empujar por un camino es la menor capacidad libre entre sus aristas. A esa cantidad se le llama su cuello de botella (bottleneck). Una arista cuyo flujo llega a su capacidad está saturada (saturated).

El programa greedy_demo corre esta idea en nuestra red, tomando siempre el camino con más aristas:

$ build/greedy_demo
Sin volver atrás, siempre el camino con más aristas:
  s > a > b > t   empuja 2, total 2
  s > a > t   empuja 1, total 3
  s > b > t   empuja 1, total 4
  no queda camino: se queda en 4
  s -> a  flujo 3 de 3
  s -> b  flujo 1 de 2
  a -> b  flujo 2 de 2
  a -> t  flujo 1 de 2
  b -> t  flujo 3 de 3

Se queda en 4, y el máximo es 5. Miren dónde se atasca. A s → b le queda 1 libre, y a a → t le queda 1 libre. Pero desde b la única salida es b → t, que está saturada, y a a no se puede llegar porque s → a también lo está. El problema viene de la primera decisión. Mandar 2 por a → b llenó b → t con flujo que venía de a, cuando a tenía su propia salida directa a t.

¿Y si se eligen mejor los caminos? La siguiente parte de la salida prueba todas las formas posibles de elegir:

Sin volver atrás, todas las formas de elegir los caminos:
  termina en 4: 2 de 6 secuencias
  termina en 5: 4 de 6 secuencias

Hay elecciones que llegan a 5 y hay elecciones que se quedan en 4. Ningún camino está prohibido: el problema es que el greedy no sabe cuál elegir. Y buscar una regla local que acierte siempre es justo lo que ya aprendimos a desconfiar: aquí no tenemos un argumento de intercambio, porque el valor de un camino depende de lo que todos los demás hagan después.

¿Dónde se rompe la intuición? Mirar un camino y decidir “lo mando” es una decisión irrevocable, y la información para tomarla bien todavía no existe. La salida no es decidir mejor. Es poder cambiar de opinión.

Idea clave. Una mala decisión de flujo no se evita, se deshace. Si por a → b pasan 2, y resulta que convenía que pasara menos, un camino posterior puede “devolver” parte de ese flujo.

La red residual

¿Qué significa devolver flujo? Sigamos con el estado del greedy justo después de su primer camino: pasan 2 por s → a, a → b y b → t. Un nuevo camino podría entrar a b por s → b, y luego, en vez de seguir por b → t, cancelar 2 unidades de las que iban de a a b. Esas unidades ya no llegan a b, así que siguen en a, y desde a salen por a → t. El resultado neto es que b → t sigue igual de lleno, a → b se vació, y entraron 2 unidades más desde s, que llegaron a t. Es como si el camino hubiera recorrido a → b al revés.

La red residual (residual network) es lo que hace de esto un camino normal. Dado un flujo f, su red residual G_f tiene los mismos nodos y, por cada arista e de u a v, dos arcos:

• El arco de ida u → v, con capacidad residual c(e) − f(e): cuánto más se puede agregar.
• El arco inverso (o de vuelta) v → u, con capacidad residual f(e): cuánto se puede cancelar.

Solo los arcos con capacidad residual positiva cuentan como presentes en G_f. El arco inverso no es una arista real de la red. Es una forma de escribir “cancelar flujo de la arista e”.

Con aristas antiparalelas, cada una aporta sus dos arcos, y entre u y v puede haber varios arcos en el mismo sentido. Por ejemplo, si existen e de u a v y e’ de v a u, entonces de u a v hay dos arcos: el de ida de e y el inverso de e’. Cada uno se usa y se actualiza aparte. Nada de lo que sigue necesita que haya un solo arco entre dos nodos.

Esta es la red residual de nuestro ejemplo después del primer camino, s → a → b → t con 2:

La fila que importa es la de a → b. Su arco de ida ya no está, pero apareció b → a con capacidad 2. Ahora existe un camino de s a t: s → b, de capacidad 2; b → a, de capacidad 2, inverso; y a → t, de capacidad 2. El greedy no lo tenía, porque no conocía el arco b → a.

Un ejemplo con aristas antiparalelas. Supongamos que a → b tiene capacidad 5 y flujo 3, y que b → a tiene capacidad 4 y flujo 1. La red residual tiene cuatro arcos entre esos dos nodos:

Un camino que pase de a a b puede usar cualquiera de los dos arcos a → b. Empujar por el primero sube el flujo de a → b, y empujar por el cuarto baja el de b → a. En los dos casos, lo que pasa neto de a a b sube igual. Un flujo que manda algo en los dos sentidos a la vez es válido, aunque tenga un pequeño ciclo que no aporta al valor.

Un camino de aumento (augmenting path) es un camino simple de s a t en la red residual. Aumentar por un camino P es esto. Se toma δ, la menor capacidad residual de sus arcos, que es su cuello de botella. Por cada arco de P:

• Si es el arco de ida de e, se hace f(e) ← f(e) + δ.
• Si es el arco inverso de e, se hace f(e) ← f(e) − δ.

Lema (aumentar). Si f es un flujo y P es un camino de aumento con cuello de botella δ, entonces lo que resulta, f’, es un flujo, y |f’| = |f| + δ.

Técnica. Comprobar cada condición de la definición. Para la conservación, ver qué le hace cada arco del camino al saldo de sus dos extremos.

Capacidad. En un arco de ida, δ ≤ c(e) − f(e), así que f(e) + δ ≤ c(e), y no baja de 0. En un arco inverso, δ ≤ f(e), así que f(e) − δ ≥ 0, y no sube de c(e).

Saldo. Llamemos saldo de un nodo a lo que sale de él menos lo que entra. Conservación es decir que el saldo es 0 en todo nodo salvo s y t, y |f| es el saldo de s. Tomemos un arco del camino que vaya de x a y. Veamos los dos casos.

• Si es el arco de ida de una arista x → y, su flujo sube δ. Sale δ más de x, y entra δ más a y. El saldo de x sube δ, y el de y baja δ.
• Si es el arco inverso de una arista y → x, su flujo baja δ. Sale δ menos de y, y entra δ menos a x. El saldo de y baja δ, y el de x sube δ.

En los dos casos pasa lo mismo: el saldo del nodo de donde sale el arco sube δ, y el del nodo adonde llega baja δ.

Conservación y valor. El camino P es simple. Un nodo intermedio de P tiene exactamente un arco que llega y uno que sale: su saldo baja δ y sube δ, y no cambia. Un nodo que no está en P no cambia. La fuente s es el primer nodo: solo tiene un arco que sale, y como P es simple no vuelve a pasar por ella. Su saldo sube δ, así que |f’| = |f| + δ. El sumidero baja δ, y no se le exige conservación. ∎

Como δ > 0, porque los arcos de G_f tienen capacidad positiva, cada aumento hace crecer el valor estrictamente.

Ford-Fulkerson

Ya tenemos todas las piezas. El algoritmo de Ford-Fulkerson es el greedy de antes, con la red residual en lugar de la red original.

algoritmo ford_fulkerson(red, s, t)
    para cada arista e hacer
        f[e] ← 0
    fin para
    mientras exista un camino de aumento P de s a t en la red residual hacer
        δ ← menor capacidad residual entre los arcos de P
        para cada arco de P hacer
            si es el arco de ida de e entonces
                f[e] ← f[e] + δ
            sino
                f[e] ← f[e] - δ
            fin si
        fin para
    fin mientras
    devolver f
fin algoritmo

Fíjense en lo que el pseudocódigo no dice: no dice qué camino elegir. Ford-Fulkerson es una familia de algoritmos, uno por cada regla de elección. Esa libertad nos va a costar caro en un momento.

El flujo inicial, todo en cero, es un flujo. Por el lema, después de cada vuelta sigue siéndolo. Así que, cuando el algoritmo termine, habrá un flujo. Que sea máximo no es obvio, y es lo que demuestra la segunda sesión.

Un recorrido a mano

Es el mismo programa de antes, con la misma regla de elegir el camino con más aristas, pero ahora con arcos inversos. En la salida, < significa que el camino recorre un arco inverso, contra la arista.

Ford-Fulkerson, la misma regla con aristas inversas (< es recorrer una inversa):
  s > a > b > t   empuja 2, total 2
  s > b < a > t   empuja 2, total 4
  s > a > b > t   empuja 1, total 5
  no queda camino: termina en 5
  s -> a  flujo 3 de 3
  s -> b  flujo 2 de 2
  a -> b  flujo 1 de 2
  a -> t  flujo 2 de 2
  b -> t  flujo 3 de 3

Corte mínimo por fuerza bruta: 5

La tabla sigue el flujo de cada arista, vuelta por vuelta. La fila de δ dice cuánto se empujó.

La flecha ⇒ es el arco inverso. En la vuelta 2, el flujo de a → b baja de 2 a 0, porque el camino lo cancela. Es la misma red en que el greedy se quedaba en 4, y con la misma primera mala decisión. La vuelta 2 la corrige.

Vale la pena ver la red residual en cada paso, porque es lo que el programa mira de verdad. Cada casilla es la capacidad residual de ese arco. Las columnas ida son c − f, y las columnas ⇒ son f.

En cada par, la suma de las dos casillas es siempre la capacidad de la arista. Empujar pasa cantidad de una casilla a la otra, y eso es todo lo que hace el programa, como veremos en C++.

Después de la vuelta 3, s → a y s → b están saturadas, y ninguna arista entra a s, así que no hay arcos inversos que salgan de s. De s no sale ningún arco residual, así que no hay camino de aumento y el algoritmo termina. El valor es 5, y ya dijimos que de s no pueden salir más de 5. En este ejemplo, entonces, 5 es el máximo. La segunda sesión generaliza este argumento.

Esto responde la primera pregunta de repaso: una red de 4 nodos en la que un mal camino obliga a usar una arista inversa.

Terminación e integralidad

¿Siempre termina? Con capacidades enteras, sí, y además da un flujo entero.

Teorema (integralidad). Si todas las capacidades son enteras, entonces, en cada momento de Ford-Fulkerson, todos los f(e) son enteros. El algoritmo termina después de a lo sumo f* aumentos, donde f* es el valor de un flujo máximo, y el flujo que devuelve es entero.

Técnica. Inducción sobre las vueltas, con este invariante: todos los flujos son enteros.

Base. Al inicio, todos los flujos son 0.

Paso. Supongamos que al empezar una vuelta todos los f(e) son enteros. Las capacidades residuales son c(e) − f(e) y f(e), que entonces son enteras. δ es la menor de varias de ellas, así que es un entero, y es positivo: δ ≥ 1. Cada f(e) cambia en +δ, −δ o nada, y sigue siendo entero.

Terminación. Por el lema, cada vuelta hace subir el valor en δ ≥ 1. El valor empieza en 0, y el valor de ningún flujo supera C, la suma de las capacidades que salen de s, así que el algoritmo termina. El flujo final es máximo, como veremos en la Sesión B, de modo que el número de vueltas es a lo sumo su valor, f*. ∎

Este teorema se ve modesto, pero la semana que viene será indispensable. Hay un flujo máximo con valores enteros, y el algoritmo lo encuentra. Eso permite que “una unidad de flujo” signifique “una persona asignada”, sin medias personas. No dice que todo flujo máximo sea entero: puede haber otros con fracciones del mismo valor.

Con capacidades racionales, basta multiplicar todo por un denominador común. Con capacidades irracionales y una mala elección de caminos, Ford-Fulkerson puede no terminar. En un programa, las capacidades son enteros.

El costo: O(E·f)

Cada vuelta busca un camino, con BFS o DFS, que cuesta O(V + E) en la red residual: esta tiene los mismos V nodos y a lo sumo 2E arcos. Luego actualiza a lo sumo V − 1 arcos. Si cada nodo toca alguna arista, V ≤ 2E, así que la vuelta cuesta O(E). Es un supuesto razonable: un nodo sin aristas se puede borrar sin cambiar nada.

Con capacidades enteras hay a lo sumo f* aumentos, más una búsqueda final que no encuentra nada. En total:

Costo de Ford-Fulkerson: O(E·f), donde f es el valor del flujo máximo, con capacidades enteras y cada búsqueda en O(E).

Este f no es la cantidad de aristas ni algo que dependa del tamaño del grafo: es un número que depende de las capacidades. Y aquí vuelve algo de la semana 7. Como O(nW) en la mochila, O(E·f) es polinomial en el valor de las capacidades, pero no en los bits que hacen falta para escribirlas: es un costo pseudopolinomial. Duplicar los bits de las capacidades puede elevar f al cuadrado.

¿Es solo una cota pesimista? No. Se alcanza.

El peor caso: el diamante

Tomemos una red con cuatro aristas de capacidad M y una arista de capacidad 1 en medio:

El flujo máximo es 2M: M por arriba y M por abajo, sin tocar la arista del medio. Con dos caminos bien elegidos se termina. Pero Ford-Fulkerson no dice que los elija bien, y hay una regla que lo hace muy mal. Si en cada vuelta se toma el camino de aumento con más aristas, pasa esto:

Cada vuelta usa la arista del medio, en un sentido o en el otro, y su capacidad 1 limita δ a 1. Esa arista oscila entre llena y vacía. El programa bad_capacities cuenta las vueltas, para esa regla y para otras dos. Va con -O2. Los milisegundos son de una sola corrida, y dependen de la máquina:

$ make bench
build/bad_capacities
capacidad                     regla       flujo iteraciones          ms
        10             el más largo          20          20         0.0
        10         primero de un DFS          20           4         0.0
        10        BFS (Edmonds-Karp)          20           2         0.0
      1000             el más largo        2000        2000         0.3
      1000         primero de un DFS        2000           4         0.0
      1000        BFS (Edmonds-Karp)        2000           2         0.0
    100000             el más largo      200000      200000        34.4
    100000         primero de un DFS      200000           4         0.0
    100000        BFS (Edmonds-Karp)      200000           2         0.0
   1000000             el más largo     2000000     2000000       360.3
   1000000         primero de un DFS     2000000           4         0.0
   1000000        BFS (Edmonds-Karp)     2000000           2         0.0

Con M = 1000000, la regla adversaria hace exactamente 2 000 000 de iteraciones, en una red de cuatro nodos y cinco aristas. La cota O(E·f) se alcanza: iteraciones = f. Eso responde la tercera pregunta de repaso. Con capacidades de 1000000, Ford-Fulkerson puede hacer 2 × 10⁶ iteraciones, en esta red. Hay que dar la arista del medio con capacidad 1: con capacidad 1000000, el primer camino ya empujaría 1000000 de una vez. Y no puede hacer más que eso en esta red, porque cada iteración empuja al menos 1 y el máximo es 2 × 10⁶.

Fíjense en las otras dos filas. Con BFS, que toma el camino con menos aristas, bastan 2 vueltas. Es la idea de Edmonds-Karp, en la segunda sesión. La versión con DFS, que toma el primer camino que encuentra una búsqueda en profundidad con los arcos en el orden del programa, hace 4 en este diamante.

¿Quiere decir que con DFS no hay problema? No. El diamante es malo para una regla en particular, no para DFS. Más adelante mediremos el DFS en redes más grandes con capacidades grandes, y en una de ellas da miles de veces más iteraciones que BFS. Lo único que garantiza la cota con DFS sigue siendo O(E·f).

Error común. Decir que “Ford-Fulkerson cuesta O(E·f), y E es pequeño, así que es rápido”. El peligro es f. Con capacidades de 10⁹, f puede ser mayor que 10⁹, y esa cota no promete nada útil. Antes de usar una versión con una regla cualquiera, miren el valor de las capacidades, no solo el tamaño del grafo.

En C++: aristas en pares

Ahora el programa. Como la inversa se usa tanto como la arista, conviene que encontrarla sea trivial. El truco es guardar todos los arcos en un arreglo, de a dos: la arista original en una posición par, y su inversa justo después, en la impar.

arco        0      1      2      3      4      5     ...
            s→a    a→s    s→b    b→s    a→b    b→a   ...

Así, el par del arco e es e ^ 1, en los dos sentidos. El ^ es el o exclusivo por bits, y e ^ 1 cambia el último bit: 4 ^ 1 = 5 y 5 ^ 1 = 4. Este es el inicio de la clase, en flow.h:

class FlowNetwork {
public:
    explicit FlowNetwork(int nodes) : arcs_from_(static_cast<std::size_t>(nodes)) {}

    // Agrega from → to y, junto con ella, su inversa con capacidad 0. Devuelve el número de la
    // arista, que siempre es par. Dos aristas antiparalelas son dos pares independientes.
    int add_edge(int from, int to, long long capacity) {
        const int edge = static_cast<int>(to_.size());
        to_.push_back(to);
        residual_.push_back(capacity);
        arcs_from_[static_cast<std::size_t>(from)].push_back(edge);
        to_.push_back(from);
        residual_.push_back(0);
        arcs_from_[static_cast<std::size_t>(to)].push_back(edge + 1);
        return edge;
    }

La clase no guarda el flujo: guarda solo las capacidades residuales. Al inicio, el arco de ida tiene c y la inversa tiene 0. El flujo de una arista se lee en su inversa, y la capacidad original es la suma de las dos:

    // De una arista original: lo que pasa por ella es lo que su inversa puede devolver.
    long long flow_on(int edge) const { return residual(edge ^ 1); }
    long long capacity(int edge) const { return residual(edge) + residual(edge ^ 1); }

    // Empuja amount por cada arco del camino. Empujar por un arco es quitarle a él y darle a su par.
    void push(const std::vector<int>& path, long long amount) {
        for (int arc : path) {
            residual_[static_cast<std::size_t>(arc)] -= amount;
            residual_[static_cast<std::size_t>(arc ^ 1)] += amount;
        }
    }

Fíjense en push. Las dos ramas del pseudocódigo, sumar en un arco de ida y restar en uno inverso, son aquí la misma línea. Empujar δ por un arco de ida baja su residual y sube el de su inversa. Empujar por una inversa hace lo mismo con los papeles cambiados. Esa simetría es lo que hace corto este código.

También por eso los long long. Cada capacidad puede caber en un int y el total no: dos aristas de 2 × 10⁹ ya dan más de lo que cabe, y un overflow aquí no da error, da otro número. La prueba de test_examples.cpp usa el diamante con M = 2 × 10⁹, de flujo 4 × 10⁹.

La parte de Ford-Fulkerson recibe la regla como parámetro. Una regla es una función que recibe la red y devuelve un camino como lista de arcos, vacía si no hay:

template <typename Rule>
FlowRun ford_fulkerson(FlowNetwork& net, int source, int sink, Rule rule, std::vector<Augmentation>* log = nullptr) {
    long long iterations = 0;
    while (true) {
        const std::vector<int> path = rule(net, source, sink);
        if (path.empty()) break;
        const long long amount = net.bottleneck(path);
        net.push(path, amount);
        iterations++;
        if (log != nullptr) log->push_back({path, amount});
    }
    return {net.flow_value(source), iterations};
}

Con esto, cambiar de regla es cambiar un argumento. Es lo que hace bad_capacities. Usar la clase toma pocas líneas. Así se arma la primera red, con s, a, b y t numerados 0, 1, 2 y 3, y se calcula su flujo:

FlowNetwork net(4);
const int s_to_a = net.add_edge(0, 1, 3);
net.add_edge(0, 2, 2);
net.add_edge(1, 2, 2);
net.add_edge(1, 3, 2);
net.add_edge(2, 3, 3);
const FlowRun run = edmonds_karp(net, 0, 3);
// run.value es 5, y net.flow_on(s_to_a) es lo que pasa por s → a.

add_edge devuelve el número de la arista. Hay que guardarlo si después se quiere saber qué pasó por ella. La próxima semana será la forma de traducir el flujo a la respuesta de otro problema.

En C++. Un template como Rule deja pasar cualquier cosa que se pueda llamar con esos argumentos: aquí, una función normal como shortest_path_rule. El compilador genera una versión de ford_fulkerson por cada tipo de regla. Nuestras reglas son funciones con la misma firma, así que Rule es el mismo puntero a función y hay una sola versión. Una lambda tiene tipo propio, y con ella sí se generaría otra. Es la misma técnica de std::sort cuando recibe una comparación.

En C++. Agreguen los dos arcos juntos, en la misma llamada, para que el par siga siendo (e, e ^ 1). Si alguna vez se empuja un arco suelto al arreglo sin su inversa, todos los pares siguientes quedan corridos, y e ^ 1 apunta a otra arista sin que nada avise.

Error común. Olvidar crear la arista inversa con capacidad 0. Un programa sin arista inversa es exactamente el greedy del principio de este capítulo: compila, termina, y a veces da la respuesta correcta. En nuestra red, con la regla del camino con más aristas, da 4 en vez de 5. La inversa tampoco se crea con capacidad c. Eso permite pasar flujo por la arista al revés desde el inicio, como si el tramo fuera en los dos sentidos. Esta red tiene s → b, a → b y a → t, de capacidad 1, y de s no se puede llegar a t:

Si la inversa se crea con capacidad c en lugar de 0, en s -> b, a -> b, a -> t, todas de 1:
  con capacidad 0: flujo 0
  con capacidad c: flujo 1

Cortes: un techo para todo flujo

Empieza la segunda sesión. Tenemos un algoritmo que se detiene cuando no quedan caminos de aumento. Para saber que acertó, hace falta alguna forma de certificar que no se puede más, sin probar todos los flujos posibles. En el ejemplo ya lo hicimos a ojo: de s solo salen capacidades 3 + 2 = 5. Ese razonamiento se puede hacer con cualquier separación de la red, no solo alrededor de s.

Un corte (cut) de una red es una partición de los nodos en dos conjuntos (S, T), con s en S y t en T. Es el mismo corte de la semana 6, con la condición de que separe la fuente del sumidero.

• La capacidad del corte, c(S, T), es la suma de las capacidades de las aristas que van de S a T.
• El flujo neto por el corte, f(S, T), es la suma de f(e) en las aristas de S a T, menos la suma de f(e) en las aristas de T a S.

Noten la asimetría. Las aristas de T a S no cuentan para la capacidad, y sí restan en el flujo neto. Una arista que vuelve no ayuda a separar nada: cerrarla no impide que el flujo pase de S a T.

Un corte mínimo (minimum cut) es un corte de capacidad mínima. Puede haber varios.

Lema (flujo neto). Para todo flujo f y todo corte (S, T), f(S, T) = |f|.

Dicho de otro modo, lo que sale de s pasa completo, descontando lo que vuelve, por cualquier frontera que separe a s de t. Cada corte ve el mismo número.

Técnica. Sumar los saldos de todos los nodos de S, y mirar cuánto aporta cada arista.

Sumemos el saldo de cada nodo de S. Por conservación, los nodos de S distintos de s tienen saldo 0. Como t no está en S, no hay ningún otro nodo con saldo distinto de 0. Entonces esa suma vale el saldo de s, que es |f|.

Ahora contemos la misma suma por aristas. Una arista de flujo f(e) suma f(e) al saldo del nodo de donde sale, y resta f(e) al saldo del nodo adonde llega. Hay cuatro casos:

• Con los dos extremos en S: suma y resta f(e). Aporta 0.
• Con los dos extremos en T: no entra en la suma. Aporta 0.
• De S a T: solo cuenta el que sale. Aporta +f(e).
• De T a S: solo cuenta el que llega. Aporta −f(e).

El total es exactamente f(S, T). Las dos cuentas son la misma suma, así que f(S, T) = |f|. ∎

Teorema (dualidad débil). Para todo flujo f y todo corte (S, T), |f| ≤ c(S, T).

Técnica. Usar el lema, y acotar cada término con la condición de capacidad.

|f| = f(S, T)
    = (suma de f(e) en las aristas de S a T) - (suma de f(e) en las aristas de T a S)
    ≤ (suma de f(e) en las aristas de S a T)        porque f(e) ≥ 0
    ≤ (suma de c(e) en las aristas de S a T)        porque f(e) ≤ c(e)
    = c(S, T)                                       ∎

Esta es la respuesta a la segunda pregunta de repaso. Además, leyendo las dos desigualdades se ve cuándo hay igualdad: |f| = c(S, T) exactamente cuando las aristas de S a T están saturadas y las de T a S llevan flujo 0. Lo vamos a necesitar.

Como vale para todo flujo y todo corte, se tiene que el mayor flujo no supera al menor corte. Y entonces hay un certificado: si encuentran un flujo y un corte con el mismo valor, los dos son óptimos. Ningún flujo puede pasar ese corte, y ningún corte puede bajar de ese flujo.

Con cut_demo se ve en nuestra red, con el flujo máximo de valor 5:

$ build/cut_demo
La primera red, con su flujo máximo de valor 5:
  lado de s     capacidad   flujo neto
  {s}                  5            5
  {s, a}               6            5
  {s, b}               6            5
  {s, a, b}            5            5
  alcanzable en la red residual: {s}
  aristas del corte:  s -> a (3)  s -> b (2)
  capacidad: 5

Hay 4 cortes, porque a y b pueden caer de cualquier lado. En todos, el flujo neto es 5, y la capacidad es 5 o más.

Miremos el corte S = {s, b}, T = {a, t}, porque tiene una arista hacia atrás. Van de S a T: s → a (3) y b → t (3), y su capacidad es 6. Va de T a S: a → b, que no suma a la capacidad. Su flujo es 1. El flujo neto es 3 + 3 − 1 = 5, como dice el lema. Sin la resta daría 6, que es incorrecto.

Error común. Sumar también las aristas de T a S en la capacidad del corte. Con S = {s, b} darían 8, y no 6. Una arista que entra a S no limita lo que sale de S.

El teorema de flujo máximo y corte mínimo

El certificado de arriba sirve si existe un corte con el mismo valor que un flujo. El teorema dice que siempre existe, y al mismo tiempo que Ford-Fulkerson acierta.

Teorema (flujo máximo y corte mínimo). Sea f un flujo en una red. Las siguientes tres afirmaciones son equivalentes:

1. f es un flujo máximo.
2. La red residual G_f no tiene ningún camino de aumento.
3. Existe un corte (S, T) con |f| = c(S, T).

En consecuencia, el valor del flujo máximo es igual a la capacidad del corte mínimo.

Técnica. Demostrar el ciclo de implicaciones 1 ⇒ 2 ⇒ 3 ⇒ 1. La parte difícil es 2 ⇒ 3: hay que construir el corte, y se construye con lo alcanzable en la red residual.

(1 ⇒ 2). Por contraposición. Si G_f tuviera un camino de aumento, el lema de aumentar daría un flujo de valor |f| + δ, con δ > 0. Entonces f no sería máximo.

(2 ⇒ 3). Supongamos que G_f no tiene camino de s a t. Sea S el conjunto de nodos alcanzables desde s en G_f, y T el resto. El nodo s está en S, porque se alcanza a sí mismo. El nodo t no está en S, porque no hay camino. Entonces (S, T) es un corte. Falta ver que |f| = c(S, T). Por la observación de la igualdad, basta ver dos cosas.

Toda arista e de u a v, con u en S y v en T, está saturada. Supongamos que no: f(e) < c(e). Entonces el arco de ida u → v tiene capacidad residual positiva y está en G_f. Como u es alcanzable, v también lo sería, y v está en T. Es una contradicción.

Toda arista e de v a u, con v en T y u en S, tiene flujo 0. Supongamos que no: f(e) > 0. Entonces el arco inverso de e, que va de u a v, tiene capacidad residual f(e) > 0 y está en G_f. Otra vez v sería alcanzable. Es una contradicción.

Por lo tanto, por el lema del flujo neto,

|f| = f(S, T) = (suma de c(e) en las aristas de S a T) - 0 = c(S, T)

(3 ⇒ 1). Sea (S, T) un corte con |f| = c(S, T), y sea g cualquier flujo. Por la dualidad débil, |g| ≤ c(S, T) = |f|. Así que f es máximo.

Para la consecuencia, tomemos un flujo máximo f, que por (1 ⇒ 3) tiene un corte (S, T) de la misma capacidad. Todo corte tiene capacidad al menos |f|, por la dualidad débil. Entonces (S, T) es un corte mínimo, y el valor de f es igual a la capacidad del corte mínimo. ∎

Tres cosas para rescatar:

• Ford-Fulkerson es correcto. Se detiene cuando no hay camino de aumento. Por (2 ⇒ 1), lo que tiene en ese momento es un flujo máximo. Eso vale con cualquier regla de elección, siempre que termine.
• Existe un flujo máximo. Con capacidades enteras, Ford-Fulkerson termina, y el resultado es un flujo máximo. Con capacidades reales, la consecuencia sigue valiendo: Edmonds-Karp termina con cualquier capacidad, como veremos.
• La demostración es también un algoritmo. La parte (2 ⇒ 3) dice cómo encontrar el corte.

Idea clave. Hay un problema de máximo y otro de mínimo, en apariencia distintos, con la misma respuesta. Un flujo certifica que el corte mínimo no puede bajar más, y un corte certifica que el flujo máximo no puede subir más. Cuando el algoritmo termina, entrega los dos certificados a la vez.

Encontrar el corte mínimo

Es la cuarta pregunta de repaso. Dado un flujo máximo, el corte sale directo de la demostración:

algoritmo corte_minimo(red, f, s)
    S ← nodos alcanzables desde s en la red residual de f, con BFS o DFS
    corte ← lista vacía
    para cada arista e de la red original hacer
        si e va de un nodo de S a un nodo que no está en S entonces
            agregar e a corte
        fin si
    fin para
    devolver corte
fin algoritmo

Ya que Ford-Fulkerson acaba de hacer una búsqueda que no encontró a t, esa misma búsqueda da S. El costo adicional es O(E).

El recorrido de la última línea va por la red original, y este detalle importa. En nuestra clase, hay que mirar solo los arcos de número par. Un arco inverso que va de S a T no es una arista de la red: es la vuelta de una arista de T a S, con flujo 0. Si se recorre todo el arreglo de arcos, esas aristas se cuelan en el corte, y las capacidades ya no suman el flujo.

Nuestra red da S = {s}, y de ahí el corte {s → a, s → b}, de capacidad 5. Es la parte final de la primera salida de cut_demo. Fíjense en que la red tiene otro corte mínimo, S = {s, a, b}, con a → t y b → t, de capacidad 2 + 3 = 5. Este algoritmo da siempre el de S más pequeño. Todo corte mínimo contiene en S lo alcanzable, un hecho que queda para los ejercicios.

Una arista saturada no siempre cruza

Lo que todos quieren decir la primera vez es: “el corte mínimo son las aristas saturadas”. No es cierto. cut_demo lo muestra en la red s → a de 2, s → b de 2, a → b de 1, a → t de 1 y b → t de 2:

Una arista saturada que no cruza (s -> a 2, s -> b 2, a -> b 1, a -> t 1, b -> t 2):
  flujo máximo: 3, cortes mínimos: 1
  lado de s     capacidad   flujo neto
  {s}                  4            3
  {s, a}               4            3
  {s, b}               4            3
  {s, a, b}            3            3
  con BFS, alcanzable en la red residual: {s, a, b}
  aristas del corte:  a -> t (1)  b -> t (2)
  capacidad: 3
  aristas saturadas:
    s -> b (2)  no cruza
    a -> t (1)  cruza
    b -> t (2)  cruza
  suma de las saturadas: 5
  con otro flujo máximo del mismo valor (el camino más largo primero), alcanzable: {s, a, b}
  aristas del corte:  a -> t (1)  b -> t (2)
  capacidad: 3
  aristas saturadas:
    s -> a (2)  no cruza
    a -> b (1)  no cruza
    a -> t (1)  cruza
    b -> t (2)  cruza
  suma de las saturadas: 6

La tabla de cortes muestra que esta red tiene un solo corte mínimo: S = {s, a, b}, de capacidad 3. El flujo que da BFS satura s → b, y esa arista no cruza ese corte, ni ningún otro corte mínimo, porque no hay otro. Las saturadas suman 5, que no es el flujo.

Hay algo más. El segundo flujo máximo, del mismo valor, satura otras aristas: s → a y a → b, en lugar de s → b. Qué aristas no cruzadas quedan saturadas depende del flujo que encontró el algoritmo, mientras que las aristas de este corte son las mismas. Lo que el teorema dice es la dirección contraria: toda arista del corte, de S a T, está saturada. No toda saturada está en el corte.

Error común. Decir que el corte mínimo son las aristas saturadas. El corte se lee desde el conjunto S, alcanzable en la red residual: son las aristas de la red original que van de S a T. Comprobarlo es barato: sus capacidades tienen que sumar el valor del flujo.

Aumentar una arista del corte

Quinta pregunta de repaso: si se aumenta en 1 la capacidad de una arista del corte mínimo, ¿siempre aumenta el flujo máximo? No. Basta una cadena de dos aristas iguales, s → a de 5 y a → t de 5:

Dos cortes mínimos en serie (s -> a 5, a -> t 5):
  flujo máximo: 5, cortes mínimos: 2
  lado de s     capacidad   flujo neto
  {s}                  5            5
  {s, a}               5            5
  con s -> a de 6:          flujo 5
  con a -> t de 6:          flujo 5
  con las dos de 6:         flujo 6

Tiene dos cortes mínimos. Cada una de las dos aristas es, por sí sola, un corte mínimo. Si se agranda s → a, sube la capacidad de ese corte, y el otro sigue en 5. Si se agrandan las dos, recién sube el flujo. Cuando hay dos cuellos de botella en serie, arreglar uno no sirve.

Lo que sí es cierto, con capacidades enteras, son dos cosas. La primera: el flujo nunca sube más de 1, porque el corte mínimo anterior aumentó a lo sumo en 1, y su nueva capacidad sigue siendo un techo. La segunda: si el corte mínimo es único y la arista va de su S a su T, el flujo sí sube exactamente 1. Todo otro corte tenía capacidad de al menos una unidad más, y ese corte ahora también. La red de la arista saturada, que tiene un solo corte mínimo, lo ilustra:

Con un único corte mínimo (la red de la arista saturada), al aumentar en 1:
  s -> a: flujo 3
  s -> b: flujo 3
  a -> b: flujo 3
  a -> t: flujo 4
  b -> t: flujo 4

Solo las dos aristas del corte hacen subir el flujo. Las pruebas de la semana comprueban las dos afirmaciones en 2000 redes al azar.

En la práctica. Ampliar la red de una empresa es exactamente esta pregunta. Si la ampliación toca un cuello de botella que tiene otro en serie, no se gana nada. Antes de invertir, se mira si el corte mínimo es único, o se prueba con el flujo: se aumenta la capacidad en el modelo, y se vuelve a calcular.

Edmonds-Karp

Regresemos al problema que dejó pendiente la primera sesión: la cota O(E·f) depende de las capacidades, y el diamante mostró que no es una exageración. La causa está en lo que el pseudocódigo no decía: qué camino elegir.

La regla de Edmonds-Karp es la más simple que hay: elegir siempre un camino de aumento con la menor cantidad de aristas. Se encuentra con BFS en la red residual, ignorando las capacidades salvo para saber si un arco está presente.

algoritmo edmonds_karp(red, s, t)
    para cada arista e hacer
        f[e] ← 0
    fin para
    mientras verdadero hacer
        ejecutar BFS desde s en la red residual, guardando llegada[v], el arco por el que se llegó a v
        si t no se alcanzó entonces
            salir del ciclo
        fin si
        P ← los arcos de t hacia atrás hasta s, siguiendo llegada
        δ ← menor capacidad residual entre los arcos de P
        aumentar f por P en δ
    fin mientras
    devolver f
fin algoritmo

En el programa, es pasarle otra regla a ford_fulkerson:

// Regla de Edmonds-Karp: el camino de aumento con menos aristas, con BFS. Vacío si no hay.
inline std::vector<int> shortest_path_rule(const FlowNetwork& net, int source, int sink) {
    std::vector<int> arc_into(static_cast<std::size_t>(net.node_count()), -1);
    std::queue<int> pending;
    pending.push(source);
    while (!pending.empty() && arc_into[static_cast<std::size_t>(sink)] < 0) {
        const int u = pending.front();
        pending.pop();
        for (int arc : net.arcs_from(u)) {
            const int v = net.head(arc);
            if (v != source && net.residual(arc) > 0 && arc_into[static_cast<std::size_t>(v)] < 0) {
                arc_into[static_cast<std::size_t>(v)] = arc;
                pending.push(v);
            }
        }
    }
    std::vector<int> path;
    if (arc_into[static_cast<std::size_t>(sink)] < 0) return path;
    for (int v = sink; v != source; v = net.tail(arc_into[static_cast<std::size_t>(v)])) {
        path.push_back(arc_into[static_cast<std::size_t>(v)]);
    }
    std::reverse(path.begin(), path.end());
    return path;
}

// Edmonds-Karp es Ford-Fulkerson con la regla del camino más corto.
inline FlowRun edmonds_karp(FlowNetwork& net, int source, int sink, std::vector<Augmentation>* log = nullptr) {
    return ford_fulkerson(net, source, sink, shortest_path_rule, log);
}

Aquí arc_into[v] guarda el arco por el que se llegó a v, y sirve también para marcar los nodos visitados. La fuente no tiene arco de llegada, y por eso la condición v != source.

Teorema (Edmonds-Karp). Con cualquier capacidad, entera o no, Edmonds-Karp hace O(VE) aumentos y cuesta O(VE²).

El punto es que V y E son el tamaño del grafo. Las capacidades ya no aparecen. A continuación damos la idea de la demostración, no una demostración completa. Son tres pasos, y el primero es el corazón.

Sigamos un ejemplo. El programa ek_trace corre una red de seis nodos: s → b de 4, s → c de 6, a → t de 3, b → a de 6, b → d de 5, c → a de 2, c → b de 2 y d → t de 5. Después de cada vuelta imprime la distancia en aristas desde s hasta cada nodo, en la red residual. Un guion significa que el nodo ya no se alcanza. En los nombres, -> es un arco de ida.

$ build/ek_trace
  distancias: s=0 a=2 b=1 c=1 d=2 t=3
vuelta 1: s > b > a > t   3 aristas, empuja 3
  críticas: a->t
  distancias: s=0 a=2 b=1 c=1 d=2 t=3
vuelta 2: s > b > d > t   3 aristas, empuja 1
  críticas: s->b
  distancias: s=0 a=2 b=2 c=1 d=3 t=4
vuelta 3: s > c > b > d > t   4 aristas, empuja 2
  críticas: c->b
  distancias: s=0 a=2 b=3 c=1 d=4 t=5
vuelta 4: s > c > a < b > d > t   5 aristas, empuja 2
  críticas: c->a b->d d->t
  distancias: s=0 a=- b=- c=1 d=- t=-
flujo máximo: 8, corte mínimo por fuerza bruta: 8

Sigamos a mano la búsqueda de la vuelta 4, que es la interesante. Después de la vuelta 3, las capacidades residuales positivas que salen de cada nodo son estas. El símbolo ⇒ marca un arco inverso.

Y este es el BFS, un nodo por fila. La columna de la derecha es lo que se agrega a la cola:

El camino es s → c → a ⇒ b → d → t, de 5 aristas, con capacidades 4, 2, 3, 2 y 2. Empuja 2. Tres arcos llegan a 0 a la vez: c → a, b → d y d → t. Lo que pasa por el inverso a ⇒ b es que el flujo de b → a baja de 3 a 1. Dos unidades que iban de b a a se quedan en b y siguen por b → d, y las que llegan a a desde c ocupan su lugar en a → t.

Después de esa vuelta, la salida dice que solo s y c se alcanzan. Entonces S = {s, c}, y el corte se lee en la red original: de S a T van s → b de 4, c → a de 2 y c → b de 2, que suman 8. Es el valor del flujo. c → a y c → b, ambas saturadas, salen de S. b → d y d → t también están saturadas, pero sus dos extremos están en T: otras dos aristas saturadas que no cruzan.

Miren ahora las distancias, columna por columna. Ninguna baja. b pasa por 1, 1, 2, 3, y t pasa por 3, 3, 4, 5. Eso no es casualidad.

Paso 1: las distancias nunca bajan. Sea d(x) la distancia en aristas desde s hasta x en la red residual de ahora. Como d son distancias de BFS, cualquier arco de x a y cumple d(y) ≤ d(x) + 1: un arco no puede saltarse niveles hacia adelante. Al aumentar por un camino más corto, algunos arcos pueden desaparecer y otros pueden aparecer. Los que aparecen son inversos de arcos del camino. Como el camino es más corto, sus arcos van de un nivel k a un nivel k + 1, y sus inversos van de k + 1 a k. Hacia atrás. Esos arcos también cumplen d(y) ≤ d(x) + 1. Por lo tanto, en la red nueva, todos los arcos siguen cumpliendo esa desigualdad con las d viejas. Un camino desde s avanza a lo sumo un nivel viejo por arco, y para llegar a x necesita al menos d(x) arcos. La distancia nueva de x no es menor que la vieja.

Paso 2: un arco es crítico O(V) veces. Un arco del camino es crítico (critical) si su capacidad residual es igual al cuello de botella: al empujar, desaparece. Todo aumento tiene al menos un arco crítico. En la salida de arriba, por ejemplo, la última vuelta tiene tres. Supongamos que x → y es crítico en un momento, cuando el camino más corto lo usa. Entonces d(y) = d(x) + 1. Para que vuelva a aparecer, hace falta empujar por su inverso y → x, lo que solo ocurre si un camino más corto posterior lo usa. En ese momento, con las distancias d’ de entonces, d’(x) = d’(y) + 1. Como las distancias no bajan, d’(y) ≥ d(y), y entonces

d'(x) = d'(y) + 1 ≥ d(y) + 1 = d(x) + 2

Entre dos veces consecutivas en que x → y es crítico, la distancia de x sube al menos 2. Y, mientras x esté en un camino hacia t, su distancia es a lo sumo V − 2. Así que cada arco es crítico a lo sumo V/2 veces.

Paso 3: sumar. Hay 2E arcos y cada uno es crítico a lo sumo V/2 veces. Cada aumento gasta al menos un “crítico”. Por eso hay a lo sumo VE aumentos. Cada aumento cuesta un BFS, de O(E). El total es O(VE²).

¿Qué le falta a esto para ser una demostración completa? Sobre todo, escribir con cuidado el paso 1, por inducción sobre los aumentos, con los nodos que dejan de ser alcanzables. El libro de Erickson y CLRS tienen la versión larga. Las pruebas de la semana comprueban cada afirmación en 3000 redes al azar: las distancias no bajan, un nodo inalcanzable sigue así, cada arco es crítico a lo sumo V/2 veces, y las vueltas no pasan de VE.

Comparar con los números

En el diamante, BFS hace 2 iteraciones, frente a los 2 000 000 de la regla adversaria, según la tabla de bad_capacities. No depende de M, porque BFS nunca toca la arista del medio: los caminos s → a → t y s → b → t tienen menos aristas.

Si se multiplican todas las capacidades por un factor, BFS sigue exactamente las mismas vueltas, porque solo mira qué arcos tienen capacidad positiva. La segunda parte de la salida de ek_trace lo muestra:

Las mismas iteraciones si todas las capacidades se multiplican:
  por       1: flujo         8, iteraciones 4
  por    1000: flujo      8000, iteraciones 4
  por 1000000: flujo   8000000, iteraciones 4

¿Y en redes más grandes? El programa iterations_bench genera redes por capas: la fuente, varias capas de 10 nodos, el sumidero, y cada nodo con 3 aristas a nodos al azar de la capa siguiente, con capacidades de hasta 10⁹. Compara BFS con la regla de DFS. Se mide con -O2, en una sola corrida por fila, así que los tiempos dependen de la máquina y sirven para comparar órdenes de magnitud, no decimales:

$ build/iterations_bench
      V       E   regla           flujo iteraciones          VE         ms
    102     290     BFS      2942603981          60       29580        0.1
    102     290     DFS      2942603981        1297       29580        1.9
    202     590     BFS      2375625399          79      119180        0.3
    202     590     DFS      2375625399       16299      119180       42.2
    402    1190     BFS      2942603981         192      478380        1.3
    402    1190     DFS      2942603981     1028098      478380     4576.3

La red de 402 nodos, con las aristas agregadas en orden al azar:
      V       E   regla           flujo iteraciones          VE         ms
    402    1190     BFS      2942603981         198      478380        1.6
    402    1190     DFS      2942603981        6292      478380       24.4

La misma red de 402 nodos con otras capacidades máximas, solo BFS:
      V       E   regla           flujo iteraciones          VE         ms
    402    1190     BFS              48          48      478380        0.6
    402    1190     BFS            3434         185      478380        1.3
    402    1190     BFS         4854818         292      478380        2.3
    402    1190     BFS      2942603981         192      478380        1.3

Tres cosas se pueden leer, y no conviene leer más, porque son unas pocas redes de una sola familia.

BFS queda muy por debajo de su cota de VE vueltas. La cota es de peor caso, y en estas redes hizo cientos de vueltas donde la cota permite cientos de miles. En la última tabla, las capacidades son otras en cada fila, y el número de vueltas cambia con ellas, sin crecer junto con el flujo. La fila de capacidades hasta 10 tiene 48 vueltas con flujo 48, y cada vuelta empujó 1.

DFS hizo, en la red más grande, más de un millón de vueltas, unas 5000 veces más que BFS, y por encima de VE. Es una sola medición, y no dice cómo crece con la red.

La misma red, con las aristas agregadas en otro orden, cambia las vueltas de DFS de 1028098 a 6292, y BFS casi no cambia. La regla de DFS, tal como la escribimos, depende mucho del orden de los arcos. No tenemos una cota que explique estos números, y por eso no les atribuimos una causa. Lo que sí sabemos es lo que garantiza cada regla: para BFS, a lo sumo VE vueltas con cualquier orden; para DFS, solo que el número de vueltas no pasa de f.

Pongamos la diferencia en números para una red de 500 nodos y 5000 aristas, con capacidades de hasta 10⁹. Sin aristas paralelas, de s salen a lo sumo 499 aristas, así que el flujo puede llegar a unos 5 × 10¹¹. La cota O(E·f) es del orden de 2,5 × 10¹⁵ pasos, que no sirve de nada. La cota O(VE²) es del orden de 1,25 × 10¹⁰, que es pesimista, pero ya no depende del tamaño de las capacidades.

Idea clave. Una regla simple cambia un costo que depende de los números por uno que depende solo del tamaño del grafo. La cota O(VE²) casi nunca se alcanza, pero es una garantía, y en un juez o en producción una garantía importa más que un buen promedio.

Comprobar una respuesta sin confiar en el programa

El teorema tiene una consecuencia muy práctica. Un flujo y un corte de la misma capacidad son un certificado: quien los recibe puede comprobar que son óptimos sin saber cómo se calcularon, y sin volver a correr ningún algoritmo. Basta revisar tres cosas, cada una en O(V + E):

1. El flujo cumple la definición: capacidades y conservación.
2. Los nodos de S y T son una partición, con s en S y t en T.
3. El valor del flujo es igual a la suma de las capacidades de las aristas de S a T.

Si las tres se cumplen, la dualidad débil dice que el flujo es máximo y el corte es mínimo, siempre que las capacidades de la revisión sean las de la entrada, y no las que el programa haya calculado. Eso es lo que hace un verificador de verdad, como el del problema opcional: lee las capacidades de la entrada.

En nuestras pruebas, flow_is_valid revisa la primera condición sobre la clase:

inline bool flow_is_valid(const FlowNetwork& net, int source, int sink) {
    std::vector<long long> net_out(static_cast<std::size_t>(net.node_count()), 0);
    for (int e = 0; e < net.edge_count(); e++) {
        const int edge = 2 * e;
        const long long f = net.flow_on(edge);
        if (f < 0 || f > net.capacity(edge)) return false;
        net_out[static_cast<std::size_t>(net.tail(edge))] += f;
        net_out[static_cast<std::size_t>(net.head(edge))] -= f;
    }
    for (int v = 0; v < net.node_count(); v++) {
        if (v != source && v != sink && net_out[static_cast<std::size_t>(v)] != 0) return false;
    }
    return true;
}

Fíjense en que el ciclo avanza de una arista a otra multiplicando por 2: recorre solo los números pares, las aristas originales. Es la misma idea con la que se lee un corte.

Esta función tiene un límite. flow_on y capacity se calculan con las capacidades residuales que el propio algoritmo modificó, así que confía en que push conserve la suma de cada par. Un push que le quite a un arco sin darle a su par haría que todo flujo se leyera como 0, y pasaría esta revisión. Por eso las pruebas de la semana calculan además, antes de correr el algoritmo, el corte mínimo por fuerza bruta, y comparan con él.

La ventaja de un certificado es que no necesita una solución de referencia. Volveremos a la idea en la semana 13, con otro propósito.

Casos de borde

Estos casos están en test_examples.cpp. Conviene pensarlos antes de escribir cualquier programa de flujo.

Y estos son los errores de programación más comunes:

En la práctica: otros algoritmos

Edmonds-Karp es lo que van a programar en este curso, y alcanza para redes de miles de aristas. No es lo mejor que se conoce. Otros algoritmos tienen mejores cotas de peor caso. Dos familias son muy usadas:

• Dinic. También trabaja con distancias de BFS, pero en cada fase aprovecha todos los caminos más cortos a la vez. Cuesta O(V²E).
• Los de preflujo (push-relabel). Dejan de mantener la conservación durante el proceso, y empujan exceso de un nodo a otro. Por ejemplo, la biblioteca Boost Graph trae push_relabel_max_flow.

Si un proyecto real necesita flujo en un grafo grande, lo razonable es usar una biblioteca, no escribir esto de nuevo. Lo que no cambia es lo que se aprendió aquí: qué es un flujo, qué certifica un corte, cómo se lee la respuesta y, sobre todo, cómo se convierte un problema en una red. Eso es la semana 12.

El código de la semana

En code/week-11:

flow.h es lo que van a reutilizar la próxima semana. Da el flujo y el lado de la fuente, residual_side, y no da la lista de aristas del corte, porque eso depende de cómo cada problema numera sus aristas.

Las pruebas se compilan con -g -fsanitize=address,undefined. La medición va con -O2 y sin sanitizers.

$ make test
mkdir -p build
g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined test_examples.cpp -o build/test_examples
build/test_examples
Todas las pruebas de la semana 11 pasaron.

Estas pruebas comprueban, entre otras cosas, lo siguiente:

• Los pares: add_edge devuelve números pares, e ^ 1 es la inversa, y dos aristas antiparalelas no se mezclan.
• En la primera red: el greedy da 4, todas sus secuencias dan 4 o 5, en las proporciones del texto, y Ford-Fulkerson da 5 usando una inversa en la segunda vuelta. La inversa con capacidad c da un flujo donde no lo hay.
• En el diamante: exactamente 2M iteraciones con la regla adversaria, hasta M = 10⁶, y 2 con BFS. El flujo de M = 2 × 10⁹ no cabe en int.
• En 3000 redes al azar, con aristas paralelas y antiparalelas, y con aristas que entran a la fuente y salen del sumidero: las reglas BFS, DFS y, con capacidades pequeñas, la adversaria dan lo mismo que la fuerza bruta sobre todos los cortes. Cada flujo cumple la definición, el flujo neto por todo corte es igual al valor y no supera la capacidad. En el corte de lo alcanzable, las aristas de S a T están saturadas, las de T a S llevan 0 y la capacidad es igual al valor.
• La arista saturada que no cruza está en una red con un solo corte mínimo, comprobado con fuerza bruta.
• Aumentar en 1 una arista: el flujo sube 0 o 1, y sube 1 si el corte es único y la arista lo cruza.
• Edmonds-Karp: las distancias no bajan, cada arco es crítico a lo sumo V/2 veces y hay a lo sumo VE vueltas. Las vueltas no cambian al multiplicar las capacidades.

El problema opcional

En esta semana, la sesión de laboratorio es la Práctica 3, de programación dinámica. El problema de la carpeta lab/network_capacity, la capacidad de una red de oleoductos, queda como ejercicio opcional. Tiene su enunciado, un esqueleto y sus casos: entren a la carpeta y corran make test. El esqueleto lee la entrada y responde con una lista que corta la red, pero que casi nunca es la correcta. Puede haber varias listas válidas, así que el problema trae un verificador.

Resumen

• Red de flujo: grafo dirigido con capacidades, fuente s y sumidero t. Un flujo respeta las capacidades y conserva en los nodos intermedios. Su valor |f| es lo que sale de s, neto. Se permiten aristas antiparalelas y paralelas, cada una con su flujo.
• El greedy falla: empujar por caminos sin volver atrás da 4 en una red de máximo 5. El resultado depende de la elección.
• Red residual: por cada arista, un arco de ida con c − f y un arco inverso con f. Un camino de aumento es un camino de s a t en ella, y aumentar da otro flujo, de valor |f| + δ.
• Ford-Fulkerson: mientras haya un camino de aumento, empujar. No dice qué camino.
• Integralidad: con capacidades enteras, termina con un flujo entero, en a lo sumo f aumentos. Por inducción: todo residual es entero, así que δ ≥ 1.
• Costo: O(E·f), con f el valor del flujo máximo y cada búsqueda en O(E). Es pseudopolinomial. En el diamante, con capacidades de 10⁶ y una arista de 1 en medio, una mala regla hace 2 × 10⁶ iteraciones.
• En C++: aristas en pares, e par y su inversa e ^ 1, creadas juntas, la inversa con capacidad 0. Se guardan solo los residuales. long long para los totales.
• Corte: partición (S, T) con s en S y t en T. La capacidad suma solo las aristas de S a T. El flujo neto por todo corte es |f|, y entonces |f| ≤ c(S, T).
• Teorema: f es máximo, no hay camino de aumento, y existe un corte con |f| = c(S, T) son equivalentes. El flujo máximo es igual al corte mínimo.
• Encontrar el corte: S es lo alcanzable en la red residual. Las aristas del corte se leen en la red original, de S a T. Sus capacidades suman el flujo.
• No toda arista saturada cruza el corte, y aumentar una arista del corte no siempre aumenta el flujo, si hay dos cortes mínimos en serie.
• Edmonds-Karp: el camino de aumento con menos aristas, con BFS. Las distancias no bajan, y cada arco es crítico O(V) veces, así que hay O(VE) aumentos. O(VE²), sin depender de las capacidades.
• En la práctica: Dinic y los algoritmos de preflujo tienen mejores cotas de peor caso. Lo que se aprende aquí es modelar.

Ejercicios

1. A mano. Corran Ford-Fulkerson en la red s → a de 3, s → b de 3, a → b de 3, a → t de 2 y b → t de 3. Empiecen por el camino s → a → b → t, que obliga a usar después un arco inverso. Escriban la tabla de flujos, vuelta por vuelta, y den un corte con la misma capacidad. Comprueben con build_network y edmonds_karp.
2. Una arista que vuelve. Den un flujo y un corte en una red con al menos una arista de T a S con flujo positivo. Calculen f(S, T) y c(S, T). Luego expliquen en qué línea de la dualidad débil se usa que f(e) ≥ 0.
3. Saldo. Demuestren que el saldo de t es −|f|: lo que entra a t, neto, es igual a lo que sale de s, neto. Usen el lema del flujo neto con S = V − {t}.
4. El corte más cercano a t. Sea T’ el conjunto de nodos desde los que se puede llegar a t en la red residual de un flujo máximo, y S’ el resto. Demuestren que (S’, T’) es un corte mínimo. Den una red en la que difiera del corte que da S alcanzable, y compruébenlo con el programa.
5. Todos los cortes mínimos contienen lo alcanzable. Sea f un flujo máximo y S₀ lo alcanzable desde s en G_f. Demuestren que todo corte mínimo (S, T) cumple S₀ ⊆ S. Sugerencia: si (S, T) es mínimo, sus aristas de S a T están saturadas y las de T a S llevan 0. ¿Qué dice eso sobre los arcos residuales que salen de S?
6. Un corte único. Demuestren que la red tiene un solo corte mínimo si y solo si todo nodo se alcanza desde s, o llega a t, en la red residual de un flujo máximo. Usen los dos ejercicios anteriores, y pruébenlo con count_min_cuts en redes al azar.
7. Capacidades en los nodos. Supongan que cada nodo v tiene además una capacidad n(v), y que por él no puede pasar más que eso. Transformen la red en una red normal, y demuestren que el flujo máximo es el mismo. Modifiquen el programa.
8. Varias fuentes y varios sumideros. Hay varios nodos de origen y varios de destino, y no importa de cuál sale o a cuál llega. Reduzcan el problema a una sola fuente y un solo sumidero. Demuestren que el valor máximo es el mismo, en las dos direcciones.
9. Regla de mayor capacidad. Elijan siempre el camino de aumento con el mayor cuello de botella. Escriban la regla, con una variante de Dijkstra, y comparen sus iteraciones con las de BFS en el diamante y en las redes de iterations_bench. No se pide demostrar una cota.
10. Descomponer un flujo. Dado un flujo entero de valor v, demuestren que se puede escribir como v caminos de s a t, más ciclos, en los que cada arista e se usa f(e) veces en total. Escriban el programa que los encuentra, y compruébenlo con el flujo de la primera red.
11. La arista del medio. En el diamante, cambien la capacidad de la arista del medio a k, con 1 ≤ k ≤ M. Calculen cuántas iteraciones hace la regla del camino más largo, y comprueben con longest_path_rule para varios valores de M y de k. Expliquen el resultado con δ.
12. El paso 1 completo. Escriban la demostración por inducción de que las distancias residuales no bajan en Edmonds-Karp, incluidos los nodos que dejan de alcanzarse. Usen el argumento de los niveles de estos apuntes.