Graph problem

Discussion of Common Lisp
Post Reply
jaycwb
Posts: 1
Joined: Wed Nov 23, 2011 12:16 pm

Graph problem

Post by jaycwb » 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 (:

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
)

Sorry by posting the whole code, maybe some of these function will help me to solve the problem.

Thanks in advance!

Jean

smithzv
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: Graph problem

Post by smithzv » Tue Nov 29, 2011 4:57 pm

This seems a bit old, but it is unanswered so I guess I'll try to point you in some direction. I have not bothered to look at your code, but if you have something that can perform a depth first search or a breadth first search there is not much more to save the path lengths. All you need to do is save what depth you are on. In the DFS this is extremely simple, just pass an extra parameter to the function that marks the length you have searched so far. Then, in your base case store the value. I'll assume this is what is tripping you up probably because you are trying to pass the result up the call stack. The simplest thing to do is to step outside the recursion and just push it onto a special variable. A similar approach can be performed for breadth first search. A common CL idiom is to make a function that provides an external interface and sets up an execution environment and then calls a worker function (typically with the same name but preceded with a %). The interface function can bind a special variable to nil for you and return the modified value as the result.

Post Reply