%--------------------- Rodar ---------------------------------
/* Loop principal do projeto, responsável pelo gerenciamento das escolhas feitas pelo usuário. */
rodar :-
nl, nl,
write('*********************************************'),nl,
write('* SELECIONE UMA DAS ALTERNATIVAS *'),nl,
write('*********************************************'),nl,
write('* 1. -> Carregar grafo *'),nl,
write('* 2. -> Achar menor caminho *'),nl,
write('* 3. -> Mostrar arquivo *'),nl,
write('* 4. -> Sair *'),nl,
write('*********************************************'),nl,nl,
write('Opção'),
read(Opcao),
processar(Opcao).
%--------------------- Processar ------------------------------
/* Processa a opção 1 do menu, se o usuário a escolhe. */
processar(1):-
dirbox('Grafo','Carregar','*.GPH',Nome),
consult(Nome),
assert(arquivo(Nome)),
rodar.
/* Processa a opção 2 do menu, somente se um arquivo contendo um grafo foi aberto*/
processar(2):-
arquivo(X),
retirar_distancia,
algoritmo,
rodar.
/* Se a opção 2 foi escolhida e não havia arquivos de grafos abertos */
processar(2):-nl,
write('Voce precisa carregar o grafo!!!.'),nl,
write('Digite "0." para continuar'),
read(X),
rodar.
/* Mostra o conteúdo do arquivo escolhido */
processar(3):-
listing((inf,nos,no_adjacentes,distancia)),
nl,
write('Digite "0." para continuar'),
read(X),
rodar.
/* Termina a aplicação limpando todas as referências a arquivos já abertos */
processar(4):-retractall(arquivo(_)).
/* Se nenhuma das opções disponíveis foi escolhida */
processar(_):-rodar.
%--------------------- Mensagem ------------------------------
/* Mostra uma mensagem se Vértice de inicio é igual ao estado meta */
mensagem(Vertice,Vertice):-
nl,
write(' A distancia ‚ zero, ponto de partida'),nl,
write('e de chegada iguais.'),!,fail.
mensagem(_,_).
%--------------------- Obtêm valores ----------------------
/* Obtêm os valores do ponto de partida e de chegada.*/
obter_valores(A1,A2):-
write('Ponto de partida (número do vértice)'),
read(A1),
A1\=='',
write('Ponto final (número do vértice)'),
read(A2),
A2\==''.
%--------------------- Seta ---------------------------------
/* Mostra uma seta se o pai for diferente de zero */
seta(0):-!.
seta(_):-write(' -> ').
%-------------------- Lista Menor Caminho ---------------------
/* Mostra o menor caminho encontrado */
list_menor_caminho(0).
list_menor_caminho(Filho):-
menor_distancia(Filho,_,Pai),
list_menor_caminho(Pai),
seta(Pai),
write(Filho).
%--------------------- Mostre Menor -------------------------------
/* Mostra o menor caminho encontrado. */
mostre_menor(Inicio,Fim):-
menor_distancia(Fim,Menor,_),
nl,
write('++++++++++++++++ RESPOSTA +++++++++++++++++'),
nl, nl,
write(' CAMINHO PERCORRIDO => '),
list_menor_caminho(Fim),
nl,
write(' DISTANCIA MINIMA=> '),
write(Menor),
nl, nl,
write('--- DIGITE "0." PARA CONTINUAR ---'),
nl,
read(Nothing).
%--------------------- Retira distância --------------------
/* Retira da memória todas as referências a pesos. */
retirar_distancia:-retractall(menor_distancia(_,_,_)).
retirar_distancia.
%--------------------- Cria Pesos ---------------------------
/* Faz as inicializações de todos os vértices que estão presentes no grafo, jogando a distância de cada um para infinita */
cria_pesos(0).
cria_pesos(N):-
N>0,
inf(X),
assert(menor_distancia(N,X,0)),
N1 is N-1,
cria_pesos(N1).
%--------------------- Seta Pesos ----------------------------
/* Muda a distância atribuindo o novo peso que é passado. */
seta_pesos(Vertice,Peso,Pai):-
retract(menor_distancia(Vertice,_,_)),
assert(menor_distancia(Vertice,Peso,Pai)).
%--------------------- Insere ---------------------------------
/* Concatena duas listas */
insere(A,[],A).
insere(A,[X|Y],[X|Z]):-
insere(A,Y,Z).
% Aqui começa os predicados do algoritmo propriamente dito */
%--------------------- Algoritmo -------------------------------
/* Controla todo o processo de busca do caminho mínimo. */
algoritmo:-
obter_valores(Inicio,Fim),!, /* Obtêm os valores de inicio e fim */
mensagem(Inicio,Fim), /* Mostra mensagem.*/
nos(X), /* Obtém o número de vértices */
cria_pesos(X), /* Cria a lista de vértices, com peso infinito */
seta_pesos(Inicio,0,0), /* Distância do Inicial é zero */
while([Inicio]), /* Loop, enquanto houver elementos na lista */
mostre_menor(Inicio,Fim). /* Mostra os valores obtidos */
%--------------------- While ---------------------------------
/* Percorre todos os vértices que estão na lista. */
while([]). /* Quanto a lista estiver vazia */
while([V|Lista]):-
no_adjacentes(V,Adjacentes), /* Encontra os vértices adjacentes */
for(Adjacentes,V,L1),/* Percorre todos os adjacentes, e retorna a lista dos que mudaram suas distâncias. */
insere(Lista,L1,L2), /* Concatena a nova lista com a antiga. */
while(L2).
%--------------------- Rodar ---------------------------------
/* Quando terminar os adjacentes */
for([],_,[]):-!. /* Quando não houver mais adjacentes */
/* Se Peso(A)>Peso(V)+Distancia(A,V) */
for([A|Adjacentes],V,[A|L]):-
distancia(A,V,D),
menor_distancia(V,E,_),
menor_distancia(A,M,_),
D1 is D+E,
M>D1,
seta_pesos(A,D1,V), /* Atribui o novo peso ao vértice */
for(Adjacentes,V,L), !.
/* Se Peso(A)<=Peso(V)+Distancia(A,V) */
for([_|Adjacentes],V,L1):-
for(Adjacentes,V,L1).