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

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

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

\begin{document}
\title{Problema do fluxo máximo\\
       Método dos caminhos de aumento\\
       Fluxos bloqueadores de aumento}
\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 dos
fluxos bloqueadores de aumento}, 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.

@*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}. Visando à realização de
testes experimentais, o parâmetro adicional \texttt{-p} pode ser
informado, caso se deseje que os fluxos bloqueadores sejam obtidos em
redes acíclicas produzidas por busca em profundidade.

@*2Compilação e execução.

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

@*2Referências.
\noindent Sobre a plataforma \sgb:\\
\path"http://www-cs-faculty.stanford.edu/~knuth/sgb.html"\\
Sobre a linguagem de \emph{litterate programming} \cweb-\LaTeX:\\
\path"http://www-cs-faculty.stanford.edu/~knuth/cweb.html"\\
Sítio do projeto: \\
\path"http://www.ime.usp.br/~coelho/oticomb/"\\
%\path"http://www.linux.ime.usp.br/~julianab/oticomb/"\\
%\path"http://www.linux.ime.usp.br/~mhashimo/oticomb/"\\


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@*1 Algoritmo dos fluxos bloqueadores de aumento.

O método dos caminhos de aumento recebe um grafo, representando uma
rede capacitada, dois vértices~|s| e~|t| e devolve um |st|-fluxo de
intensidade máxima e um |st|-separador de capacidade mínima nessa
rede.  Os vértices~|s| e~|t| são, respectivamente, a \emph{fonte} e o
\emph{sorvedouro}. O |st|-separador mínimo é um certificado para a
maximalidade do fluxo encontrado. O método começa com um
|st|-fluxo~|x| e busca, em cada iteração, aumentar sua intensidade
através de um caminho de aumento.  Quando a rede residual com relação
a~|x| não contém caminhos de aumento, o |st|-fluxo~|x| é máximo e o
método pára.

Dizemos que um |st|-fluxo~|x| em uma rede é \textbf{bloqueador} 
se cada caminho de~|s| a~|t| na rede possui um arco saturado, 
isto é, cuja capacidade residual é nula com relação ao fluxo~|x|. 
Podemos dizer também que um fluxo bloqueador é 
um \textbf{fluxo maximal} em uma rede.

O algoritmo dos fluxos bloqueadores de aumento mantém um
|st|-fluxo~|x|, re\-pre\-sen\-ta\-do pelo campo |flx(a)| de cada
arco~|a|, e procura aumentar sua intensidade a cada iteração através
de fluxos bloqueadores na \textbf{rede residual de caminhos mínimos}.
A rede residual de caminhos mínimos é uma subrede acíclica da rede
residual que contém apenas os arcos que estão em algum ca\-mi\-nho
mínimo entre a fonte e o sorvedouro nessa rede.

Note que, pelo teorema da decomposição de fluxos, um fluxo bloqueador
em uma rede acíclica pode ser decomposto em um conjunto de
fluxos-caminhos.  Assim, aumentar a intensidade de um fluxo~|x|
através de um fluxo bloqueador em uma subrede acíclica da rede
residual, equivale a aumentar a intensidade de~|x| sucessivamente
através de uma seqüência de caminhos de aumento.  Portanto, o
algoritmo dos fluxos bloqueadores de aumento é uma variação do método
dos caminhos de aumento.

@ Antes da primeira iteração, um |st|-fluxo inicial é definido na rede
e os arcos irmãos são gerados.  Feito isso, o processo iterativo de
busca por fluxos bloqueadores e aumento da intensidade do fluxo pode
ser iniciado. Se o parâmetro |largura| estiver ativo, então a subrede
acíclica da rede residual a ser considerada é a rede residual de
caminhos mínimos, conforme descrição original do algoritmo, obtida a
partir de uma busca em largura.  Caso contrário, a rede acíclica é
construída a partir de uma busca em profundidade.  Apesar de não
termos estabelecido limitantes para o consumo de tempo do algoritmo
baseado nessa alteração, estamos interessados em analisá-lo
experimentalmente.

A condição (|t->dist == -1|) indica que não existem mais caminhos de
aumento na rede residual e que, portanto, o algoritmo pode parar. A
validade de tal condição de parada está justificada na descrição dos
procedimentos para obtenção da rede acíclica.  Devido ao interesse na
complexidade experimental do algoritmo, imprime-se o número total de
iterações após a execução.

