adjacency matrix/Floyd/Warshall

[kirby]

Apparently my teacher believes that even if we don't have time to learn stuff (nor enough examples) we should move on, so I now need to know how to make Floyd-Warshall's and Warshall's algorithms in clisp.

My first problem is to generate the adjacency matrix from the graph, in this case it would be a list of lists, e.g.:

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

That should generate:

Code: Select all

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

I've got this:

Code: Select all

(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)

Any help is greatly appreciated.

PS: I've been told I should have been using let instead of setf to declare variables, but I don't know how to use it (I investigated but can't make matrix function work with let ;__;). I hate when there's a class in school and they teach you wrong u__u

[ramarren]

in clisp

The language is called Common Lisp, commonly abbreviated CL. CLISP is a particular implementation of this language. There is a free online book about CL: Practical Common Lisp. It is not that long, especially if you skip things you don't need, and it explains among other things how to use LET properly.

adjacency matrix from the graph

A graph is an abstract object. What it seems you mean is to transform the edge list representation into an adjacency matrix representation. A matrix is a random access data structure, while a list is a serial access, which means you should go through the list one by one setting appropriate matrix cells. Which obviously requires some kind of unique mapping from node names to integers.

[nuntius]

(looks like a couple 9s slipped in for 0s in your adjacency graph)

Here's a code snippet to get you in the right direction.

Code: Select all

(defun symbol-rank (symbol)
  "map a symbol to a number"
  ;; could use many other things like a hash table
  (ecase symbol
    (a 0)
    (b 1)
    (c 2)
    (d 3)))

(defun graph-to-matrix (graph)
  "convert a list of connection pairs into an adjacency matrix"
  ;; currently hard-coding knowledge that the result is 4x4...
  (let ((matrix (make-array (list 4 4) :initial-element 0)))
    (dolist (pair graph)
      (let* ((x (first pair))
             (y (second pair))
             (xr (symbol-rank x))
             (yr (symbol-rank y)))
        ;; a little debug
        (print (list x y xr yr))
        ;; now use that to do something to the matrix
        ))
    matrix))

#| example output:
(graph-to-matrix '((a b) (c d)))

(A B 0 1) 
(C D 2 3) 
#2A((0 0 0 0) (0 0 0 0) (0 0 0 0) (0 0 0 0))
|#

If you actually need the matrix as a list of lists, then I would add another function to convert an actual array structure into the list of lists. array-dimensions is your friend... or you could create the list of lists and index into it using nth.