\input cwebmac
% coelho MAR 2003
\documentclass[language=brazil,structure=flat]{cweb}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[T1]{fontenc}
%----------------------------

\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{-.125in}
\setlength{\evensidemargin}{-.125in}
\setlength{\textwidth}{6.75in}

% Macros do LaTeX
\newcommand{\cweb}{\texttt{CWEB}}
\newcommand{\sgb}{\texttt{SGB}}
\newcommand{\defi}[1]{\textit{#1}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\seq}[1]{\langle #1 \rangle}
\newcommand{\opcao}[1]{$\langle$#1$\rangle$}
\newcommand{\caminho}[1]{$\langle$#1$\rangle$}
\newcommand{\conjunto}[1]{\{\,#1\,\}}
\newcommand{\conj}[1]{\{#1\}}
\newcommand{\NP}{\textup{NP}}
\newcommand{\PP}{\textup{P}}

% \pch  problema do circuito hamiltoniano
\newcommand{\pch}{\textsc{PCH}}

\newcommand{\gbb}{\textsc{gb\_basic}}
\newcommand{\gbr}{\textsc{gb\_rand}}
\newcommand{\gbs}{\textsc{gb\_save}}

\begin{document}




\title{{\small Exemplo de uso do Stanford GraphBase com \texttt{CWEB}-\LaTeX}\\
Busca em Profundidade}
\author{coelho}

\maketitle

\tableofcontents


\N{2}{1}Introdução.

Existem pelo menos duas maneiras populares de se fazer busca
sistemática em um grafo: busca em largura (\textit{breadth-first
search} e busca em profundidade (depth-first search). Neste programa
implementamos a versão recursiva de busca em profundidade.




\fi

\N{2}{2}O que o programa faz.  Este programa recebe um grafo, através de um
arquivo no formato do \sgb\ ou de uma opção para gerá-lo, e constrói
uma floresta de busca em profundidade do grafo.


\fi

\N{2}{3}Como usar o programa.
Para usar o programa o
usuário deve, na linha de comando, escrever
\begin{quote}
\texttt{meu\_prompt> dfs \opcao{opções}}
\end{quote}
onde \texttt{\opcao{opções}} consiste de zero ou mais das seguintes
especificações em qualquer ordem
\begin{description}
\item[\texttt{-r}]  Usa a subrotina \PB{\\{random\_graph}} do módulo
\gbr\ do \sgb\ para gerar um grafo pseudo-aleatório com \PB{\|n}
vértice \PB{\|m} arcos ou arestas, usando um gerador de números
pseudo-aleatórios que depende de um semente (veja opção \texttt{-s}).

\item[\texttt{-c}] Usa a subrotina \PB{\\{circuit}} do módulo \gbb\ do
\sgb\ para gerar um circuito simétrico com \PB{\|n} vértices. Todo
circuito é hamiltoniano.

\item[\texttt{-e}] Usa a subrotina \PB{\\{empty}} do módulo \gbb\ do
\sgb\ para gerar um grafo com \PB{\|n} vértices e zero arcos.
O grafo sem arcos não é hamiltoniano.

\item[\texttt{-p}] Usa a subrotina \PB{\\{petersen}} do módulo \gbb\ do
\sgb\ para gerar o grafo de Petersen. O grafo de Petersen não é
hamiltoniano.

\item[\texttt{-t}] Usa a subrotina \PB{\\{transitive}} do módulo \gbb\ do
\sgb\ para gerar um torneio com \PB{\|n} vértices. Um torneio é um grafo
que tem um arco de \PB{\|u} a \PB{\|v} se \PB{$\|u<\|v$}. Torneios não são
hamiltonianos.

\item[\texttt{-k}] Usa a subrotina \PB{\\{complete}} do módulo \gbb\ do
\sgb\ para gerar um grafo simétrico completo com \PB{\|n} vértices. Num
grafo completo simétrico temos uma arco de \PB{\|u} a \PB{\|v} para cada para
\PB{\|u} e \PB{\|v} de vértices distintos. Todo grafo completo simétrico é
hamiltoniano.

\item[\texttt{-g\opcao{nome}}] Nenhum grafo será gerado. O grafo sobre
o qual o programa trabalhará será lido do arquivo  \opcao{nome}.

\item[\texttt{-s\opcao{número}}] Usa o número \PB{\|s} como semente do
gerardor de números pseudo-aleatórios, onde \PB{\|s} é o \opcao{número} dado.

\item[\texttt{-n\opcao{número}}] O grafo gerado terá \PB{\|n} vértices,
onde \PB{\|n} é o \opcao{número} dado.

\item[\texttt{-m\opcao{número}}] O grafo gerado terá \PB{\|m} arcos ou
arestas, onde \PB{\|m} é o \opcao{número} dado.

\item[\texttt{-h\opcao{número}}] Usa a heurística do vértice de grau de
saída mínimo.

\item[\texttt{-o\opcao{nome}}] O grafo de trabalho é salvo no arquivo
\opcao{nome}.
\end{description}
É evidente que só faz sentido usar apenas uma entre as opções \texttt{-r,
-c, -e, -p, -t, -k, -g}. Também não faz sentido usar a opção
\texttt{-g} junto com as opções \texttt{-n, -s} e \texttt{-m}. Só faz
sentido usar a opção \texttt{-m} junto com \texttt{-r}.

Como de hábito, caso o usuário escreva apenas
\begin{center}
\texttt{meu\_prompt> dfs}
\end{center}
o programa deve descrever o seu funcionamento.

\Y\B\4\X3:Função \PB{\\{mostre\_uso}}\X${}\E{}$\6
\&{void} \\{mostre\_uso}(\,)\1\1\2\2\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stdout},{}$\6
\.{"Uso:\ \%s\ <opcoes>\\n"}\6
\.{"onde\ <opcoes>\ consi}\)\.{ste\ de\ zero\ ou\ mais\ }\)\.{das\ seguintes\
especi}\)\.{ficações:\\n"}\6
\.{"\ \ \ \ \ -r\ \ grafo\ pseu}\)\.{do-aleatorio\ com\ n\ v}\)\.{ertices\ e\ m%
\ arestas\\}\)\.{n"}\6
\.{"\ \ \ \ \ -c\ \ circuito\ c}\)\.{om\ n\ vertices\\n"}\6
\.{"\ \ \ \ \ -e\ \ grafo\ com\ }\)\.{n\ vertices\ e\ zero\ ar}\)\.{cos\\n"}\6
\.{"\ \ \ \ \ -p\ \ grafo\ de\ P}\)\.{etersen\\n"}\6
\.{"\ \ \ \ \ -t\ \ torneio\ co}\)\.{m\ n\ vertices\\n"}\6
\.{"\ \ \ \ \ -k\ \ grafo\ sime}\)\.{trico\ completo\ com\ n}\)\.{\ vertices%
\\n"}\6
\.{"\ \ \ \ \ -g<nome>\ traba}\)\.{lha\ com\ o\ grafo\ do\ a}\)\.{rquivo\
<nome>\\n"}\6
\.{"\ \ \ \ \ -s<num>\ \ para\ }\)\.{o\ gerar\ numeros\ pseu}\)\.{do-aleatorios%
\\n"}\6
\.{"\ \ \ \ \ -n<num>\ numero}\)\.{\ de\ vertices\\n"}\6
\.{"\ \ \ \ \ -m<num>\ numero}\)\.{\ de\ arcos/arestas\\n"}\6
\.{"\ \ \ \ \ -o<nome>\ grafo}\)\.{\ de\ trabalho\ sera\ sa}\)\.{lvo\ no\
arquivo\ <nome}\)\.{>\\n"}\6
${},\39\\{nome\_programa});{}$\6
\\{exit}(\T{0});\6
\4${}\}{}$\2\par
\U6.\fi

\N{2}{4}Estrutura geral do programa.
Abaixo encontra-se o `layout' do programa, como é visto pelo
compilador \texttt{C}.


\Y\B\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{include} \.{"gb\_graph.h"}\C{ estruturas de dados padrão do \sgb\ }\6
\8\#\&{include} \.{"gb\_save.h"}\C{ rotinas para ler e salvar um grafo }\6
\8\#\&{include} \.{"gb\_basic.h"}\C{ rotinas para gerar alguns grafos básicos }%
\6
\8\#\&{include} \.{"gb\_rand.h"}\C{ produz um grafo pseudo-aleatório }\6
\ATH\7
\X5:Variáveis globais\X\6
\X6:Declaração de funções\X\7
\&{int} ${}\\{main}(\\{argc},\39\\{argv}){}$\1\1\6
\&{int} \\{argc};\C{ o número de argumentos na linha de comando }\6
\&{char} ${}{*}\\{argv}[\,]{}$;\C{ o vetor de strings contendo os argumentos }%
\2\2\6
${}\{{}$\1\6
\X7:Variáveis locais do \PB{\\{main}}\X;\6
\X8:Examine as opções na linha de comando\X;\6
\X10:Crie o grafo \PB{\|g} dado\X;\6
\X15:Construa uma floresta dfs de \PB{\|g}\X;\6
\&{if} (\\{salva\_arquivo})\1\5
\X23:Salve o grafo \PB{\|g} no arquivo \PB{\\{salva\_arquivo}}\X;\2\6
\\{gb\_recycle}(\|g);\C{ devolve a memória usada por \PB{\|g} }\6
\&{return} \T{0};\C{ termino normal }\6
\4${}\}{}$\2\par
\fi

\M{5} Gosto que \PB{\\{nome\_programa}} e algumas outras variáveis sejam
globais.

\Y\B\4\X5:Variáveis globais\X${}\E{}$\6
\&{typedef} \&{enum} ${}\{{}$\1\6
${}\.{FALSE},\39\.{TRUE}{}$\2\6
${}\}{}$ \&{Boolean};\6
\&{char} ${}{*}\\{nome\_programa}\K\NULL{}$;\C{ nome do programa }\par
\As11\ET12.
\U4.\fi

\M{6}A seguir está a lista de funções que fazem parte do programa.
\Y\B\4\X6:Declaração de funções\X${}\E{}$\6
\X3:Função \PB{\\{mostre\_uso}}\X\6
\X16:Função \PB{\\{dfs\_r}}\X\par
\U4.\fi

\N{2}{7}Tratamento das opções.
Entre as váriaveis local do \PB{\\{main}} teremos o grafo \PB{\|g} sobre o qual
trabalharemos. Outras variáveis são relativas a opções do programa.
Estas váriáveis são inicializadas com seu valores default. Assim
\begin{center}
\texttt{meu\_prompt> dfs -n30}
\end{center}
tem o mesmo efeito que
\begin{center}
\texttt{meu\_prompt> dfs -r -n30 -m100}
\end{center}


\Y\B\4\X7:Variáveis locais do \PB{\\{main}}\X${}\E{}$\6
\&{unsigned} \&{long} \|n${}\K\T{20}{}$;\C{ número de vértices }\6
\&{unsigned} \&{long} \|m${}\K\T{100}{}$;\C{ número de arcos    }\6
\&{long} \\{directed}${}\K\T{1}{}$;\C{ o grafo gerado não precisa ser simétrico
}\6
\&{long} \\{seed}${}\K\T{0}{}$;\C{ semente para o gerador pseudo-aleatório }\6
\&{Boolean} \\{aleatório}${}\K\.{FALSE}{}$;\C{ gerar um grafo pseudo-aleatório
}\6
\&{Boolean} \\{circuito}${}\K\.{FALSE}{}$;\C{ gerar um circuito  }\6
\&{Boolean} \\{vazio}${}\K\.{FALSE}{}$;\C{ gerar um grafo sem arcos }\6
\&{Boolean} \\{petersen}${}\K\.{FALSE}{}$;\C{ gerar o grafo de Petersen }\6
\&{Boolean} \\{torneio}${}\K\.{FALSE}{}$;\C{ gerar um torneio }\6
\&{Boolean} \\{completo}${}\K\.{FALSE}{}$;\C{ gerar um grafo completo }\6
\&{Boolean} \\{heurística}${}\K\.{TRUE}{}$;\C{ heurística do grao de saída
mínimo }\6
\&{Boolean} \\{escolheu}${}\K\.{FALSE}{}$;\C{ indica se foi escolhido como
criar o grafo }\6
\&{char} ${}{*}\\{nome\_arquivo}\K\NULL{}$;\C{ nome do arquivo do grafo de
trabalho }\6
\&{char} ${}{*}\\{salva\_arquivo}\K\NULL{}$;\C{ para salvar o grafo de trabalho
}\par
\A9.
\U4.\fi

\M{8}As opções podem ser fornecidas em qualquer ordem. Se o grafo é dado
por mais de uma maneira (opções \texttt{-r, -c, -e, -p, -t, -k} ou
\texttt{-g}), o programa pára com uma mensagem de erro. A variável
\PB{\\{escolheu}} é usada para detectar este tipo de inconsistência. Está é a
única inconsistência verificada na linha de comando. Assim, por exemplo,
o programa não reclama se for chamado com as opções \texttt{-c -n10 -m1000};
note que todo circuito com 10 vértices tem 20 arcos.


\Y\B\4\X8:Examine as opções na linha de comando\X${}\E{}$\6
$\\{nome\_programa}\K\\{argv}[\T{0}];{}$\6
\&{if} ${}(\\{argc}\E\T{1}){}$\1\5
\\{mostre\_uso}(\,);\2\6
\&{while} ${}(\MM\\{argc}){}$\5
${}\{{}$\1\6
\&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-r"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{aleatório}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-c"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{circuito}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-e"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{vazio}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-p"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{petersen}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-t"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{torneio}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-k"})\E\T{0}\W\R%
\\{escolheu}){}$\1\5
${}\\{escolheu}\K\\{completo}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{strncmp}(\\{argv}[\\{argc}],\39\.{"-g"},\39\T{2})\E\T{0}%
\W\R\\{escolheu}){}$\5
${}\{{}$\1\6
${}\\{escolheu}\K\.{TRUE};{}$\6
${}\\{nome\_arquivo}\K\\{argv}[\\{argc}]+\T{2};{}$\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\\{strcmp}(\\{argv}[\\{argc}],\39\.{"-h"})\E\T{0}){}$\1\5
${}\\{heurística}\K\.{TRUE};{}$\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-n\%lu"},\39{\AND}\|n)%
\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-m\%lu"},\39{\AND}\|m)%
\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{sscanf}(\\{argv}[\\{argc}],\39\.{"-s\%ld"},\39{\AND}%
\\{seed})\E\T{1}){}$\1\5
;\2\6
\&{else} \&{if} ${}(\\{strncmp}(\\{argv}[\\{argc}],\39\.{"-o"},\39\T{2})\E%
\T{0}){}$\1\5
${}\\{salva\_arquivo}\K\\{argv}[\\{argc}]+\T{2};{}$\2\6
\&{else}\5
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"Uso:\ \%s\ [-r|-c|-e|-}\)\.{p|-t|-k|-g<nome>]]%
\ [}\)\.{-h]\ [-s<semente>]\ [-}\)\.{n<num>]\ [-m<num>]\ [-}\)\.{o<nome>]\\n"},%
\39\\{nome\_programa});{}$\6
\&{return} ${}{-}\T{1};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\6
\&{if} ${}(\R\\{escolheu}){}$\1\5
${}\\{aleatório}\K\.{TRUE}{}$;\C{ opção default }\2\par
\U4.\fi

\N{2}{9}Criação do grafo. O trabalho desta parte do programa é construir ou
reconstruir o grafo \PB{\|g} sobre o qual trabalharemos. O grafo será
construído se algumas das opções de geração automática do grafo foi
usada. Caso a opção \texttt{-g\opcao{nome}} tenha sido usada o grafo
será recontruído a partir do conteúdo de \PB{\\{nome\_arquivo}}. A criação
do grafo depende da

\Y\B\4\X7:Variáveis locais do \PB{\\{main}}\X${}\mathrel+\E{}$\6
\&{Graph} ${}{*}\|g\K\NULL{}$;\C{ grafo de trabalho }\par
\fi

\M{10}Se uma rotina de criação do grafo encontrar um problema, ela devolve
\PB{$\NULL$} (ou seja, \texttt{NULL}), depois de colocar um número de código
que
identifica o erro na variável externa \PB{\\{panic\_code}}.  Se não ocorrer
problemas a rotina devolve o endereço do grafo criado (\PB{\&{Graph} ${}{*}$}).


\Y\B\4\X10:Crie o grafo \PB{\|g} dado\X${}\E{}$\6
\&{if} (\\{aleatório})\1\5
${}\|g\K\\{random\_graph}(\|n,\39\|m,\39\T{0},\39\T{0},\39\\{directed},\39%
\NULL,\39\NULL,\39\T{1},\39\T{1},\39\\{seed});{}$\2\6
\&{else} \&{if} (\\{circuito})\1\5
${}\|g\K\\{circuit}(\|n);{}$\2\6
\&{else} \&{if} (\\{vazio})\1\5
${}\|g\K\\{empty}(\|n);{}$\2\6
\&{else} \&{if} (\\{petersen})\1\5
${}\|g\K\\{petersen}(\,);{}$\2\6
\&{else} \&{if} (\\{torneio})\1\5
${}\|g\K\\{transitive}(\|n);{}$\2\6
\&{else} \&{if} (\\{completo})\1\5
${}\|g\K\\{complete}(\|n);{}$\2\6
\&{else} \&{if} (\\{nome\_arquivo})\1\5
${}\|g\K\\{restore\_graph}(\\{nome\_arquivo}){}$;\2\6
\&{if} ${}(\|g\E\NULL{}$)\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\%s:\ grafo\ nao\ pode\ }\)\.{ser\ criado\
(codigo\ d}\)\.{o\ erro:\ \%ld)\\n"},\39\\{nome\_programa},\39\\{panic%
\_code});{}$\6
\&{return} ${}{-}\T{1}{}$;\C{ Opsss ... }\6
\4${}\}{}$\2\6
${}\\{fprintf}(\\{stdout},\39\.{"grafo:\ \%s.\\nnumero\ }\)\.{de\ vertices:\ %
\%ld.\\nn}\)\.{umero\ de\ arcos:\ \%ld.}\)\.{\\n"},\39\|g\MG\\{id},\39\|g\MG%
\|n,\39\|g\MG\|m){}$;\par
\A14.
\U4.\fi

\N{2}{11}Busca em profundidade. Finalmente chegamos ao coração do programa.
Durante a execução do programa cada vértice do grafo está no estado
\PB{\.{NÃOVISTO}}, \PB{\.{VISITADO}}  ou
\PB{\.{EXAMINADO}}. Um vértice \PB{\|u} está no estado \PB{\.{NÃOVISTO}} se
programa ainda
não encontro um caminho de \PB{\|r} até \PB{\|u}. Os vértices \PB{\.{VISITADO}}
fazem
parte de um caminho na iteração corrente
de um vértice raiz \PB{\|r} a um vértice \PB{\|u}. Um vértice \PB{\|u} está no
estado
\PB{\.{EXAMINADO}} se todos os arcos com ponto inicial em \PB{\|u} já foram
examinados.

A estruturas de dados que representa o estado corrente do algoritmo é
implementada usando três `utility fields' em cada vértice: \PB{\\{estado}}, %
\PB{\\{pred}}
(predecessor). Além disso ainda há um campo que guarda o número
\PB{\\{pré\_ordem}} do vértices.  Consideraremos cada um deles separadamente.


\Y\B\4\D$\\{estado}$ \5
$\|z.{}$\|I\C{ o \PB{\\{estado}} de um vértice é armazenado no utility field %
\PB{\|z} }\par
\Y\B\4\X5:Variáveis globais\X${}\mathrel+\E{}$\6
\&{enum} ${}\{{}$\1\6
${}\.{NÃOVISTO}\K\T{0},\39\.{VISITADO}\K\T{1},\39\.{EXAMINADO}\K\T{2}{}$\2\6
${}\}{}$;\par
\fi

\M{12}Os vértices no estado \PB{\.{VISITADO}} formam um caminho de um vértice
raiz \PB{\|r} a um vértice
\PB{\|u}.  Todo vértice \PB{\.{VISITADO}} tem um predecessor no caminho,
indicado pelo campo
\PB{\\{pred}}. Este predecessor é outro vértice
ativo; a única excessão é a raiz \PB{\|r} que tem ele mesmo como predecessor.
Assim,
um arco de \PB{\|v} a \PB{\|w} no caminho é
representado na estrutura por \PB{$\|w\MG\\{pred}\E\|v$}. O campo \PB{\\{pred}}
permite que o
programa faça backtracking no caminho.

Os campos \PB{\\{pred}} mantém a chamada
\textit{arvoré de busca em profundidade}.
Assim, no fundo, o programa mantém uma representação `reversa' do caminho
corrente de \PB{\|r} a cada vértice \PB{\|u} na árvore de busca emprofundidade,
ou
seja, o caminho de \PB{\|r} a um vértice \PB{\|u} \PB{\.{VISITADO}} ou \PB{%
\.{EXMINADO}}.
\begin{center}
\caminho{\PB{$\|s\K\|u\MG\\{pred}$ $\MG$}\ldots\PB{$\MG$ \\{pred} $,$}\ldots%
\PB{$,$ $\|u\MG\\{pred}\MG\\{pred}\MG\\{pred},\|u\MG\\{pred}\MG\\{pred},\|u\MG%
\\{pred},\|u$}}.
\end{center}

\Y\B\4\D$\\{pred}$ \5
$\|y.{}$\|V\C{ o predecessor (\PB{\\{pred}}) de um vértice e armazenado no
utility field \PB{\|x}}\par
\B\4\D$\\{pré\_ordem}$ \5
$\|x.{}$\|I\C{ número pré-ordem do vértice }\par
\B\4\D$\\{pós\_ordem}$ \5
$\|w.{}$\|I\C{ número pós-ordem do vértice }\par
\Y\B\4\X5:Variáveis globais\X${}\mathrel+\E{}$\6
\&{long} \\{préordem}${}\K\T{0};{}$\6
\&{long} \\{pósordem}${}\K\T{0}{}$;\par
\fi

\M{13}Busca em profundidade explora um grafo sistematicamente, visitando
todos os vértices e verificando para onde estes vértices podem nos conduzir.
O vértice no estado \PB{\.{VISITADO}} que é ponta final do caminho corrente é %
\PB{\|u}.

Há três possibilidade, o arco \PB{\|a} com ponta inicial em \PB{\|u} tem ponta
final \PB{$\|a\MG\\{tip}$} em um vértice \PB{\|v} que é \PB{\.{NÃOVISTO}}, \PB{%
\.{VISITADO}} ou
\PB{\.{EXAMINADO}}.  Se o vértice \PB{\|v} é \PB{\.{VISITADO}}, então \PB{\|v}
já faz parte do
caminho corrente e tentaremos estender o caminho através do arco
sucessor de \PB{\|a} na lista de adjacência de \PB{\|u}. O mesmo é feito se %
\PB{\|v} é
\PB{\.{EXAMINADO}}. Caso \PB{\|v} seja \PB{\.{NÃOVISTO}}, marcamos \PB{\|v}
como \PB{\.{VISITADO}} e
\PB{\|v} passa a ser a nova ponta final do caminho corrente e passamos a
examinar os arcos com ponta inicial nele. Se chegarmos a um ponto em que
todos os arcos com ponta inicial em \PB{\|u} nos levam a vértices \PB{%
\.{VISITADOS}}
ou \PB{\.{EXAMINADOS}}, chegou a hora de dar um passo atrás e fazer com que
\PB{$\|u\MG\\{pred}$} volte a ser a ponta final do caminho.

\fi

\M{14}O campo \PB{\\{util\_types}} de um grafo contém um string de comprimento
14,
seguido do caractere nulo `\PB{\\T{0}}'. Os primeiros 6 caracteres do
\PB{\\{util\_type}} indicam o uso dos campos utilitários \PB{$\|u,\|v,\|w,\|x,%
\|y$} e \PB{\|z}
dos registros \PB{\&{Vertex}}. Os próximos dois caracteres dão o formato dos
campos utilitários \PB{\|a} e \PB{\|b} em \PB{\&{Arc}}. Finalmente, os seis
último caracteres
mostram o formato dos campos utilitários \PB{$\\{uu},\\{vv},\\{ww},\\{xx},%
\\{yy}$} e \PB{\\{zz}} em
\PB{\&{Graph}}.
Cada caractere deve ser um \texttt{I} (denotando um inteiro longo),
\texttt{S}  (representando o endereço de um string), \texttt{V}
(indicando o endereço de um \PB{\&{Vertex}}), \texttt{A} (denotando o endereço
de um \PB{\&{Arc}}), \texttt{G} (endereço de um \PB{\&{Graph}}), ou \texttt{Z}
(significando que o campo não está em uso).

\Y\B\4\X10:Crie o grafo \PB{\|g} dado\X${}\mathrel+\E{}$\6
$\\{strcpy}(\|g\MG\\{util\_types},\39\.{"ZZIIVIZZZZZZZZ"}){}$;\par
\fi

\N{2}{15}Construção da floresta dfs.

\Y\B\4\X15:Construa uma floresta dfs de \PB{\|g}\X${}\E{}$\6
${}\{{}$\1\6
\&{register} \&{Vertex} ${}{*}\|v{}$;\7
\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$
${}\|v\PP{}$)\6
${}\{{}$\1\6
${}\|v\MG\\{estado}\K\.{NÃOVISTO};{}$\6
${}\|v\MG\\{pred}\K\|v;{}$\6
\4${}\}{}$\2\7
\&{for} ${}(\|v\K\|g\MG\\{vertices};{}$ ${}\|v<\|g\MG\\{vertices}+\|g\MG\|n;{}$
${}\|v\PP{}$)\1\6
\&{if} ${}(\|v\MG\\{estado}\E\.{NÃOVISTO}{}$)\1\6
${}\\{dfs\_r}(\|g,\39\|v);{}$\2\2\6
\4${}\}{}$\2\par
\U4.\fi

\M{16}Função \PB{\\{dfs\_r}}.

\Y\B\4\X16:Função \PB{\\{dfs\_r}}\X${}\E{}$\6
\&{void} \\{dfs\_r}(\&{Graph} ${}{*}\|g,\39{}$\&{Vertex} ${}{*}\|r){}$\1\1\2\2\6
${}\{{}$\1\6
\&{register} \&{Arc} ${}{*}\|a{}$;\7
\X22:Visita em pré-ordem de \PB{\|r}\X;\6
${}\|r\MG\\{pré\_ordem}\K\PP\\{préordem}{}$;\6
${}\|r\MG\\{estado}\K\.{VISITADO}{}$;\7
\&{for} ${}(\|a\K\|r\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next}{}$)\6
${}\{{}$\C{ examina o arco \PB{\|a} }\1\6
\&{Vertex} ${}{*}\|v\K\|a\MG\\{tip}{}$;\7
\&{if} ${}(\|v\MG\\{estado}\E\.{NÃOVISTO}{}$)\6
${}\{{}$\1\6
\X17:Trata o tree arc \PB{\\{rv}}\X;\6
${}\\{dfs\_r}(\|g,\39\|v){}$;\6
${}\|v\MG\\{pred}\K\|r{}$;\C{ \PB{\\{pred}} guarda a árvore \PB{\\{dfs}} }\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\|v\MG\\{estado}\E\.{VISITADO}{}$)\6
${}\{{}$\C{ achou um ciclo }\1\6
\X18:Trata o back arc \PB{\\{rv}}\X;\6
\4${}\}{}$\2\6
\&{else} \&{if} ${}(\|v\MG\\{estado}\E\.{EXAMINADO}\W\|r\MG\\{pré\_ordem}>\|v%
\MG\\{pré\_ordem}){}$\5
${}\{{}$\1\6
\X19:Trata o forward arc \PB{\\{rv}}\X;\6
\4${}\}{}$\2\6
\&{else}\C{ \PB{$\|v\MG\\{estado}\E\.{EXAMINADO}\W\|r\MG\\{pré\_ordem}<\|v\MG%
\\{pré\_ordem}$} }\6
${}\{{}$\1\6
\X20:Trata o cross arc \PB{\\{rv}}\X;\6
\4${}\}{}$\2\6
\4${}\}{}$\2\7
${}\|r\MG\\{estado}\K\.{EXAMINADO};{}$\6
\X21:Visita em pós-ordem de \PB{\|r}\X;\6
${}\|r\MG\\{pós\_ordem}\K\PP\\{pósordem};{}$\6
\4${}\}{}$\2\par
\U6.\fi

\M{17}Isto é só para não dar erro de sintaxe. Pode ser necessário dependendo
da aplicação.

\Y\B\4\X17:Trata o tree arc \PB{\\{rv}}\X${}\E{}$\6
$\{\,\}{}$\par
\U16.\fi

\M{18}Isto é só para não dar erro de sintaxe. Pode ser necessário dependendo
da aplicação.
\Y\B\4\X18:Trata o back arc \PB{\\{rv}}\X${}\E{}$\6
$\{\,\}{}$\par
\U16.\fi

\M{19}Isto é só para não dar erro de sintaxe. Pode ser necessário dependendo
da aplicação.
\Y\B\4\X19:Trata o forward arc \PB{\\{rv}}\X${}\E{}$\6
$\{\,\}{}$\par
\U16.\fi

\M{20}Isto é só para não dar erro de sintaxe. Pode ser necessário dependendo
da aplicação.
\Y\B\4\X20:Trata o cross arc \PB{\\{rv}}\X${}\E{}$\6
$\{\,\}{}$\par
\U16.\fi

\M{21}Isto é só para não dar erro de sintaxe. Pode ser necessário dependendo
da aplicação.
\Y\B\4\X21:Visita em pós-ordem de \PB{\|r}\X${}\E{}$\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stdout},\39\.{"\%s\\n"},\39\|r\MG\\{name});{}$\6
\4${}\}{}$\2\par
\U16.\fi

\M{22}Isto é só para não dar erro de sintaxe. Pode ser necessário dependendo
da aplicação.
\Y\B\4\X22:Visita em pré-ordem de \PB{\|r}\X${}\E{}$\6
$\{\,\}{}$\par
\U16.\fi

\N{2}{23}Salva grafo. Se o usuário utilizou a opção
\texttt{-o}\opcao{nome} o grafo \PB{\|g} é salvo no arquivo
\opcao{nome}. É usual que o arquivo que contém um grafo no formato do
\sgb\ tenha a extensão \texttt{.gb}. Para salvar um grafo usamos a
subrotina \PB{\\{gb\_save}} do módulo \gbs\ do \sgb.



\Y\B\4\X23:Salve o grafo \PB{\|g} no arquivo \PB{\\{salva\_arquivo}}\X${}\E{}$\6
${}\{{}$\1\6
\&{long} \\{anomalia}${}\K\\{save\_graph}(\|g,\39\\{salva\_arquivo});{}$\7
\&{if} (\\{anomalia})\6
${}\{{}$\1\6
${}\\{fprintf}(\\{stderr},\39\.{"\%s:\ grafo\ nao\ pode\ }\)\.{ser\ salvo\ no\
arquivo}\)\.{"}\.{"\ \%s\ (codigo\ do\ erro}\)\.{:\ \%ld)\\n"},\39\\{nome%
\_programa},\39\\{salva\_arquivo},\39\\{anomalia});{}$\6
\\{gb\_recycle}(\|g);\6
\&{return} ${}{-}\T{2}{}$;\C{ Opsss ... }\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U4.\fi

\M{24}

\cwebIndexIntro{%
Aqui vai uma lista de identificadores usados e onde eles aparecem.
Entradas grifadas indicam os lugares de definições. Mensagens de erros
também são mostradas.
}

\end{document}


\fi


\inx
\fin
\con
