\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 do pré-fluxo\\
       Excess 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 excess
scaling}, uma versão do \textbf{método do pré-fluxo} para resolver o
\textbf{problema do fluxo máximo}. A plataforma \sgb{} é necessária para a
execução do programa.

@*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 excessscaling.tex} para gerar o arquivo \LaTeX{} de documentação.\\
\texttt{make excessscaling.dvi} para gerar o arquivo DVI de visualização.\\
\texttt{make excessscaling.pdf} para gerar o arquivo PDF de visualização.\\
\texttt{make excessscaling.ps} para gerar o arquivo PostScript de visualização.\\
\texttt{make excessscaling.c} para gerar o código-fonte C do programa.\\
\texttt{make excessscaling} para gerar o executável do programa.\\
\texttt{excessscaling} 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 excess scaling.
O método do pré-fluxo começa a partir de um pré-fluxo inicial e em cada
iteração escolhe um vértice ativo para sofrer uma operação
push ou uma operação relabel. O algoritmo excess scaling mantém um
limitante inferior $\Delta$ e seleciona vértices ativos cujo excesso é maior
que o valor $\Delta / 2$.  O método pára quando a lista de vértices ativos está
vazia 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 para
obtermos a rede residual de maneira implícita.

@<Algoritmo excess scaling@> =
void excessscaling(Graph *g, Vertex *fonte, Vertex *sorvedouro){
  @<Variáveis da função |excessscaling|@>@;
  @<Obtém limitante inicial@>@;
  @<Executa pré-processamento@>@;
  @<Constrói arcos irmãos@>@;
  iteracoes = 0;
  inicializalista(g);
  while(Delta >= 1){
    @<Insere vértices ativos@>@;
    while(!listavazia()){
      i = retiradalista();
      @<Executa push ou relabel@>@;
      iteracoes++;
    }
    Delta = Delta / 2;
  }
  finalizalista();
  fprintf(stdout, "número de iterações: %d\n", iteracoes);
  return;
}

@ O valor inicial de $\Delta$ é a maior capacidade vezes o número de arcos.

@<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 = Delta * g->m;
  Delta = (int) pow(2.0, floor(log((double) Delta) / log(2.0)));

@ O pré-processamento consiste em atribuir o pré-fluxo inicial e os
rótulos iniciais.  O pré-fluxo inicial $x$ é tal que $x_a = u_a$ para
todo arco $a$ que sai do vértice fonte e $x_a = 0$ para todo arco $a$
restante do grafo. A função distância inicial $d$ é tal que $d(fonte)
= n$ e $d(i) = 0$ para todo vértice $i$ restante.

@<Executa pré-processamento@> =
  for(i = g->vertices; i < g->vertices + g->n; i++){
    i->dist = 0;
    i->exc = 0;
    i->atual = i->arcs;
  }
  for(i = g->vertices; i < g->vertices + g->n; i++){
    for(a = i->arcs; a; a = a->next){
      if(i == fonte && a->tip != fonte) a->flx = a->cap;
      else a->flx = 0;
      i->exc -= a->flx;
      a->tip->exc += a->flx;
    }
  }
  fonte->dist = g->n;

@ 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;
      }
    }
  }

@ Os vértices ativos com excesso suficientemente grande são adicionados à
lista. Deve-se adicionar uma condição extra para não adicionar o sorvedouro.

@<Insere vértices ativos@> =
  for(i = g->vertices; i < g->vertices + g->n; i++){
    if(i != sorvedouro && i->exc > Delta / 2) inserenalista(i);
  }

@ Se o vértice ativo $i$ examinado é origem de algum arco admissível
$a$, executa-se um push no arco $a$. Senão, executa-se um
relabel no vértice $i$.

@<Executa push ou relabel@> =
  for(a = i->atual; a; a = a->next){
    if(a->flx >= 0) temp = a->cap - a->flx;
    else temp = a->irmao->flx;
    if(temp > 0 && i->dist == a->tip->dist + 1) break;
  }
  if(a == NULL){
    @<Executa um relabel@>@;
    i->atual = i->arcs;
  }
  else{
    @<Executa um push@>@;
    i->atual = a;
  }

@*2Execução de um relabel.
Para executar um relabel é necessário visitar todos os vizinhos
do vértice examinado $i$ na rede residual. 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 positiva.

@<Executa um relabel@> =
  for(min = -1, a = i->arcs; a; a = a->next){
    if(a->flx >= 0) temp = a->cap - a->flx;
    else temp = a->irmao->flx;
    if(temp > 0 && a->tip != i){
      if(min == -1 || min > a->tip->dist) min = a->tip->dist;
    }
  }
  i->dist = min + 1;
  inserenalista(i);

@*2Execução de um push.
Executar um push resume-se a atualizar valores.

@<Executa um push@> =
  if(i->exc < temp) temp = i->exc;
  if(a->tip != sorvedouro && Delta - a->tip->exc < temp) temp = Delta - a->tip->exc;
  if(a->flx >= 0) a->flx += temp;
  else a->irmao->flx -= temp;
  i->exc -= temp;
  a->tip->exc += temp;
  if(i->exc > Delta / 2) inserenalista(i);
  if(a->tip != sorvedouro && a->tip->exc > Delta / 2){
    if(a->tip->exc - temp <= Delta / 2) inserenalista(a->tip);
  }

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

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

@*1Lista de vértices.
A estrutura de dados aqui utilizada para armazenar os vértices ativos
foi baseada no livro \emph{Network Flows} de R.~K.~Ahuja,
T.~L.~Magnanti e J.~B.~Orlin.

@<Lista de vértices@> =
  Vertex **lista;
  int level, size;

  void inicializalista(Graph *g){
    int indice;
    lista = (Vertex **) malloc((2 * g->n) * sizeof(Vertex *));
    for(indice = 0; indice < 2 * g->n; indice++)
      lista[indice] = NULL;
    level = 0;
    size = 0;
    return;
  }

  void finalizalista(){
    free(lista);
    return;
  }

  boolean listavazia(){
    if(size == 0)
      return(TRUE);
    return(FALSE);
  }

  Vertex *retiradalista(){
    Vertex *i;
    while(lista[level] == NULL) level++;
    i = lista[level];
    lista[level] = i->prox;
    size--;
    return(i);
  }

  void inserenalista(Vertex *i){
    i->prox = lista[i->dist];
    lista[i->dist] = i;
    if(i->dist < level) level = i->dist;
    size++;
    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@>@;
  excessscaling(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", a->inicio->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 é definido por um valor $k$ tal que $d(i)
\not = k$ para todo vértice $i$. Os vértices do separador possuem distância
maior que $k$.

@<Imprime separador de capacidade mínima@> =
  for(k = 1; k < g->n; k++){
    for(i = g->vertices; i < g->vertices + g->n; i++){
      if(i->dist == k) break;
    }
    if(i == g->vertices + g->n) break;
  }

  fprintf(saida, "separador:\n");
  for(min = 0, i = g->vertices; i < g->vertices + g->n; i++){
    if(i->dist > k){
      fprintf(saida, "\"%s\"\n", i->name);
      for(a = i->arcs; a; a = a->next){
        if(a->flx >= 0 && a->tip->dist < k) 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, k;
  FILE *saida;

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

@c
@<Bibliotecas necessárias@>@;
@<Lista de vértices@>@;
@<Algoritmo excess 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 dist    u.I
@d exc     v.I
@d prox    w.V
@d atual   x.A

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

@
\end{document}