@<Algoritmo dos fluxos bloqueadores de aumento@> =
void fluxos_bloqueadores_aumento(Graph *g, Vertex *s, Vertex *t, boolean largura){
  @<Variáveis da função |fluxos_bloqueadores_aumento|@>@;
  @<Define associação dos arcos aos vetores de fluxos@>@;
  @<Obtém fluxo inicial@>@;
  @<Constrói arcos irmãos@>@;
  iteracoes = 0;

  do{
    if (largura) {
      @<Obtém rede residual de caminhos mínimos@>@;
    }
    else {
      @<Obtém rede acíclica com busca em profundidade@>@;
    }
    if (t->dist != -1) {
      @<Encontra fluxo bloqueador na rede acíclica@>@;
      @<Aumenta fluxo através do fluxo bloqueador@>@;
      iteracoes++;
    }
  }while(t->dist != -1);


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


@ |flx| e |flx_bloq| são vetores cujas posições representam fluxo
  corrente e fluxo bloqueador em cada arco.  A utilização de tais
  vetores é necessária pois o \sgb{} disponibiliza apenas 2 campos
  utilitários para cada arco e estamos utilizando mais campos.  A
  associação de cada arco a uma posição desses vetores será feita
  através do campo |a->pos|.

@<Define associação dos arcos aos vetores de fluxos@> =
  indice = 0;
  for (i=g->vertices; i<g->vertices+g->n; i++) {
   for (a=i->arcs; a; a=a->next) {
      a->pos = indice++;
   }
  }


@ 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){
      flx(a) = 0;
    }
  }


@ Os arcos irmãos são construídos exatamente segundo 
  sua definição. Note que o arco irmão gerado é inicialmente
  apontado por |j->arcs|.

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



@ Nesta implementação, os arcos irmãos dos arcos da rede original 
são re\-conhe\-cidos por terem fluxo negativo. 

@<Função |arco_original|@> =
 int arco_original(Arc *a) {
   return (flx(a) >= 0);
 }


@*2 Obtenção da rede acíclica.

Visitando cada vértice apenas uma vez, através de uma busca na rede
re\-si\-dual, construímos uma árvore de busca.  Tal árvore é a subrede
acíclica a ser considerada pelo algoritmo na iteração.

Durante a busca, o campo~|i->dist| de cada vértice~|i| 
da rede é definido com a distância entre~|i| e o vértice fonte~|s|
na árvore de busca. Assim, ao final do processamento, 
a subrede acíclica será caracterizada pela presença de 
arcos~|ij| tais que |j->dist = i->dist + 1|.

Antes do início da busca, a distância de cada vértice
a~|s| é definida como~-1. Sendo assim, se ao 
final do processamento |t->dist == -1|, então o vértice
sorvedouro~|t| não é acessível a partir do vértice
fonte~|s| na rede residual e, portanto, não existem
caminhos de aumento. Isso explica a condição de parada
do~|while| na função~|fluxos_bloqueadores_aumento|.

Note que a busca deve ser feita na rede residual e, portanto,
apenas arcos com capacidade residual positiva são
considerados. 

@ Se uma busca em largura for utilizada para o procedimento, a subrede
acíclica será uma rede de caminhos mínimos.

@<Obtém rede residual de caminhos mínimos@> =
    for (i=g->vertices; i<g->vertices+g->n; i++) {
        i->dist = -1;
    }

    s->dist = 0;    
    inicializa_fila(g);
    insere_fila(s);

    while (!fila_vazia()) {
      i = remove_fila();

      for (a=i->arcs; a; a=a->next) {
	if (get_cap_residual(a) > 0) {
	  j = a->tip;
	  if (j->dist == -1) {
	    j->dist = i->dist + 1;
	    insere_fila(j);
	  }
	}
      }
    }


@ Uma busca em profundidade também determina uma subrede acíclica.

@<Obtém rede acíclica com busca em profundidade@> = 
  for (i=g->vertices; i<g->vertices+g->n; i++) {
    i->dist = -1;
  }
  
  s->dist = 0;
  busca_em_profundidade(s);


@ A busca em profundidade é feita através de uma
  função recursiva.

