\documentclass[language=brazil, structure=flat]{cweb}

\usepackage[brazil]{babel}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{indentfirst}

\newcommand{\cweb}{\texttt{CWEB}}
\newcommand{\C}{\texttt{C}}
\newcommand{\sgb}{\texttt{SGB}}

\begin{document}
\title{Fluxos máximos\\
       Método dos caminhos de aumento\\
       Capacity scaling}
\author
  {
    \begin{tabular}{cp{25pt}c}
    Juliana Barby Simão & & Marcelo Hashimoto\\
    \small{\textsc{Apoio financeiro da FAPESP}} & & \small{\textsc{Apoio financeiro da FAPESP}}\\
    \small{\textsc{Processo 04/00580-8}} & & \small{\textsc{Processo 04/00581-4}}
    \end{tabular}\\
    \\
    \textsc{Orientador:} José Coelho de Pina
  }
\date{}
\maketitle
\tableofcontents
\newpage

@*1Introdução.
Esta é uma implementação em \cweb-\LaTeX{} do \textbf{algoritmo
capacity scaling}, uma versão do \textbf{método dos caminhos de
aumento} para resolver o \textbf{problema do fluxo máximo}. A
plataforma \sgb{} é necessária para execução.

@*2Descrição.
Este programa recebe o nome de um arquivo que contém um grafo no formato \sgb,
o nome de um arquivo de saída, o nome de um vértice fonte e o nome de um
vértice sorvedouro e imprime no arquivo de saída um fluxo de intensidade
máxima e um separador de capacidade mínima da rede representada pelo
grafo. Assume-se que as capacidades dos arcos estão representadas no campo
\emph{len}.

@*2Compilação e execução.
\noindent \texttt{make capacityscaling.tex} para gerar o arquivo \LaTeX{} de documentação.\\
\texttt{make capacityscaling.dvi} para gerar o arquivo DVI de visualização.\\
\texttt{make capacityscaling.pdf} para gerar o arquivo PDF de visualização.\\
\texttt{make capacityscaling.ps} para gerar o arquivo PostScript de visualização.\\
\texttt{make capacityscaling.c} para gerar o código-fonte C do programa.\\
\texttt{make capacityscaling} para gerar o executável do programa.\\
\texttt{capacityscaling} para executar o programa.

