How to find the longest path between two nodes in Lisp?

Question

I need to program a Lisp function that finds the longest path between two nodes, without revisiting any nodes. Though, if the start and end node are the same, this node can be revisited. The function needs to be both recursive and depth-first-search.

I've been trying to get at this for hours, and cannot come up with a solution. I know the general outline of the function, but cannot program it correctly. In some code and mostly pseudo-code:

(defun longest-path (start end net &optional (current-path nil))  
    (cond ((and (eql start end)
                (not (null current-path)))
          (list start))
          (t
           (find neighbors of start/node)
           (remove any previously traveled neighbors to avoid loop)
           (call longest-path on these neighbors)
           (check to see which of these correct paths is longest))))

The net looks something like '((a b) (b c)) , where the first item is the node, and everything else is its neighbors (e.g. node a has neighbor b, node b has neighbor c).

Yes, this is for homework, so if you don't feel comfortable posting a solution, or any part of it, don't. I'm just new to Lisp and would like some tips/help to get a decent start.

Thanks

Edit: Well, the most I could get was this:

(defun longest-path (start end net &optional (current-path nil))
  (cond ((and (eql start end)
              (not (null current-path)))
         (list start))
        (t
         (push start current-path)
         (let ((neighbors (cdr (assoc start net))))
           (let ((new-neighbors (set-difference neighbors current-path)))
             (let ((paths (mapcar #'(lambda (node)
                                      (longest-path node end net current-path))
                            new-neighbors)))
               (let ((longest (longest paths)))
                 (if longest
                     (cons start longest)
                   nil))))))))


(defun longest (lst)
  (do ((l lst (cdr l))
       (r nil (if (> (length (car l)) (length r))
                  (car l)
                r)))
      ((null l) r)))

It produces correct solutions, except when the start and end node are the same. I can't figure out how to perform a search even when they're the same.

Commemorate

Answer 1

I have remembered this algorithm from Paul Graham's book: Ansi Common Lisp. Here is the link of the solution of one exercise from book. This should help you.

Solution

Cordi

Answer 2

I think you need to check three cases:

1. end reached -> return this path
2. no more choices -> return nil
3. find longest path of neighbors

Code outline:

(defun longest-path (node end-node net current-path)
  (cond ((eql node end-node)
         (or current-path (list node end-node)))
        ((null (node-neighbors node net))
         ())
        (t
         (let* ((neighbors (node-neighbors node net))
                (not-visited-neighbors (set-difference neighbors current-path))
                (paths (mapcar (lambda (next-node)
                                 (longest-path next-node end-node net
                                               (cons node current-path)))
                               not-visited-neighbors)))
           (first (sort paths #'> :key #'length))))))

Salpinx

Hi, thanks for the help. I tried your code, but did not get the correct solutions. For example, if I tried (longest-path 'a 'c '((a b) (b c)) nil) I'd get (B A). Instead, I should get (A B C). – Commemorate