\documentclass[11pt,a4paper,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
\usepackage{textcomp}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}
%----------------------------
%\usepackage[colorlinks,bookmarks,linkcolor=black,citecolor=black]{hyperref}
\usepackage{hyperref}
\hypersetup{colorlinks=false}
\usepackage{srcltx}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage{subfig}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\def\@setaddresses{\par
  \nobreak \begingroup
\footnotesize
  \def\author##1{\nobreak\addvspace\bigskipamount}%
  \def\\{\unskip, \ignorespaces}%
  \interlinepenalty\@M
  \def\address##1##2{\begingroup
    \par\addvspace\bigskipamount\indent
    \@ifnotempty{##1}{(\ignorespaces##1\unskip) }%
    {\scshape\ignorespaces##2}\par\endgroup}%
  \def\curraddr##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape Current address}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      ##2\par}\endgroup}%
  \def\email##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape Endereço eletrônico}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      \ttfamily##2\par}\endgroup}%
  \def\urladdr##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape URL}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      \ttfamily##2\par}\endgroup}%
  \addresses
  \endgroup
}
\makeatother

\def\({\left(}
\def\){\right)}
\def\<{\langle}
\def\>{\rangle}
\let\:\colon

\def\aa{{\mathtt A}}
\def\cc{{\mathtt C}}
\def\gg{{\mathtt G}}
\def\tt{{\mathtt T}}
\def\ZZ{{\mathbb Z}}
\def\RR{{\mathbb R}}
\def\FF{{\mathbb F}}
\let\:\colon
\def\bfx{\mathbf{x}}
\def\bfp{\mathbf{p}}
\def\Stanf{^\text{S}}

\def\KM{\mathop{{\rm KM}}\nolimits}

\usepackage{datetime}

\begin{document}
\onehalfspacing

\title[EP2 CCM128 1o.~semestre 2014]{%
  {\sl CCM128 Exercício-Programa 4}\\\medskip
  O modelo de Kleinberg}
\author{Y.~Kohayakawa}
\address{Instituto de Matemática e Estatística, Universidade de São Paulo, Rua
  do Matão 1010, 05508--090~São Paulo, SP}
\email{yoshi@ime.usp.br}

\def\datename{Versão de}
%\date{\today, \currenttime.  Versão preliminar} 
\date{\today, \currenttime}

\maketitle
%\thispagestyle{empty}
\footskip=25pt

\noindent\textbf{Data de entrega:}\quad 9/7/2014 (23:55)

\section{Introdução}
Este EP é apenas uma especificação mais detalhada do Exercício~4.5.44,
\textit{Kleinberg graph model}, de Sedgewick e Wayne (Creatve
Exercises). 

Para entender o contexto em que se insere este exercício, recomanda-se
uma leitura cuidadosa da Seção~4.5 de Sedgewick e Wayne.  A leitura do
Capítulo~20 de \textit{Networks, Crowds, and Markets}:
\textit{Reasoning About a Highly Connected World}, de David Easley e
Jon Kleinberg, é também fortemente recomendada.  Veja
\href{http://www.cs.cornell.edu/home/kleinber/networks-book/}%
{\texttt{http://www.cs.cornell.edu/home/kleinber/networks-book/}}.
Aliás, este livro é uma excelente fonte para diversas linhas de
pesquisa da ciência da computação atual.

\section{O modelo de Kleinberg}
\label{sec:JKModel}
Descrevemos aqui o \textit{modelo de Kleinberg} de grafo aleatório.
Consideraremos apenas o caso bidimensional desse modelo.  Seja dado um
inteiro positivo~$N$.  O grafo aleatório~$\KM(N)$ pode ser gerado da
seguinte forma: inicialmente, considere o
\textit{grafo-grade}~$N\times N$, que é o grafo com conjunto de
vértices~$[N]\times[N]$ (aqui, $[N]=\{0,1,\dots,N-1\}$) e com dois
vértices~$(x,y)$ e~$(x',y')$ adjacentes se e só se~$|x-x'|+|y-y'|=1$.
Agora, adicionamos uma aresta adicional aleatória~$e_v$ para cada
vértice~$v=(x,y)$ desse grafo-grade.  A aresta~$e_v$ incide em~$v$.
Para gerar a outra ponta de~$e_v$, escolhemos um
vértice~$w=(x',y')\in[N]\times[N]$, $w\neq v$, aleatoriamente, com a
probabilidade de gerarmos~$w$ proporcional a~$1/d(v,w)$.  Aqui,
$d(v,w)$ é a distância de~$v$ e~$w$ na assim chamada métrica~$\ell_1$
ou \textit{Manhattan distance}:
$d(v,w)=d((x,y),(x',y'))=|x-x'|+|y-y'|$.  (Lembrem-se do método
\texttt{discrete(double a[])} de \texttt{StdRandom}.)  Para
gerarmos~$\KM(N)$, adicionamos ao grafo-grade $N\times N$ todas as
arestas~$e_v$ assim geradas.  (Note que pode ocorrer de
termos~$e_v=e_{v'}$ para algum par~$v\neq v'$.)

No grafo-grade~$N\times N$, dois vértices típicos~$v$ e~$w$ estão a
uma distância~$\geq cN$, para alguma constante absoluta~$c>0$.  Neste
EP, você verá que a adição de apenas uma aresta nova por vértice
torna essa distância típica muito menor: ela torna-se algo
como~$O((\log N)^2)$.  Ademais, você verá que um algoritmo natural e
simples de roteamento fornece caminhos curtos entre quaisquer dois
vértices.

\section{O algoritmo de Kleinberg}
\label{sec:Ks_algo}
Sejam dados dois vértices~$v=(x,y)$ e~$w=(x',y')$ em~$\KM(N)$.  O
algoritmo de Kleinberg procede de forma muito natural:
sejam~$v_1,\dots,v_k$ os vizinhos de~$v$ em~$\KM(N)$.  Escolha
um~$v_i$ que seja o mais próximo possível de~$w$ na
distância~$\ell_1$.  Agora execute este algoritmo recursivamente
entre~$v_i$ e~$w$.

\section{Seu programa}
\label{sec:seu_prog}
Seu EP deve conter os seguintes componentes: \texttt{KMGraph.java} e
\texttt{KAlgorithm.java} e quaisquer outros módulos adicionais que
você achar interessante (por exemplo, para fazer o bônus abaixo,
talvez você queira implementar um módulo gráfico separado). 

\subsection{A classe \texttt{KMGraph.java}}
\label{sec:graph_model}
A classe \texttt{KMGraph.java} deve gerar grafos aleatórios de
Kleinberg~$\KM(N)$.  A saída da chamada
{\small
\begin{verbatim}
$ java-introcs KMGraph N
\end{verbatim}
} \noindent deve ser um~$\KM(N)$, no formato que temos usado para
representar grafos (os vértices de~$\KM(N)$ devem ser coisas como
\texttt{314.159}, que representa o vértice~$(314,159)$).  A classe
\texttt{KMGraph.java} deve ter um construtor, a ser usado da seguinte
maneira por seus clientes: {\small
\begin{verbatim}
  Graph G = new KMGraph(N);
\end{verbatim}
} 

\subsection{A classe \texttt{KAlgorithm.java}}
\label{sec:graph_model}
A classe \texttt{KAlgorithm.java} deve implementar o algoritmo de
Kleinberg para encontrar caminhos curtos entre vértices dos
grafos~$\KM(N)$.  Deve haver três modos de execução de
\texttt{KAlgorithm}:
{\small
\begin{verbatim}
$ java-introcs KAlgorithm N
\end{verbatim}
} 
{\small
\begin{verbatim}
$ java-introcs KAlgorithm N file.gr
\end{verbatim}
} \noindent e
{\small
\begin{verbatim}
$ java-introcs KAlgorithm
\end{verbatim}
} No primeiro caso, \texttt{KAlgorithm} deve gerar um~$\KM(N)$ e
trabalhar com este grafo.  O segundo caso é igual ao primeiro, mas seu
programa deve, adicionalmente, gravar o grafo gerado~$\KM(N)$ no
arquivo de nome \texttt{file.gr}.  Na terceira forma de execução %$
de \texttt{KAlgorithm}, seu programa deve ler um grafo de
Kleinberg~$\KM(N)$ de \texttt{stdin}, e deve trabalhar com ele.
Finalmente, para trabalhar com um grafo fixo, gravado em um arquivo
(digamos, \verb|f.gr|), o usuário poderá também dizer {\small
\begin{verbatim}
$ java-introcs KAlgorithm - f.gr
\end{verbatim}
} \noindent onde \texttt{f.gr} é um arquivo que foi gerado fazendo-se
{\small
\begin{verbatim}
$ java-introcs KMGraph N > f.gr
\end{verbatim}
} \noindent ou 
{\small
\begin{verbatim}
$ java-introcs KAlgorithm N f.gr
\end{verbatim}
}

Uma vez que \texttt{KAlgorithm} é invocado e um grafo~$\KM(N)$ está
fixo, ele deve entrar em um modo interativo (ele passa a ler
``comandos'' do \texttt{stdin} e passa a executá-los).  O usuário
poderá então emitir comandos da forma \texttt{v:}, \texttt{v:max},
\texttt{v:w}, \texttt{v:w:p}, \texttt{rand:}, \texttt{rand:max},
\texttt{rand:rand} e \texttt{rand:rand:p}.  O significado desses
comandos é como segue.

\smallskip 
\paragraph{\texttt{v:w}}
\label{sec:v:w}
neste caso, seu programa deve calcular e imprimir dois valores: (1)~a
distância entre~\texttt{v} e~\texttt{w} em~$\KM(N)$ e (2)~o
comprimento do caminho encontrado pelo algoritmo de Kleinberg
entre~\texttt{v} e~\texttt{w} em~$\KM(N)$.

\smallskip 
\paragraph{\texttt{v:w:p}}
\label{sec:v:w:p}
este caso é como \texttt{v:w}, mas devem também ser impressos os dois
caminhos encontrados (um caminho de comprimento mínimo
entre~\texttt{v} e~\texttt{w} e o caminho encontrado pelo algoritmo de
Kleinberg).

\smallskip 
\paragraph{\texttt{v:max}}
\label{sec:v:max}
neste caso, seu programa deve calcular e imprimir dois valores: (1)~o
\textit{máximo} das distâncias entre~\texttt{v} e os outros vértices
de~$\KM(N)$ e (2)~o máximo dos comprimentos dos caminhos encontrados
pelo algoritmo de Kleinberg entre~\texttt{v} e todos os outros vértices
de~$\KM(N)$.

\smallskip 
\paragraph{\texttt{v:}}
\label{sec:v:}
neste caso, seu programa deve calcular e imprimir dois valores: (1)~a
distância \textit{média} de~\texttt{v} a todos os outros vértices
de~$\KM(N)$ e (2)~o comprimento \textit{médio} dos caminhos
encontrados pelo algoritmo de Kleinberg entre~\texttt{v} e todos os
outros vértices de~$\KM(N)$.

\smallskip 
\paragraph{\texttt{rand:rand}} 
\label{sec:rand:rand}
neste caso, seu programa deve calcular e imprimir dois valores: (1)~a
distância entre dois vértices sorteados uniforme e independentemente
ao caso em~$\KM(N)$ e (2)~o comprimento do caminho encontrado pelo
algoritmo de Kleinberg entre estes dois vértices sorteados (isto é o
mesmo que executar \texttt{v:w} com~\texttt{v} e~\texttt{w} gerados de
forma aleatória).

\smallskip 
\paragraph{\texttt{rand:rand:p}}
\label{sec:rand:rand:p}
isto é como se executássemos \texttt{v:w:p} com~\texttt{v}
e~\texttt{w} gerados de forma aleatória (como acima). 

\smallskip 
\paragraph{\texttt{rand:max}}
\label{sec:rand:max}
isto é como se executássemos \texttt{v:max} com~\texttt{v}
gerado de forma aleatória (como acima). 

\smallskip 
\paragraph{\texttt{rand:}}
\label{sec:rand:}
isto é como se executássemos \texttt{v:} com~\texttt{v}
gerado de forma aleatória (como acima). 

\subsection{Desempenho do algoritmo de Kleinberg}
\label{sec:Ks_algo_check}
Escreva um programa para verificar experimentalmente que o algoritmo
de Kleinberg encontra caminhos de comprimento~$O((\log N)^2)$
em~$\KM(N)$ típicos.  Faça vários experimentos para vários valores
de~$N$ (grandes).

\subsection{Bônus}
\label{sec:bonus}
Implemente métodos gráficos que facilitem ver como as coisas
funcionam.  Por exemplo, seu EP poderia desenhar os grafos~$\KM(N)$
gerados ou sendo manipulados.  Seu EP poderia também indicar em tais
desenhos os caminhos mínimos encontrados por busca em largura e
aqueles encontrados pelo algoritmo de Kleinberg.

\subsection*{Observações} Seguem algumas observações importantes.

\small
\begin{enumerate}
\item \textit{Este EP pode ser feito em quartetos} (isso mesmo, em
  quartetos!).  Serão aceitos EPs feitos em grupos menores \verb|:-)|
\item Seja cuidadoso com sua programação (correção, documentação,
  apresentação, clareza de código, etc).  A correção não é baseada
  apenas na correção de seu programa.
\item Comparem entre vocês o desempenho de seus programas.
\item Entregue seu EP no Paca.
\item Não deixe de incluir em seu material um \textit{relatório} para
  discutir seu EP: faça quaisquer comentários que você achar
  interessante e inclua exemplos de execuções de seu programa.
\end{enumerate}

\subsubsection*{Observação final}  Enviem dúvidas para a lista de discussão da
disciplina.

%\bibliographystyle{abbrv}
%\bibliography{refs_Teach}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (flyspell-mode t)
%%% eval: (LaTeX-math-mode t)
%%% TeX-master: t
%%% End:
