Graph problem
Posted: Wed Nov 23, 2011 12:29 pm
Hello everyone!
I'm a student and I'm having a few problems with my LISP work.
Well, I have to work on a graph that contains the connections between cities, and I have to to depth first search, breadth first search and stuff like that.
I've managed to work on that, but the final problem is to find all the sizes of paths between city "A" the origin and "B", the destination. I was able to work on it with Prolog, but now LISP is giving me headaches :S
Let me paste my code to show you guys how I'm working (:
Btw, the code is in portuguese, so I 'll add some english comments on it (:
Sorry by posting the whole code, maybe some of these function will help me to solve the problem.
Thanks in advance!
Jean
I'm a student and I'm having a few problems with my LISP work.
Well, I have to work on a graph that contains the connections between cities, and I have to to depth first search, breadth first search and stuff like that.
I've managed to work on that, but the final problem is to find all the sizes of paths between city "A" the origin and "B", the destination. I was able to work on it with Prolog, but now LISP is giving me headaches :S
Let me paste my code to show you guys how I'm working (:
Btw, the code is in portuguese, so I 'll add some english comments on it (:
Code: Select all
(defparameter visitados nil) ;; retorno de funcoes (profundidade e largura)
(defparameter flagEncontrou nil)
(defparameter pilha nil)
(defparameter fila nil)
(defparameter org nil)
(defparameter retorno nil)
(defparameter count 0)
(defparameter distancias nil)
;;DEFINITION OF THE CITIES
(defparameter capitais '(rio_branco
maceio
macapa
manaus
salvador
fortaleza
brasilia
vitoria
goiania
sao_luis
cuiaba
campo_grande
belo_horizonte
belem
joao_pessoa
curitiba
recife
teresina
rio_de_janeiro
natal
porto_alegre
porto_velho
boa_vista
florianopolis
sao_paulo
aracaju
palmas
)
)
;;DEFINITION OF THE LIST OF CONNECTIONS
( defparameter *grafo* '(
( porto_alegre florianopolis )
( florianopolis curitiba )
( florianopolis porto_alegre )
( curitiba sao_paulo )
( curitiba campo_grande )
( curitiba florianopolis )
( sao_paulo campo_grande )
( sao_paulo belo_horizonte )
( sao_paulo rio_de_janeiro )
( sao_paulo curitiba )
( campo_grande cuiaba )
( campo_grande goiania )
( campo_grande belo_horizonte )
( campo_grande sao_paulo )
( campo_grande curitiba )
( rio_de_janeiro belo_horizonte )
( rio_de_janeiro vitoria )
( rio_de_janeiro sao_paulo )
( belo_horizonte goiania )
( belo_horizonte vitoria )
( belo_horizonte salvador )
( belo_horizonte sao_paulo )
( belo_horizonte distrito_federal )
( belo_horizonte rio_de_janeiro )
( belo_horizonte campo_grande )
( vitoria salvador )
( vitoria rio_de_janeiro )
( vitoria belo_horizonte )
( goiania campo_grande )
( goiania belo_horizonte )
( goiania distrito_federal )
( goiania cuiaba )
( goiania palmas )
( goiania salvador )
( distrito_federal goiania )
( distrito_federal salvador )
( salvador vitoria )
( salvador belo_horizonte )
( salvador aracaju )
( salvador maceio )
( salvador recife )
( salvador teresina )
( salvador palmas )
( salvador distrito_federal )
( aracaju salvador )
( aracaju maceio )
( maceio aracaju )
( maceio salvador )
( maceio recife )
( recife salvador )
( recife maceio )
( recife teresina )
( recife fortaleza )
( recife joao_pessoa )
( cuiaba campo_grande )
( cuiaba goiania )
( cuiaba porto_velho )
( cuiaba manaus )
( cuiaba belem )
( cuiaba palmas )
( porto_velho cuiaba )
( porto_velho rio_branco )
( porto_velho manaus )
( rio_branco porto_velho )
( rio_branco manaus )
( manaus rio_branco )
( manaus porto_velho )
( manaus boa_vista )
( manaus belem )
( manaus cuiaba )
( boa_vista manaus )
( boa_vista belem )
( belem manaus )
( belem boa_vista )
( belem macapa )
( belem cuiaba )
( belem palmas )
( belem sao_luis )
( macapa belem )
( palmas cuiaba )
( palmas goiania )
( palmas belem )
( palmas salvador )
( palmas sao_luis )
( palmas teresina )
( sao_luis belem )
( sao_luis palmas )
( sao_luis teresina )
( teresina sao_luis )
( teresina palmas )
( teresina salvador )
( teresina recife )
( teresina fortaleza )
( fortaleza teresina )
( fortaleza recife )
( fortaleza natal )
( fortaleza joao_pessoa )
( natal joao_pessoa )
( natal fortaleza )
( joao_pessoa natal )
( joao_pessoa fortaleza )
( joao_pessoa recife )
)
)
;;FUNCTION THAT GIVES ME A LIST WITH ALL CITIES LINKED with "vertice"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; FUNCAO QUE RETORNA LISTA COM TODOS OS ADJACENTES ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun adjacentes (vertice)
(let (adj)
(dolist (g *grafo*)
(if (equal (car g) vertice)
(if (not( member (cadr g) adj))
(setq adj (append adj (list (cadr g))))
)
)
(if (equal (cadr g) vertice)
(if (not( member (car g) adj))
(setq adj (append adj (list (car g))))
)
)
)
adj
)
)
;;FIRST DEPTH SEARCH
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; CHAMADA DA FUNCAO DE PROFUNDIDADE ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun profundidade(origem destino)
(if (not (member origem capitais)) ;;se nao for capital
(print Origem nao encontrado na lista de capitais ) ;; erro
(if (not (member destino capitais)) ;;else if-> verifica destino
(print Destino nao encontrado na lista de capitais ) ;;se nao for capital -> erro
(progn
(setq visitados nil)
(setq flagEncontrou nil)
(profundidadeRec origem destino)
)
)
)
)
;;RECURSIVE CALL
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; FUNCAO RECURSIVA DE PROFUNDIDADE ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun profundidadeRec(origem destino)
(let ((ite))
(if(equal origem destino)
(progn
(setq flagEncontrou T)
(setq visitados (append visitados (list destino)))
)
(if(not (member origem visitados))
(progn
(setq visitados(append visitados (list origem)))
(dolist (ite (adjacentes origem))
(if (equal flagEncontrou T)
(return)
(profundidadeRec ite destino)
)
)
)
)
)
)
visitados
)
;; BREADTH FIRST SEARCH
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; CHAMADA DE FUNCAO DE LARGURA ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun largura (origem destino)
(if (not (member origem capitais))
(print 'Origem 'nao 'mapeada')
(if (not (member destino capitais))
(print 'Destino 'nao 'mapeado )
; else do if
(progn
(setq flagEncontrou nil)
(setq fila nil)
(setq fila (list origem))
(setq visitados nil)
(larguraRec fila destino)
visitados
)
)
)
)
;;RECURSIVE CALL
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; FUNCAO RECURSIVA DE LARGURA ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun larguraRec(fila destino)
(let((p))
(if (equal (car fila) nil)
(print 'Erro 'na 'busca 'em 'largura )
)
(setq p (car fila))
(setq fila (cdr fila))
(if (equal p destino)
(progn
(setq flagEncontrou T)
(setq visitados (append visitados (list destino)))
)
)
(if (not (member p visitados))
(progn
(setq visitados(append visitados (list p)))
(dolist (a (adjacentes p))
(if (not (member a fila) )
(if(not( member a visitados))
(progn
(setq fila(append fila (list a)))
)
)
)
)
(if (equal flagEncontrou T)
(return)
)
(larguraRec fila destino)
)
)
)
)
;;FUNCTION THAT GIVES ME A LIST WITH ALL THE NODES LINKED WITH A CERTAIN DISTANCE (distancia) FROM THE NODE (origem)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; FUNCAO QUE RETORNA NOS A UMA DISTANCIA ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun distancia(origem tamanho)
(if (not (member origem capitais))
(print 'Origem 'nao 'encontrado 'na 'lista 'de 'capitais )
(progn
(setq count 0)
(setq visitados nil)
(setq retorno nil)
(setq org origem)
(setq visitados(append visitados (list origem)))
(distanciaRec origem tamanho)
retorno
)
)
)
;;RECURSIVE CALL
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; NOS A UMA DISTANCIA RECURSIVO ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun distanciaRec(origem tamanho)
(if (= tamanho 0)
(print 'Tamanho 'inválido )
)
(dolist (ite (adjacentes origem))
(if ( = count (- tamanho 1))
(progn
(if (not (member ite retorno))
(progn
(if (not(equal ite org))
(setq retorno(append retorno(list ite)))
)
)
)
)
(if (< count (- tamanho 1))
(progn
(if (not (member ite visitados))
(progn
(setq count (+ count 1))
(distanciaRec ite tamanho)
(setq count (- count 1))
)
)
)
)
)
)
)
;;5) (Valor 3.0 Pontos) Implemente uma função que retorne as distâncias possÃveis entre dois nós do grafo.
;; Note que pode haver mais de uma distância em função dos vários caminhos possÃveis entre os nós.
;;THE PROBLEM I'M TRYING TO SOLVE BUT I KEEP ON GETTIN' NIL
;;;;;;;;;;;;;;;;;;;;;;;;;;
;; DISTANCIAS POSSIVEIS ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun distanciasPossiveis(origem destino)
(if (not (member origem capitais)) ;;se nao for capital
(print 'Origem 'nao 'encontrado 'na 'lista 'de 'capitais ) ;; erro
(if (not (member destino capitais)) ;;else if-> verifica destino
(print 'Destino 'nao 'encontrado 'na 'lista 'de 'capitais ) ;;se nao for capital -> erro
(progn
(setq visitados nil)
(setq flagEncontrou nil)
(setq distancias nil)
(distanciasPossiveisRec origem destino)
(setq distancias (- distancias 1))
distancias
)
)
)
)
;;RECURSIVE CALL
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; FUNCAO RECURSIVA DE DISTANCIAS POSSIVEIS ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun distanciasPossiveisRec(origem destino)
(let ((ite nil))
(print 'oi)
(if(equal origem destino)
(progn
(setq flagEncontrou T)
(setq visitados (cdr visitados))
(print 'incluiu 'distancia)
(setq distancias (append distancias (list (list-length visitados))))
distancias
)
(if(not (member origem visitados))
(progn
(setq visitados(append visitados (list origem)))
(dolist (ite (adjacentes origem))
(if (equal flagEncontrou T)
(progn
(profundidadeRec ite destino)
(setq visitados (cdr visitados))
(setq flagEncontrou nil)
)
(return)
)
)
)
)
)
)
distancias
)
Thanks in advance!
Jean