Матрица смежности / Флойд / Warshall in lisp - PullRequest
Новая
       65

Матрица смежности / Флойд / Warshall in lisp

3 голосов
/ 25 мая 2011

Очевидно, мой учитель считает, что даже если у нас нет времени на то, чтобы учить что-либо (и не хватает примеров), мы должны двигаться дальше, поэтому мне теперь нужно знать, как сделать алгоритмы Флойда-Варшалла и Варшалла в надежном виде.

Как и в случае с прологом, моя задача - сгенерировать матрицу смежности из графа, в этом случае это будет список списков, например ::10000 

((A B) (A C) (A D) (B C) (C D))

Это должно сгенерировать: 

((0 1 1 1) (1 0 1 9) (1 1 0 1) (1 9 1 0))

У меня есть это: 

(defun floyd(graph)
    (setf l (length graph)) 
    (setf mat (matrix l graph))
)

(defun matrix(l graph)
    (setf matrix (make-array (list l l)))
    (dotimes (i l)
        (dotimes (j l)
            (if (= i j)
                (setf (aref matrix i j) 0)
                (setf (aref matrix i j) ???)
            )
        )
    )
    matrix
)

Любая помощь очень ценится.

Кроме того, и не по теме: если бы я мог решить свой собственный вопрос, должен ли я ответить себе ради ответа на вопрос?

1 Ответ

1 голос
/ 01 июля 2011

Я преобразовал псевдокод Википедии в Common Lisp с объявлениями типов. Объявление типа возврата нестандартно, я использовал SBCL. Я думаю, что это не будет работать, но это может дать вам представление о том, как должен выглядеть код на Лиспе. 

(defparameter *n* 5)
(defparameter *path*
  (make-array (list *n* *n*)
          :element-type '(unsigned-byte 64)))


(defun floyd-warshall (path)
  (declare (type (simple-array (unsigned-byte 64) 2) path)
       (values (simple-array (unsigned-byte 64) 2) &optional))
  (destructuring-bind (y x) (array-dimensions path)
    (unless (= y x)
      (break "I expect a square matrix, not ~ax~a." x y))
    (macrolet ((p (j i)
         `(aref path ,j ,i)))
      (dotimes (k x)
    (dotimes (i x)
      (dotimes (j x)
        (setf (p j i)
          (min (p j i) (+ (p k i)
                  (p j k)))))))))
  path)

Примечание 1: Если у вас есть объемное 3D изображение, у вас должны быть такие индексы (aref vol k j i), где k указывает z, j y и i направление x. Сюда в SBCL и, предположительно, во всех других реализациях срезы являются последовательными в памяти.

Примечание 2: macrolet может сэкономить много печатать. Также посмотрите на реализацию массивов with в этой прекрасной библиотеке: git: //github.com/nikodemus/raylisp.git/objects/box.lisp

...