longest path, without node and route structures

gistfile1.lisp

; https://github.com/logicchains/LPATHBench/blob/master/writeup.md
 

(defun parse-line (line &aux (pos 0) n)
  (declare (ignorable n))
  (loop repeat 3
        collect (multiple-value-setq (n pos)
                    (parse-integer line :start pos :junk-allowed t))))
 
(defparameter *file* "agraph")
 
(defun read-places ()
  (with-open-file (stream *file*)
    (let ((num-lines (parse-integer (read-line stream nil))))
      (values (loop for line = (read-line stream nil nil)
                    while line
                    collect (parse-line line))
              num-lines))))
 
(defun parse-places ()
  (multiple-value-bind (place-data num-nodes)
      (read-places)
    (let ((costs (make-array num-nodes :initial-element nil))
          (dests (make-array num-nodes :initial-element nil)))
      (loop for (node-id neighbour dist) in place-data do
            (push dist      (svref costs node-id))
            (push neighbour (svref dests node-id)))
      (values costs dests))))
 
(declaim (ftype (function (simple-vector simple-vector fixnum simple-vector) fixnum)
                get-longest-path))

(defun get-longest-path (costs dests node-id visited &aux (max 0))
  (declare (optimize (speed 3) (space 0) (debug 0) (safety 0)
                     (compilation-speed 0)
                     #+lispworks (fixnum-safety 0))
           (fixnum max))
  (setf (svref visited node-id) t)
  (setf max (loop for dest fixnum in (svref dests node-id)
                  and cost fixnum in (svref costs node-id)
                  unless (svref visited dest)
                  maximize (+ (the fixnum cost)
                              (the fixnum (get-longest-path costs dests dest visited)))
                  #+lispworks fixnum))
  (setf (svref visited node-id) nil)
  max)
 
(defun run ()
  (multiple-value-bind (costs dests)
      (parse-places)
    (let* ((visited  (make-array (length costs) :initial-element nil))
           (start    (get-internal-real-time))
           (len      (get-longest-path costs dests 0 visited))
           (end      (get-internal-real-time))
           (duration (truncate (* 1000 (- end start))
                               internal-time-units-per-second)))
      (format t "~d LANGUAGE Lisp ~d ~%" len duration))))

#+sbcl 
(sb-ext:save-lisp-and-die "lisp" :toplevel #'run :executable t)