Fluxo máximo: algoritmo Push-relabel

label = rótulo, push = empurrar

O algoritmo push-relabel (também conhecido como preflow-push) é um algoritmo para calcular o fluxo máximo de uma rede de fluxo. A definição exata do problema que queremos resolver pode ser encontrada no artigo - Fluxo máximo: Ford-Fulkerson e Edmonds-Karp.

Neste artigo, consideraremos a solução do problema puxando um pré-fluxo pela rede, que será executada em $O(V^4)$, ou mais precisamente em tempo $O(V^2 E)$. O algoritmo foi projetado por Andrew Goldberg e Robert Tarjan em 1985.

Definições

Durante o algoritmo, teremos que lidar com um pré-fluxo ou seja, uma função $f$ que é semelhante à função de fluxo, mas não satisfaz necessariamente a restrição de conservação de fluxo. Para isso, apenas as restrições $$0 \le f(e) \le c(e)$$ e $$\sum_{(v, u) \in E} f((v, u)) \ge \sum_{(u, v) \in E} f((u, v))$$ devem ser válidas.

Portanto, é possível que algum vértice receba mais fluxo do que distribui. Dizemos que esse vértice tem algum excesso de fluxo e definimos sua quantidade com a função de excesso $x(u) =\sum_{(v, u) \in E} f((v, u)) - \sum_{(u, v) \in E} f((u, v))$.

Da mesma forma que com a função de fluxo, podemos definir as capacidades residuais e o grafo residual com a função de pré-fluxo.

O algoritmo começará com um pré-fluxo inicial (alguns vértices terão excesso de fluxo) e, durante a execução, o pré-fluxo será tratado e modificado. Dando alguns detalhes, o algoritmo selecionará um vértice com excesso e empurrará o excesso para os vértices vizinhos. Isso será repetido até que todos os vértices, exceto a fonte e o coletor(vértices source $s$ e sink $t$), estejam livres de excesso. É fácil ver que um pré-fluxo sem excesso é um fluxo válido. Isso faz com que o algoritmo termine com um fluxo real.

Ainda existem dois problemas no qual temos que lidar. Primeiro, como garantimos que isso realmente termina? E segundo, como garantimos que isso realmente nos dará um fluxo máximo, e não apenas um fluxo aleatório?

Para resolver esses problemas, precisamos da ajuda de outra função, as funções que servem para rotular $h$, também chamadas de funções de altura, que atribui a cada vértice um número inteiro. Chamamos uma rotulagem de válida, se $h(s) = |V|$, $h(t) = 0$, e $h(u) \le h(v) + 1$ se houver uma aresta $(u, v)$ no grafo residual - ou seja, a aresta $(u, v)$ tem uma capacidade positiva no grafo residual. Em outras palavras, se é possível aumentar o fluxo de $u$ a $v$, assim, a altura de $v$ pode ser no máximo uma vez menor que a altura de $u$, mas pode ser igual ou até maior.

É importante observar que, se existe uma função de rotulagem válida, não existe um augmenting path de $s$ a $t$ no grafo residual. Porque esse caminho terá um comprimento de no máximo $|V| - 1$ arestas, e cada aresta pode diminuir a altura em no máximo por um, o que é impossível se a primeira altura for $h(s) = |V|$ e a última altura for $h(t) = 0$.

Usando esta função de rotulagem, podemos declarar a estratégia do algoritmo push-relabel. Começamos com um pré-fluxo válido e uma função de rotulagem válida. Em cada etapa, empurramos algum excesso entre os vértices e atualizamos os rótulos dos vértices. Temos que garantir que, após cada etapa, que o pré-fluxo e a rotulagem ainda sejam válidos. Se o algoritmo determinar então que o pré-fluxo é um fluxo válido e como também temos uma rotulagem válida, não existe um caminho entre $s$ e $t$ no grafo residual, o que significa que o fluxo é realmente um fluxo máximo (essa parte é bem confusa, é importante tentar problemas relacionados).

Se compararmos o algoritmo de Ford-Fulkerson com o algoritmo push-relabel, parece que os algoritmos são duais um do outro. O algoritmo Ford-Fulkerson mantém um fluxo válido o tempo todo e o aprimora até que não exista mais um caminho augmenting path, enquanto no algoritmo push-re-label não existe um augmenting path em nenhum momento, e melhoraremos o pré-fluxo até que seja um fluxo válido.

Algoritmo

Primeiro, precisamos inicializar o grafo com uma função válida de pré-fluxo e rotulagem.

Usar o pré-fluxo vazio - como é feito no algoritmo Ford-Fulkerson - não é possível, porque haverá um "augmenting path" e isso implica que não existe uma rotulagem válida. Portanto, inicializaremos cada aresta saindo de $s$ com sua capacidade máxima: $f((s, u)) = c((s, u))$. E todas as outras arestas com zero. Nesse caso, existe uma rotulagem válida, ou seja $h(s) = |V|$ para o vértice fonte e $h(u) = 0$ para todos os outros.

Agora vamos descrever as duas operações com mais detalhes.

Com a operação push tentamos empurrar o excesso de fluxo de um vértice $u$ para um vértice vizinho $v$. Temos uma regra: só podemos empurrar o fluxo de $u$ para $v$ se $h(u) = h(v) + 1$. Em termos leigos, o excesso de fluxo deve fluir para baixo, mas de uma forma não muito "brusca". É claro que só podemos "empurrar" $\min(x(u), c((u, v)) - f((u, v)))$ fluxo.

Se um vértice tem excesso, mas não é possível empurrar o excesso para nenhum vértice adjacente, precisamos aumentar a altura desse vértice. Chamamos essa operação de relabel. Vamos aumentá-lo o máximo possível, mantendo a validade da rotulagem.

Para recapitular, o algoritmo em poucas palavras é: Inicializamos um pré-fluxo válido e uma rotulagem válida. Enquanto possamos executar as operações push ou relabel, nós continuamos a realizar elas. Depois, o pré-fluxo é na verdade um fluxo e nós o retornamos.

Complexidade

É fácil mostrar que o rótulo máximo de um vértice é $2|V| - 1$. Nesse ponto, todo o excesso restante pode e será enviado de volta à fonte. Isso fornece no máximo $O(V^2)$ operações de rotulagem.

Também pode ser demonstrado que haverá no máximo $O(V E)$ "empurrões saturados" (um impulso em que a capacidade total da aresta é usada) e no máximo $O(V^2 E)$ não-saturados (um empurrão em que a capacidade de uma aresta não é totalmente utilizada). Se escolhermos uma estrutura de dados que nos permita encontrar o próximo vértice com excesso em $O(1)$, a complexidade total do algoritmo é $O(V^2 E)$.

Implementação

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()
{
    height.assign(n, 0);
    height[0] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[0] = inf;
    for (int i = 1; i < n; i++)
        push(0, i);
    seen.assign(n, 0);

    while (!excess_vertices.empty()) {
        int u = excess_vertices.front();
        excess_vertices.pop();
        if (u != 0 && u != n - 1)
            discharge(u);
    }

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

Aqui usamos a queue excess_vertices para armazenar todos os vértices que atualmente têm excesso. Dessa forma, podemos escolher o próximo vértice para uma operação push ou re-label em tempo constante.

E para garantir que não gastemos muito tempo localizando o vértice adjacente para o qual podemos enviar o excesso de fluxo, usamos uma estrutura de dados chamada current-arc. Basicamente, iteraremos sobre as arestas em uma ordem circular e sempre armazenaremos a última aresta que usamos. Dessa forma, para um determinado valor de rotulagem, alternaremos a aresta atual apenas $O(n)$ vezes. E como a re-rotulagem já leva tempo $O(n)$, não pioramos a complexidade.