@<Função |busca_em_profundidade|@> = 
void busca_em_profundidade(Vertex *i) {
  Vertex *j;
  Arc    *a;

  for (a=i->arcs; a; a=a->next) {
    if (get_cap_residual(a) > 0) {
      j = a->tip;
      if (j->dist == -1) {
	j->dist = i->dist+1;
	busca_em_profundidade(j);
      }
    }
  }
  return;
}


@ A capacidade residual de um arco da rede original correponde
à diferença entre sua capacidade e seu fluxo corrente. A capacidade
residual de um arco irmão de um arco original corresponde ao fluxo 
corrente em seu arco irmão.

@<Função |get_capacidade_residual|@> =
 long get_cap_residual(Arc *a) {
    if (!arco_original(a)) {
        return flx(a->irmao);
    }
    else {
        return (a->cap - flx(a));
    }
 }


@*2 Obtenção do fluxo bloqueador.

Para a obtenção do fluxo bloqueador, tentamos enviar uma quantidade
má\-xi\-ma de fluxo a partir da fonte~|s| ao sorvedouro~|t|. 
A idéia é enviar o fluxo recursivamente através dos
vizinhos da fonte e de forma que todos os caminhos de~|s| a~|t|
possuam um arco saturado ao final do processamento.

O fluxo bloqueador será representado pelo campo |flx_bloq(a)|
de cada arco~|a| da rede acíclica.

@<Encontra fluxo bloqueador na rede acíclica@> =
    @<Gera limitante fluxo bloqueador@>@;
    @<Inicializa fluxo bloqueador@>@;
    envia_fluxo_bloqueador(s,t,max_fluxo);	


@ Um limitante para o fluxo bloqueador é dado pela soma das
 capacidades residuais dos arcos que saem da fonte
 na rede acíclica.

@<Gera limitante fluxo bloqueador@> = 
    max_fluxo = 0;
    for (a=s->arcs; a; a=a->next) {
      if (a->tip->dist == s->dist + 1)
        max_fluxo += get_cap_residual(a);
    }


@ Antes de encontrar o fluxo bloqueador da iteração,
  ``limpamos'' o fluxo bloqueador da iteração passada.

@<Inicializa fluxo bloqueador@> =
    for (i=g->vertices; i<g->vertices+g->n; i++) {
      for (a=i->arcs; a; a=a->next) {
	flx_bloq(a) = 0;
      }
    }


@ Na função |envia_fluxo_bloqueador|, o parâmetro |fluxo| indica a
quantidade de fluxo que o vértice~|i| recebeu da fonte. Busca-se,
então, repassar esse fluxo aos vizinhos de~|i| na rede
acíclica. Primeiramente, tenta-se enviar ao primeiro vizinho de~|i|,
digamos |j|, o mínimo entre o fluxo recebido e a capacidade residual
do arco que os conecta. O vizinho~|j| tenta enviar o fluxo recebido
recursivamente e devolve a quantidade de fluxo que efetivamente
chegou até o sorvedouro.  A variável |flx_sobra| é atualizada, então,
com a quantidade de fluxo que o vértice~|i| ainda pode tentar
distribuir.  O processo é repetido para os demais vizinhos de~|i|,
sempre tentando repassar o máximo da quantidade de fluxo que ainda
resta, o que equivale ao mínimo entre |flx_sobra| e a capacidade
residual do arco que liga~|i| ao vizinho. Note que a função
devolve a quantidade de fluxo que efetivamente chegou à fonte
a partir do vértice~|i|.


@<Função |envia_fluxo_bloqueador|@> =
long  envia_fluxo_bloqueador (Vertex *i, Vertex *t, long fluxo) {
    @<Variáveis da função |envia_fluxo_bloqueador|@>@;

    flx_sobra = fluxo;  

    if (i == t) {
        return fluxo;         
    }

    for (a=i->arcs; a && flx_sobra > 0; a=a->next) {
        if (get_cap_residual(a) > 0) {
            j = a->tip;
            if (j->dist == i->dist + 1) {
                @<Busca repassar fluxo ao vizinho@>@;
	    }
	}
    }
    return (fluxo - flx_sobra);
}


@ Um vértice só pode repassar o fluxo a um vizinho se a capacidade
  re\-si\-dual do arco que os conecta ainda não foi atingida pelo
  fluxo bloqueador em construção. 

@<Busca repassar fluxo ao vizinho@> = 
 if (flx_bloq(a) < get_cap_residual(a)) {
  flx_caminho = envia_fluxo_bloqueador(j,t,min(flx_sobra,(get_cap_residual(a) - flx_bloq(a))));
  flx_bloq(a) += flx_caminho;
  flx_sobra   -= flx_caminho;   
 }

