Algoritmos para Grafos  |  Índice

Implementação do algoritmo de Ford-Fulkerson

Nossa implementação do algoritmo de Ford-Fulkerson tem uma camada interna (que procura por pseudocaminhos aumentadores) e uma camada externa (que usa os pseudocaminhos para calcular um fluxo máximo).  Este capítulo trata da camada externa.  Implementações da camada interna serão discutidas nos capítulos seguintes.

A escolha de uma boa estrutura de dados é fundamental para uma implementação eficiente do algoritmo de Ford-Fulkerson.  Teremos que fazer várias decisões de projeto, nem todas muito confortáveis.

Sumário:

Estrutura de dados: nós expandidos

Em princípio, a estrutura de dados de que precisamos para representar grafos capacitados é muito simples:  basta adaptar a estrutura que já definimos para grafos com custos nos arcos, trocando custo por capacidade.  Entretanto, uma implementação eficiente do algoritmo de Ford-Fulkerson exige de uma estrutura de dados mais rica, que permita a manipulação de pseudocaminhos.  Para dar suporte a essa estrutura mais rica, convém expandir os nós das listas de adjacência, adicionando a eles alguns campos auxiliares. Assim, além dos campos usuais w e next, teremos

Um nó com esses campos será chamado nó expandido.

typedef struct node *link;
struct node { // nó expandido
   vertex w; 
   int c; 
   int flow; 
   int type; 
   link twin; 
   link next;
};

Para especificar uma instância do problema do fluxo máximo, somente os campos  wc,  e  next  são necessários.  Suporemos portanto que os campos flow, type, e twin estão em branco por enquanto;  eles serão preenchidos durante a execução do algoritmo.

Exercícios 1

  1. Entrada de dados.  Escreva uma função que receba um arquivo contendo uma instância do problema do fluxo máximo e construa as correspondentes listas de adjacência com nós expandidos. (O valor dos campos flow, type, e twin ficará indefinido.)  A primeira linha do arquivo de dados especifica o número de vértices e o número de arcos do grafo; a segunda linha especifica os vértices inicial e final; cada uma das linhas seguintes especifica um arco e sua capacidade. Exemplo:
    6 8
    0 5
    0-1   2
    0-2   3
    1-3   3
    1-4   1
    2-3   1
    2-4   1
    3-5   2
    4-5   3
    
  2. Grafo capacitado aleatório.  Escreva uma função que construa uma instância aleatória do problema do fluxo máximo. A instância deve ter V vértices e A arcos e deve ser representada por listas de adjacência com nós expandidos. (O valor dos campos flow, type, e twin ficará indefinido.) As capacidades devem ser escolhidas aleatoriamente no intervalo fechado 0..M-1. Os vértices inicial e final também devem ser escolhidos aleatoriamente.

Arcos artificiais

É difícil procurar pseudocaminhos num grafo por causa dos arcos reversos dos pseudocaminhos.  Para enfrentar essa dificuldade, vamos acrescentar alguns arcos auxiliares ao nosso grafo. Graças a esses arcos, será possível trabalhar só com caminhos tradicionais, sem o pseudo.

Para cada arco v-w, acrescentaremos ao grafo um novo arco  w-vantiparalelov-w.  Diremos que os novos arcos são artificiais e os antigos são originais.  Da mesma forma que o arco original v-w é representado por um nó expandido  a  na lista adj[v], o correspondente arco artificial w-v será representado por um nó expandido b na lista adj[w]:

     b = malloc( sizeof (struct node));
     b->w = v; 
     b->twin = a;
     a->twin = b;
     b->next = G->adj[w];     
     G->adj[w] = b;

Usaremos o campo twin para que a possa ser facilmente localizado a partir de b e vice-versa.  O campo  type  indicará o tipo do arco:  +1 se o arco for original e -1 se for artificial:

     a->type = +1; 
     b->type = -1; 

O novo grafo, depois da adição dos arcos artificiais, será chamado grafo expandido.   (Os arcos artificiais introduzem um pequeno desconforto técnico: se o grafo original tiver arcos antiparalelos, o correspondente grafo expandido terá arcos paralelos, o que entra em choque com nossa proibição de tais arcos.  Felizmente, nossa estrutura de dados aceita arcos paralelos com naturalidade.)

Ao trabalhar com o grafo expandido, gostaríamos de ignorar a distinção entre arcos artificiais e originais, tratando todos da mesma maneira. Para isso, é preciso que cada arco artificial tenha uma capacidade bem como um fluxo. Como essa capacidade e esse fluxo devem ser definidos?  Essa é uma decisão de projeto importante.  Adotaremos a seguinte definição: cada arco artificial terá capacidade zero e fluxo igual ao negativo do fluxo no correspondente arco original:

     b->c = 0; 
     b->flow = -a->flow;

Como flow é positivo nos arcos originais, a desigualdade flowc valerá em todo arco artificial. Essa desigualdade também vale, por hipótese, em todos os arcos originais.  (Mas os campos flow dos nós não definem um fluxo no grafo expandido.)

