Trabalho I - 2010/2
Entrega: 26/10/2010
PLANEJANDO SEU ROTEIRO DE VIAGEM
Este trabalho foi criado inspirado no site www.europebyair.com,
que vende passagens aéreas. Quando você clica no mapa dentro do site
aparece uma tela com um mapa da Europa com todas as cidades servidas
pela companhia. Quando clica sobre uma cidade, todos os trechos que tem
como origem aquela cidade são mostrados graficamente através de arcos
daquela cidade para para cada um dos destinos. Na verdade o conjunto
das cidades e trechos formam um grafo.
Neste trabalho, você vai ler um
arquivo com um conjunto de cidades e trechos como no exemplo abaixo.
Por exemplo, a cidade de Lisbon tem conexão direta para .... Note que
a lista de conexões originadas em cada cidade é terminada sempre com
uma # para facilitar a leitura (usando >>).
NOTA: Assuma que as rotas são
bidirecionais. Por exemplo: se existe rota de Lisbon para London (como
expresso na primeira linha do exemplo abaixo) então também existe
rota de London para Lisbon, mesmo que esta não esteja inclusa na lista
de destinos de London (exatamente como ocorre no exemplo abaixo, vide
segunda linha).
Lisbon London Brussels Paris Barcelona Madrid #
London Canaries Palma Paris Munich #
Brussels Lisbon Barcelona Palma Munich #
Paris Lisbon Madrid London #
Barcelona Lisbon Brussels Venice Naples #
Madrid Lisbon London Brussels Paris Frankfurt Munich Milan Rome #
Canaries London #
Palma Brussels #
Munich London Madrid Rome Brussels Athens #
Venice Brussels Barcelona Athens #
Naples Barcelona Milan #
Milan Lisbon Madrid Brussels Rome Naples Athens #
Athens Brussels Munich Milan Venice Rome Rhodes #
Rhodes Athens #
O programa deverá implementar dois modos: o modo JOGO e o modo EDIÇÃO.
1. Modo JOGO ou PLANEJAMENTO DE VIAGEM:
Neste modo o usuário fornece uma cidade origem e uma cidade destino. O programa entra então em um loop.
Inicialmente mostra a cidade origem com todas as cidades para as quais
esta cidade tem voô direto e pede ao usuário para escolher uma. A cada
escolha o programa volta ao início do loop mostrando a última cidade
escolhida com todas as cidades para as quais esta cidade tem vôo direto
e pede ao usuário para escolher uma. E assim por diante.
O programa termina quando a cidade escolhida pelo usuário coincidir com
a cidade destino do início do jogo. Neste momento o programa imprime a
rota completa selecionada (inclusive com repetições de cidade se as
ecolhas do usuário contiverem loops) e o número de vôos.
VARIANTE: Você pode também fazer com que o programa escolha aleatoriamente as cidades de origem e destino do jogo.
2. Modo EDIÇÃO ou MANUTENÇÃO:
Neste modo o usuário deve permitir a alteração do grafo através de operações como:
(a) inserir nova cidade;
(b) inserir novo trecho;
(c) remover cidade;
(d) remover trecho;
(e) salvar em arquivo.
3. Modo MENOR CAMINHO:
Se você quiser tentar algo diferente pode implementar um algum
algoritmo que encontre e imprima o menor caminho entre duas cidades.
Isto é opcional e também pode ser feito em substituição ao modo de edição.
Há algorimos para encontrar o menor caminho em grafos (e.g., para
single source: Dijkstra’s) em vários livros de algoritmos (e.g,
Cormen, Leiserson & Rivest; Weiss; Aho, Hopcroft & Ullman, etc.)
Aqui vão alguns detalhes e sugestões:
1.
O programa deverá usar intensivamente estruturas de dados flexíveis
como listas, conjuntos, mapeamentos, onde apropriado, com alocação
dinâmica de memória, ao invés do uso de vetores do C++.
2. Sugere-se a utilização da biblioteca STL.
3. Cada cidade pode ser um nodo do grafo.
4. Deve haver uma estrutura
mestre de acesso a todos os nodos que pode ser uma list, set com
ponteiros para nodos, ou melhor ainda um map de strings (nome da
cidade) para ponteiro para nodo.
5. Cada nodo tem o nome da cidade e o conjunto de nodos para cujas cidades há uma rota direta partindo da cidade deste nodo.
DATA DA ENTREGA: 26/10/2010
FIM