@ É preciso definir a função auxiliar |min|, utilizada acima, que 
  devolve o mínimo entre os inteiros |a| e |b|.
@<Função |min|@>=
long min(long a, long b) {
    if (a > b) {
        return b;
    }
    return a;
}


@ Resta também definir as variáveis da função |envia_fluxo_bloqueador|.

@<Variáveis da função |envia_fluxo_bloqueador|@> = 
    Vertex *j;
    Arc *a;
    long flx_sobra;  
    long flx_caminho;        



@*2 Aumento do fluxo através do fluxo bloqueador.

Uma vez que o fluxo bloqueador foi definido, podemos aumentar a
intensidade do fluxo corrente na rede da seguinte forma: somamos ao
fluxo de um arco original o fluxo bloqueador que o mesmo transporta e
subtraímos o fluxo bloqueador transportado por seu irmão.

@<Aumenta fluxo através do fluxo bloqueador@> = 
  for (i=g->vertices; i<g->vertices+g->n; i++) {
    for (a=i->arcs; a; a=a->next) {
      if (!arco_original(a)) {
	flx(a->irmao) -= flx_bloq(a);
      }
      else {
	flx(a) += flx_bloq(a);
      }
    }
  }


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

@<Variáveis da função |fluxos_bloqueadores_aumento|@> =
  long iteracoes, indice, max_fluxo;
  Vertex *i, *j;
  Arc *a;

@*1Fila de vértices.

A fila utilizada na busca em largura é implementada como uma fila
circular através da utilização do próprio vetor de vértices de um
grafo do SGB.

O campo |i->vertice| de determinado vértice~|i| do grafo~|g|,
utilizado para a cons\-tru\-ção da fila, representa o vértice que ocupa a
mesma posição de~|i| no vetor |g->vertices|.  O primeiro vértice na
fila é dado por |ini->vertices| e o último, por |fim->vertices|. A
condição (|ini == fim|) indica que a fila está vazia.  A implementação
supõe que no máximo |g->n| vértices ocuparão a fila ao mesmo tempo, o
que sempre ocorre durante uma busca na rede residual.


@<Fila circular de vértices@> =
Vertex *ini, *fim, *zero;
Vertex *max;

void inicializa_fila (Graph *g) {
  ini   = g->vertices;
  fim   = g->vertices;
  zero  = g->vertices;
  max   = g->vertices + g->n;
  return;
}

void insere_fila (Vertex *i) {  
    fim->vertice = i;
    fim++;
    if (fim > max) {
      fim = zero;
    }
    if (fim == ini) {
      fprintf(stderr,"ERRO: Fila excedeu sua capacidade.\n");
      exit(-1);
    }
}


boolean fila_vazia() {
  if (ini == fim) 
    return TRUE;
  return FALSE;
}

Vertex *remove_fila () {
  Vertex *i;
  if (!fila_vazia()) {
    i = ini->vertice;
    ini++;
    if (ini > max) {
      ini = zero;
    }
    return i;
  }
  return NULL;
}


Vertex *primeiro_fila() {
  if (!fila_vazia()) {
    return ini->vertice;
  }
  return NULL;
}



@*1Função principal.

O programa consiste basicamente 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;
  boolean largura;
  @<Variáveis secundárias da função principal@>@;
  @<Verifica consistência dos parâmetros@>@;
  @<Aloca vetores |flx| e |flx_bloq|@>@;
  fluxos_bloqueadores_aumento(g, fonte, sorvedouro,largura);
  @<Imprime fluxo máximo@>@;
  @<Imprime separador de capacidade mínima@>@;
  return(0);
}

@ Entretanto, antes da aplicação do algoritmo, é preciso alocar
os vetores~|flx| e~|flx_bloq| que armazenam respectivemente
o fluxo corrente em cada arco e o fluxo bloqueador da iteração.
Os vetores são alocados com tamanho igual a duas vezes o número de 
arcos do grafo, pois armazenarão dados sobre arcos originais e
sobre seus arcos irmãos.

@<Aloca vetores |flx| e |flx_bloq|@> = 
  flx = (long *) malloc (2*g->m * sizeof(long));
  flx_bloq = (long *) malloc (2*g->m *sizeof (long));

  if (!flx || !flx_bloq) {
    fprintf(stderr,"ERRO: Problemas com alocação de memória.\n");
    exit(-1);
  }