Sedgewick-part5-java/capacitated-network-prog-22-2.png

Exemplo A.  Considere o grafo cujos arcos estão indicados a seguir junto com as respectivas capacidades (segunda linha da tabela). O vértice inicial é 0 e o vértice final é 5. A terceira linha da tabela define um fluxo que respeita as capacidades.

0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 
  2   3   3   1   1   1   2   3
  2   2   1   1   1   1   2   2    

Veja a seguir o correspondente grafo expandido (os arcos artificiais estão em vermelho):

0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 1-0 2-0 3-1 4-1 3-2 4-2 5-3 5-4
  2   3   3   1   1   1   2   3   0   0   0   0   0   0   0   0
  2   2   1   1   1   1   2   2  -2  -2  -1  -1  -1  -1  -2  -2

Exercícios 2

  1. Verifica fluxo.  Suponha dado um grafo expandido G com vértice inicial s e vértice final t e com fluxo definido pelos campos flow dos nós expandidos.  Escreva uma função checkFlow() que verifique se os campos flow descrevem um fluxo no grafo original. Verifique também se o fluxo respeita as capacidades.  Sua função deve devolver a intensidade do fluxo ou -1 se algo estiver errado.
  2. Escreva uma função que calcule uma macarronada que represente um dado fluxo num grafo. Sua função deve receber um grafo expandido, com vértice inicial s, vértice final t, e um fluxo (representado nos campos flow dos nós). Sua função deve imprimir uma coleção de caminhos que represente o fluxo. Para cada caminho, deve imprimir também a quantidade de fluxo que cada caminho conduz.
  3. [Sedgewick 22.3] Fluxo em quase-árvore radicada.  Seja G um grafo expandido com vértice inicial s e vértice final t. Suponha que o grafo G − t é uma árvore radicada com raiz s.  Descreva um algoritmo para calcular um fluxo máximo que respeite as capacidades e um corte mínimo.

Caminhos aumentadores e capacidades residuais

Com a introdução dos arcos artificiais, os pseudocaminhos do grafo original podem ser representados por caminhos tradicionais no grafo expandido:  os arcos artificiais de um caminho no grafo expandido representam os arcos reversos do correspondente pseudocaminho no grafo original.  Assim, por exemplo, em vez de um pseudocaminho aumentador  0-2-3=1-4-5  no grafo original, teremos o caminho aumentador  0-2-3=1-4-5  no grafo expandido.)

Suponha que o grafo original tem um certo fluxo (representado pelos campos flow dos seus arcos originais e artificiais). Então a capacidade residual de um arco, seja ele original ou artificial, é a diferença

c − flow .

Como o fluxo é positivo nos arcos originais, a capacidade residual dos arcos artificiais é positiva. Se o fluxo respeita as capacidades dos arcos originais (ou seja, se flow ≤ c), a capacidade residual dos arcos originais também é positiva.

A capacidade residual de um caminho é a menor das capacidades residuais de seus arcos.  Um caminho de st no grafo expandido é aumentador se tiver capacidade residual estritamente positiva. Essa definição corresponde, exatamente, ao conceito de pseudocaminho aumentador no grafo capacitado original.

Sedgewick-part5-java/flow-fig-22-16-e.png

Exemplo B.  Considere o grafo capacitado abaixo, com vértice inicial 0 e vértice final 5.  A segunda linha da tabela especifica as capacidades e a terceira dá um fluxo.

0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 
  2   3   3   1   1   1   2   3  
  2   1   2   0   0   1   2   1    

A tabela seguinte mostra os arcos do grafo expandido e suas capacidades residuais.  Os arcos artificiais estão pintados de vermelho.

0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 1-0 2-0 3-1 4-1 3-2 4-2 5-3 5-4
  0   2   1   1   1   0   0   2   2   1   2   0   0   1   2   1

O caminho  0-2-3=1-4-5,  por exemplo, tem capacidade residual 1.

Camada externa da implementação do algoritmo

A função GRAPHmaxFlow() abaixo implementa o algoritmo de Ford-Fulkerson.  Ela calcula um fluxo máximo num grafo capacitado G com vértice inicial s e vértice final t.  O grafo G não tem arcos artificiais, mas os nós de suas listas de adjacência são expandidos (estando os campos flow, type e twin em branco).   A função GRAPHmaxFlow() tem três fases:

/* Esta função devolve a intensidade de um fluxo máximo
   no grafo capacitado G
   com vértice inicial s e vértice final t.
   O fluxo é armazenado nos campos flow 
   dos nós das listas de adjacência.
   O código supõe que G tem no máximo 
   1000 vértices.
   (Código inspirado na segunda parte do programa 22.3
   de Sedgewick.) */
