E10 WordGraphs + Cycles = WordLoops
Word ladders. Veja inicialmente o Web Exercise 4.1.11, Word ladders, de S&W (os programas WordLadder.java e IndexSET.java seguem abaixo). Para as origens de word ladders, inventadas dor Lewis Carroll, veja
https://en.wikipedia.org/wiki/Word_ladder
No Web Exercise 4.1.11 de S&W, há um grafo subjacente: o grafo em que duas palavras são ligadas por uma aresta se elas têm o mesmo comprimento e diferem exatamente em uma letra. Um word ladder de uma palavra \(s\) para um palavra $t$ é um caminho mais curto nesse grafo.
Word graphs. Nos grafos deste exercício, vamos ligar duas palavras \(s\) e $t$ se (i) $s$ e $t$ têm o mesmo comprimento e diferem exatamente em uma letra, ou (ii) $s$ e $t$ têm comprimentos que diferem de exatamente um, e a palavra mais curta pode ser obtida da palavra mais longa apagando-se uma de suas letras. Assim, nossos grafos têm mais arestas que os grafos de Lewis Carroll e podemos encontrar ladders entre palavras de comprimentos diferentes:
ir
vir
via
voa
vota
votar
voltar
O programa WordGraphPlain.java fornecido monta tais grafos. O programa WordComponentsPlain.java pode ser usado para verificar a estrutura de componentes desses grafos. Você pode também encontrar word ladders generalizados como o word ladder acima entre "ir" e "voltar" usando WordLadderGeneralizedPlain.java.
Observação. Neste exercício, precisaremos de listas de "palavras válidas". Você pode supor que nenhuma palavra com "." será dada em tais listas (por exemplo, abreviações como "prof." não estarão nessas listas). Em nossos exemplos, usamos a lista de palavras em
https://www.ime.usp.br/~yoshi/DATA/Pwords
Geração mais eficiente de word graphs. Sua primeira tarefa é escrever uma versão mais eficiente de WordGraphPlain.java. Seu programa deve chamar-se WordGraph.java.
O programa WordComponents.java, que usa WordGraph.java em vez de WordGraphPlain.java, pode ser usado para conferir a estrutura de componentes dos grafos gerados por WordGraph.java. Naturalmente, com o mesmo conjunto de palavras, os programas WordComponents.java e WordComponentsPlain.java devem determinar a mesma estrutura de componentes.
O desempenho esperado de seu programa WordGraph.java é como ilustrado nos exemplos de execução abaixo. Enquanto que WordGraphPlain.java é no mínimo quadrático (por que?), seu WordGraph.java deve ser próximo de linear.
Observação. Quando falamos da eficiência de WordGraph.java e de WordGraphPlain.java, referimo-nos à eficiência do construtor WordGraph() e do construtor WordGraphPlain().
Exemplos de execução
$ head -n10000 DATA/Pwords | java-algs4 WordComponentsPlain | md5
Time to produce wordgraph: 6.247
10000 vertices and 17610 edges
Ave degree: 3.522
1166 components
313234d1e3dbe667293e360971559fea
$ head -n20000 DATA/Pwords | java-algs4 WordComponentsPlain | md5
Time to produce wordgraph: 22.073
20000 vertices and 37532 edges
Ave degree: 3.7532
2167 components
7e467a8b9b453727503ae4bddd6530a4
$ head -n40000 DATA/Pwords | java-algs4 -Xss50m WordComponentsPlain | md5
Time to produce wordgraph: 90.918
40000 vertices and 79104 edges
Ave degree: 3.9552
4301 components
252521cc6d35d9d30ccbfd7fe4dfe22b
$ head -n10000 DATA/Pwords | java-algs4 WordComponents | md5
Time to produce wordgraph: 0.252
10000 vertices and 17610 edges
Ave degree: 3.522
1166 components
313234d1e3dbe667293e360971559fea
$ head -n20000 DATA/Pwords | java-algs4 WordComponents | md5
Time to produce wordgraph: 0.631
20000 vertices and 37532 edges
Ave degree: 3.7532
2167 components
7e467a8b9b453727503ae4bddd6530a4
$ head -n40000 DATA/Pwords | java-algs4 -Xss50m WordComponents | md5
Time to produce wordgraph: 0.796
40000 vertices and 79104 edges
Ave degree: 3.9552
4301 components
252521cc6d35d9d30ccbfd7fe4dfe22b
$
Circuitos. Estude agora o programa Cycles.java fornecido por S&W (Seção 4.1). Esse programa detecta circuitos em grafos. Neste exercício, você deve adicionar um novo construtor ao programa Cycle.java:
public Cycle(Graph G, int s)
Seu construtor deve produzir um objeto do tipo Cycle que "codifica" um circuito de $G$ que passa por $s$. Isto é, o trecho de código
Cycle finder = new Cycle(G, s);
if (finder.hasCycle()) {
for (int v : finder.cycle())
StdOut.print(v + " ");
StdOut.println();
} else
StdOut.println("No cycle through " + s);
deve imprimir um tal circuito (caso exista). Acrescente também a Cycle.java um método de assinatura
public int length()
que devolve o comprimento do circuito encontrado. Se nenhum circuito passando por $s$ existir, length() deve devolver $-1$. Seu programa, com esses métodos novos, deve chamar-se Cycle.java.
A chamada Cycle(G, s) deve custar tempo $O(V + E)$.
Observação. Quando pensamos em um circuito como uma sequência de vértices $x_0,x_1,\dots,x_l$, exigimos que $x_i\neq x_j$ para todo $i\neq j$ com $0<i\leq l$ e $0<j\leq l$, mas temos que $x_0=x_l$. O inteiro $l$ é o comprimento do circuito.
Word loops. Usando WordGraph.java e seu Cycle.java, podemos escrever WordLoop.java, que encontra "word loops" passando por palavras dadas pelo usuário. Se o usuário pedir um word loop passando por "estudante", uma saída válida seria
estudante [11 words]: estudante estudaste estufaste estufastes estufasses estufasse estufassem estudassem estudasses estudastes estudantes estudante
Para "professor", a saída poderia ser
professor [3 words]: professor professou professo professor
Note que word loops não precisam ser curtos: qualquer circuito no word graph que contém a palavra em questão é válido.
O programa WordLoop.java é fornecido abaixo. Para verificar se os word loops gerados por WordLoop.java estão corretos, você pode usar o programa CheckCycle.java.
Desempenho. Exemplos de execução são dados nos arquivos experiments1.txt e experiments2.txt (mesmo conjunto de execuções em duas máquinas diferentes).
Entrega. Você deve entregar seus programas WordGraph.java e Cycle.java.
- 6 de julio de 2021, 15:44
- 6 de julio de 2021, 15:48