@*2Referências.
\noindent Sobre a plataforma \sgb:\\
\texttt{http://www-cs-faculty.stanford.edu/\~{}knuth/sgb.html}\\
Sobre a linguagem de \emph{litterate programming} \cweb-\LaTeX:\\
\texttt{http://www-cs-faculty.stanford.edu/\~{}knuth/cweb.html}\\

@*1Algoritmo capacity scaling.
O método dos caminhos de aumento começa a partir de um fluxo inicial e
em cada iteração encontra um caminho de aumento relativo ao fluxo
atual e aumenta a intensidade do fluxo através desse caminho. O método
pára quando não há mais caminhos de aumento. O algoritmo capacity
scaling mantém um limitante inferior $\Delta$ para a capacidade
residual dos caminhos de aumento desejados. Nesta implementação, após
uma busca por caminhos de aumento, todo vértice acessível a partir da
fonte através de caminhos alternantes passa a ter um arco predecessor
definido. Logo, a execução termina quando o sorvedouro não tem um arco
predecessor definido e $\Delta < 1$. Devido ao interesse na
complexidade experimental do algoritmo, imprime-se o número total de
iterações após a execução. Como a rede originalmente não contém arcos
irmãos, eles devem ser construídos antes.

@<Algoritmo capacity scaling@> =
void capacityscaling(Graph *g, Vertex *fonte, Vertex *sorvedouro){
  @<Variáveis da função |capacityscaling|@>@;
  @<Obtém limitante inicial@>@;
  @<Obtém fluxo inicial@>@;
  @<Constrói arcos irmãos@>@;
  iteracoes = 0;
  while(Delta >= 1){
    do{
      @<Encontra caminho de aumento@>@;
      @<Aumenta fluxo através do caminho de aumento@>@;
      iteracoes++;
    }while(sorvedouro->arcopred != NULL);
    Delta = Delta / 2;
  }

  fprintf(stdout, "número de iterações: %d\n", iteracoes - 1);
  return;
}

@ O valor inicial de $\Delta$ corresponde à maior capacidade.

@<Obtém limitante inicial@> =
  for(Delta = -1, i = g->vertices; i < g->vertices + g->n; i++){
    for(a = i->arcs; a; a = a->next){
      if(Delta < a->cap) Delta = a->cap;
    }
  }
  fprintf(stdout, "capacidade máxima: %d\n", Delta);
  Delta = (int) pow(2.0, floor(log((double) Delta) / log(2.0)));

@ O fluxo inicial $x$ é tal que $x_a = 0$ para todo arco $a$.

@<Obtém fluxo inicial@> =
  for(i = g->vertices; i < g->vertices + g->n; i++){
    for(a = i->arcs; a; a = a->next){
      a->flx = 0;
    }
  }

@ Os arcos irmãos são construídos exatamente segundo sua definição.
Nesta implementação, os arcos irmãos são reconhecidos por terem fluxo
negativo.

@<Constrói arcos irmãos@> =
  for(i = g->vertices; i < g->vertices + g->n; i++){
    for(a = i->arcs; a; a = a->next){
      if(a->flx >= 0){
        j = a->tip;
        gb_new_arc(j, i, a->cap);
        a->irmao = j->arcs;
        a->irmao->flx = -1;
        a->irmao->irmao = a;
      }
    }
  }

@*2Caminhos de aumento.
Os caminhos de aumento são obtidos através de uma busca em largura
simples a partir do vértice fonte, implementada através de uma fila
tradicional. Inicialmente a fila só tem um único elemento: o próprio
vértice fonte.

@<Encontra caminho de aumento@> =
  for(i = g->vertices; i < g->vertices + g->n; i++){
    i->arcopred = NULL;
    i->estado = NAOVISTO;
  }

  inicializafila();
  inserenafila(fonte);
  fonte->estado = VISITADO;

  while(!filavazia()){
    i = retiradafila();
    @<Examina vértice retirado da fila@>@;
  }

@ Ao examinar um vértice, visita-se seus vizinhos na rede residual
restrita e insere-os na fila.  A capacidade residual do caminho
alternante até o vértice é mantida no atributo \emph{res}. Ao invés de
manter uma estrutura de dados separada para a rede residual, mantemos
esta implícita. Para tanto, basta que a busca considere apenas os
arcos com capacidade residual maior ou igual a $\Delta$. Utiliza-se
uma variável temporária para armazenar a capacidade residual dos
arcos.

@<Examina vértice retirado da fila@> =
  for(a = i->arcs; a; a = a->next){
    j = a->tip;

    if(j->estado == NAOVISTO){
      if(a->flx >= 0) temp = a->cap - a->flx;
      else temp = a->irmao->flx;
      if(temp >= Delta){
        if(i != fonte && temp > i->res) j->res = i->res;
        else j->res = temp;
        inserenafila(j);
        j->estado = VISITADO;
        j->arcopred = a;
      }
    }
  }

@*2 Aumento do fluxo através do caminho.
Como cada vértice acessível a partir da fonte através de um caminho
alternante tem um arco predecessor definido, o aumento do fluxo é
simples: basta percorrer o caminho a partir do sorvedouro, valendo-se
dos arcos predecessores, modificando o fluxo em cada arco de acordo
com a rede na qual ele se encontra.

@<Aumenta fluxo através do caminho de aumento@> =
  a = sorvedouro->arcopred;
  while(a != NULL){
    if(a->flx >= 0) a->flx = a->flx + sorvedouro->res;
    else a->irmao->flx = a->irmao->flx - sorvedouro->res;
    if(a->inicio == fonte) a = NULL;
    else a = a->inicio->arcopred;
  }

@ Como toda a função foi definida, podemos declarar as variáveis.

@<Variáveis da função |capacityscaling|@> =
  int iteracoes, temp, Delta;
  Vertex *i, *j;
  Arc *a;

@*1Fila para busca em largura.

A implementação da fila utilizada na busca em largura é feita através
do uso de um apontador em cada vértice e dois apontadores auxiliares
extras.

@<Fila para busca em largura@> =
  Vertex *head, *tail;

  void inicializafila(){
    head = NULL;
    tail = NULL;
  }

  boolean filavazia(){
    if(head == NULL)
      return(TRUE);
    return(FALSE);
  }

  Vertex *retiradafila(){
    Vertex *i = head;
    head = head->prox;
    if(head == NULL)
      tail = NULL;
    return(i);
  }

  void inserenafila(Vertex *i){
    if(head == NULL){
      head = i;
      tail = i;
    }
    else{
      tail->prox = i;
      tail = i;
    }
    i->prox = NULL;
    return;
  }

@*1Função principal.
O programa consiste de três fases: inicialização, execução do
algoritmo e finalização. A inicialização consiste em verificar a
consistência dos parâmetros de entrada. A aplicação do algoritmo é
simplesmente a chamada da função que já definimos anteriormente. A
finalização consiste em imprimir no arquivo de saída o fluxo máximo
obtido e o separador de capacidade mínima.

@<Função principal@> =
int main(int argc, char *argv[]){
  Graph *g;
  Vertex *fonte, *sorvedouro;
  @<Variáveis secundárias da função principal@>@;
  @<Verifica consistência dos parâmetros@>@;
  capacityscaling(g, fonte, sorvedouro);
  @<Imprime fluxo máximo@>@;
  @<Imprime separador de capacidade mínima@>@;
  return(0);
}

@*2Consistência dos parâmetros.
Para que o programa seja executado corretamente, exige-se que o nome
de arquivo fornecido referencie um grafo válido no formato \sgb, onde
o campo \emph{len} dos arcos corresponde à capacidade. Também é
necessário que os nomes de vértices referenciem vértices que de fato
existem no grafo e que a rede contenha somente capacidades
não-negativas. Caso um número de parâmetros incorreto seja fornecido,
as instruções do programa são impressas, exibindo a sintaxe.

@<Verifica consistência dos parâmetros@> =
  if(argc != 5){
    fprintf(stderr, "%s <in> <out> \"source\" \"sink\"\n", argv[0]);
    exit(-1);
  }
  @<Verifica validade dos arquivos@>@;
  @<Verifica existência dos vértices@>@;
  @<Verifica sinal das capacidades@>@;

@ O programa utiliza as funções padrão para abrir o arquivo desejado.
Caso o arquivo não possa ser aberto, o programa é imediatamente
interrompido.

@<Verifica validade dos arquivos@> =
  if((g = restore_graph(argv[1])) == NULL){
    fprintf(stderr, "entrada inválida\n");
    exit(-2);
  }

  if((saida = fopen(argv[2], "w")) == NULL){
    fprintf(stderr, "saída inválida\n");
    exit(-3);
  }

@ Os vértices do grafo são examinados um por um até que os nomes
fornecidos sejam encontrados. No caso de nomes iguais, considera-se o
primeiro.

@<Verifica existência dos vértices@> =
  fonte = NULL;
  sorvedouro = NULL;
  for(i = g->vertices; i < g->vertices + g->n; i++){
    if(!strcmp(i->name, argv[3])) fonte = i;
    if(!strcmp(i->name, argv[4])) sorvedouro = i;
  }
  if(fonte == NULL || sorvedouro == NULL){
    fprintf(stderr, "vértices inválidos\n");
    exit(-4);
  }

@ Os arcos do grafo são examinados um por um. O programa é
interrompido imediatamente se um arco com capacidade negativa for
encontrado.

@<Verifica sinal das capacidades@> =
  for(i = g->vertices; i < g->vertices + g->n; i++){
    for(a = i->arcs; a; a = a->next){
      if(a->cap < 0){
        fprintf(stderr, "capacidades negativas\n");
        exit(-5);
      }
    }
  }

@*2Impressão do fluxo de intensidade máxima.
Após a execução do algoritmo, imprime-se o fluxo e a intensidade.

@<Imprime fluxo máximo@> =
  for(max = 0, i = g->vertices; i < g->vertices + g->n; i++){
    for(a = i->arcs; a; a = a->next){
      if(a->flx >= 0){
        fprintf(saida, "fluxo de \"%s\" a \"%s\": %ld\n", i->name, a->tip->name, a->flx);
        if(i == sorvedouro) max -= a->flx;
        if(a->tip == sorvedouro) max += a->flx;
      }
    }
  }
  fprintf(saida, "intensidade: %d\n", max);

@*2Impressão do separador de capacidade mínima.
O separador de capacidade mínima contém os vértices acessíveis a partir da
fonte através de caminhos alternantes, ou seja, os vértices examinados.

@<Imprime separador de capacidade mínima@> =
  fprintf(saida, "separador:\n");
  for(min = 0, i = g->vertices; i < g->vertices + g->n; i++){
    if(i->estado != NAOVISTO){
      fprintf(saida, "\"%s\"\n", i->name);
      for(a = i->arcs; a; a = a->next){
        if(a->flx >= 0 && a->tip->estado == NAOVISTO) min += a->cap;
      }
    }
  }
  fprintf(saida, "capacidade: %d\n", min);
  fclose(saida);

@ Podemos agora definir as variáveis secundárias da função principal.

@<Variáveis secundárias da função principal@> =
  Vertex *i;
  Arc *a;
  int min, max;
  FILE *saida;

@*1Estrutura geral.
Para concluir o programa basta definir a estrutura geral.

@c
@<Bibliotecas necessárias@>@;
@<Fila para busca em largura@>@;
@<Algoritmo capacity scaling@>@;
@<Função principal@>@;

@*2Bibliotecas.
Além das bibliotecas básicas, é preciso usar a plataforma \sgb.

@<Bibliotecas necessárias@> =
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gb_graph.h>
#include <gb_save.h>

@*2Macros.
Definimos aqui todas as macros utilizadas no programa.

@d boolean   int
@d FALSE     0
@d TRUE      1

@d NAOVISTO  0
@d VISITADO  1

@d arcopred  u.A
@d estado    w.I
@d res       x.I
@d prox      y.V

@d cap       len
@d flx       a.I
@d irmao     b.A
@d inicio    irmao->tip

@
\end{document}