int GRAPHmaxFlow( Graph G, vertex s, vertex t) 
{ 
   vertex pa[1000]; // parent vertex
   link parc[1000]; // parent arc
   expandGraph( G);
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         a->flow = 0;

   int intensity = 0;
   while (true) {
      int delta = AugmPath( G, s, t, pa, parc);
      // delta = cap residual de caminho aumentador
      if (delta == 0) break;
      for (vertex w = t; w != s; w = pa[w]) { 
         link a = parc[w]; 
         a->flow += delta; 
         a->twin->flow -= delta; 
      }
      intensity += delta;
   }

   contractGraph( G);
   return intensity;
}
/* Acrescenta os arcos artificiais ao grafo G
   e preenche os campos type e twin de todos os nós
   das listas adj[]. 
   (Os novos nós ficam concentrados no início das listas adj[]. */
void expandGraph( Graph G) { 
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         a->type = +1;
   for (vertex v = 0; v < G->V; ++v) 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         if (a->type == +1) {
            link b = malloc( sizeof (struct node));
            b->w = v; 
            b->c = 0; 
            b->type = -1; 
            b->twin = a;
            a->twin = b;
            b->next = G->adj[a->w];     
            G->adj[a->w] = b;
         }
}
/* A função contractGraph() desfaz o efeito de expandGraph(),
   removendo todos os arcos artificiais do grafo.
   (A função supõe que os nós que representam os arcos artificiais 
   estão concentrados
   no início das listas adj[].) */
void contractGraph( Graph G) {
   for (vertex v = 0; v < G->V; ++v) {
      link a = G->adj[v];
      while (a != NULL && a->type == -1) {
         link b = a;
         G->adj[v] = a = a->next;
         free( b);
      }
   }
}

[Juan Gutiérrez Alva apontou um erro na minha versão anterior da função GRAPHmaxFlow().]  Parte substancial do código de GRAPHmaxFlow() está escondida na função AugmPath(), que tem a missão de encontrar um caminho aumentador (= augmenting path) no grafo expandido e devolver a capacidade residual desse caminho. Se não existe caminho aumentador, a função devolve 0. Senão, o caminho é armazenado nos vetores pa[] e parc[] (os nomes dos vetores são abreviaturas de parent e parent arc respectivamente) da seguinte maneira: para cada vértice w do caminho,

Observe como o bloco de linhas

      for (vertex w = t; w != s; w = pa[w]) { 
         link a = parc[w]; 
         a->flow += delta; 
         a->twin->flow -= delta; 
      }

de GRAPHmaxFlow() trata corretamente de enviar delta unidade de fluxo ao longo do arco representado por  a,  quer o arco seja original quer artificial.

Quanto à função AugmPath(), duas diferentes implementações são discutidas a seguir nos capítulos Caminhos aumentadores mínimos e Caminhos aumentadores de capacidade máxima.

Exemplo C.  Considere novamente o grafo capacitado do exemplo A com vértice inicial 0, vértice final 5, e as capacidades indicadas a seguir.

0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 
  2   3   3   1   1   1   2   3  

Depois de construir o grafo expandido, a função GRAPHmaxFlow() executa quatro iterações. As sucessivas invocações de AugmPath() produzem a seguinte sequência de caminhos aumentadores (os arcos artificiais estão indicados em vermelho). 

0-1-3-5    
0-2-4-5    
0-2-3=1-4-5
Sedgewick-part5-java/flow-fig-22-6-b.png

(A capacidade residual, delta, do primeiro caminho aumentador é 2. Cada um dos demais tem capacidade residual 1.) Essa sequência de aumentos produz o fluxo máximo indicado a seguir.

0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 
  2   2   1   1   1   1   2   2    

A intensidade do fluxo é 4.

Exercícios 3

  1. Mostre que o incremento de fluxo em uma iteração genérica do while (true) {...} na função GRAPHmaxFlow() é calculado corretamente.
  2. Vetor auxiliar supérfluo.  O vetor pa[] no código de GRAPHmaxFlow() é supérfluo pois pa[x] é sempre igual a parc[x]->twin->w. Reescreva GRAPHmaxFlow() sem o vetor pa[].
  3. Alocação dinâmica.  Reescreva a função GRAPHmaxFlow() substituindo as alocações estáticas de pa[] e parc[] por alocações dinâmicas (e correspondentes desalocações).
  4. Rastreamento.  Acrescente código à função GRAPHmaxFlow() (ou talvez à função AugmPath()) para que ela imprima cada um dos caminhos aumentadores calculados por AugmPath().
  5. Corte mínimo.  Acrescente código à função GRAPHmaxFlow() para que ela calcule não só um fluxo máximo mas também um corte de capacidade mínima.  (A função e AugmPath() deverá ganhar um novo parâmetro e o código da função deve ser ligeiramente aumentado.)
  6. [Sedgewick 22.13]  Escreva uma função checkFlowDataStruct() que verifique a consistência da estrutura de dados no início de uma iteração qualquer da função GRAPHmaxFlow().  A função deve verificar se todos os campos dos nós das listas adj estão corretos e consistentes entre si.