@*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~|len| de cada arco corresponda à sua capacidade. Também é
necessário que os nomes de vértices referenciem vértices que de fato
existam no grafo e que a rede contenha somente capacidades
não-negativas. Por fim, é preciso verificar se a opção referente ao
tipo de busca foi informada corretamente. 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 && argc != 6){
    fprintf(stderr, "Uso: %s <in> <out> \"source\" \"sink\" [-p]\n", argv[0]);

    exit(-1);
  }
  @<Verifica validade dos arquivos@>@;
  @<Verifica existência dos vértices@>@;
  @<Verifica sinal das capacidades@>@;
  @<Verifica tipo de busca@>@;

@ 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, "ERRO: Problemas com arquivo de entrada.\n");
    exit(-2);
  }

  if((saida = fopen(argv[2], "w")) == NULL){
    fprintf(stderr, "ERRO: Arquivo de saída inválido.\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]) == 0) fonte = i;
    if(strcmp(i->name, argv[4]) == 0) sorvedouro = i;
  }
  if(fonte == NULL || sorvedouro == NULL){
    fprintf(stderr, "ERRO: 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, "ERRO: Capacidade negativa encontrada.\n");
        exit(-5);
      }
    }
  }

@ A opção \texttt{-p} indica que o fluxo bloqueador deve ser obtido
  em uma rede acíclica produzida por uma busca em profundidade.
  Por padrão, a rede acíclica é construída através de uma busca
  em largura.


@<Verifica tipo de busca@> =
  largura = TRUE;
  if (argc == 6) {
    if(strcmp("-p", argv[5]) == 0) largura = FALSE;
    else {
      fprintf(stderr,"ERRO: Opção inválida: %s.\n",argv[5]);
      exit(-6);
    }
  }


@*2 Impressão do fluxo de intensidade máxima.

Após a execução do algoritmo, imprime-se o fluxo máximo encontrado e
sua 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(arco_original(a)){
        fprintf(saida, "Fluxo de \"%s\" a \"%s\": %ld\n", i->name, a->tip->name, flx(a));
        if(i == sorvedouro) max -= flx(a);
        if(a->tip == sorvedouro) max += flx(a);
      }
    }
  }
  fprintf(saida, "Intensidade: %d\n", max);
  fprintf(stdout,"Intensidade do fluxo máximo: %d\n", max);


@*2Impressão do separador de capacidade mínima.  O separador de
capacidade mínima contém os vértices da rede original a\-ces\-sí\-veis
a partir da fonte através de caminhos alternantes, ou seja, os
vértices examinados durante a última busca por um fluxo bloqueador na
rede residual.  Tais vértices são identificados por possuírem o campo
|dist| definido com um valor não-negativo.

@<Imprime separador de capacidade mínima@> =
  fprintf(saida, "\nSeparador:\n");
  for(min = 0, i = g->vertices; i < g->vertices + g->n; i++){
    if(i->dist >= 0){
      fprintf(saida, "\"%s\"\n", i->name);
      for(a = i->arcs; a; a = a->next){
        if(flx(a) >= 0 && a->tip->dist == -1) min += a->cap;
      }
    }
  }
  fprintf(saida, "Capacidade: %d\n", min);
  fprintf(stdout,"Capacidade do separador minimo: %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@>@;
@<Variaveis globais@>@;
@<Fila circular de vértices@>@;
@<Função |min|@>@;
@<Função |arco_original|@>@;
@<Função |get_capacidade_residual|@>@;
@<Função |envia_fluxo_bloqueador|@>@;
@<Função |busca_em_profundidade|@>@; 
@<Algoritmo dos fluxos bloqueadores de aumento@>@;
@<Função principal@>@;


@ Os vetores |flx| e |flx_bloq| são variáveis globais e
  precisam ser declarados. 

@<Variaveis globais@> = 
 long *flx, *flx_bloq;

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

@<Bibliotecas necessárias@> =
#include <stdio.h>
#include <stdio.h>
#include <stdlib.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 vertice   v.V

@d cap          len
@d pos          a.I
@d irmao        b.A
@d inicio       irmao->tip
@d flx_bloq(a)  flx_bloq[a->pos]
@d flx(a)       flx[a->pos]


@
\end{document}