Estou criando um programa lisp para encontrar um caminho acíclico em um gráfico não direcionado e retornar esse caminho ao usuário. O caminho não precisa necessariamente ser o caminho mais curto. Meu código completo é o seguinte:
(defvar graph '((A B C)
(B A C)
(C A B D)
(D C)
))
(defun getneighbours (graph node) ;Gets neighbors of the given node.
(if (assoc node graph)
(cdr (assoc node graph))
'()
)
)
(defun acyclicpath (graph start goal)
(setq visited '()) ;Reset the returnpath and visited variables for the next search.
(setq returnpath '())
(if (dfswithpath graph start goal) ;Path found reverse path and return.
(reverse 'returnpath)
)
nil
)
(defun dfswithpath (graph node goal)
(if (equal node goal) ;Goal reached return true.
(push node returnpath)
t
)
(push node visited) ;Update visited list.
(dolist (neighbour (getneighbours graph node)) ;Call dfs on each neighbour of node if not already visited.
(if (not (member neighbour visited))
(if (dfswithpath graph neighbour goal)
(push node returnpath)
t
)
)
)
nil ;No path found
)
(print (acyclicpath graph 'A 'C))
A execução desse código resulta em um valor nulo sendo sempre retornado pela função dfswithpath. Limitei o problema à chamada recursiva dfswithpath na função dolist. Parece que ele nunca resolve t e, portanto, a função push aninhada nunca é chamada. No entanto, não consigo entender por que esse é o caso.