PUCRS
Faculdade de Informática
Programação de Software Básico -
4613S-04


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