;; Bibliothèque pour les Graphes non modifiables ;; pour le TCA 101 2002/2003 #| Tant qu'on se limite à des graphes non modifiables i.e: où on ne peut ajouter ni sommet ni arête, il est possible d'utiliser la même représentation physique pour le type orienté arêtes et pour le type orienté sommets. Les primitives pour ces deux types définies dans le livre ont alors toutes une complexité constante. |# ;; primitives pour le type orienté arêtes (defgeneric nb-nodes (graph)) (defgeneric nb-edges ((G graph))) (defgeneric node ((G graph) (i integer))) (defgeneric edge ((G graph) (i integer))) (defgeneric edge-end ((e edge) (i integer))) (defgeneric mark-node ((n node))) (defgeneric unmark-node ((n node))) (defgeneric node-marked ((n node))) (defgeneric mark-edge ((e edge))) (defgeneric unmark-edge ((e edge))) (defgeneric edge-marked((e edge))) ;;------------------------------------------ ;; primitives supplémentaires pour le type ;; orienté sommets (defgeneric nb-edges ((n node))) (defgeneric edge ((n node) (i integer))) (defgeneric follow-edge ((n node) (e edge))) ;;------------------------------------------ ;; classes suffisantes pour le type ;; orienté arêtes (defclass graph () ((nodes :initarg :nodes :accessor graph-nodes) ;:read-only t) (edges :initarg :edges :accessor graph-edges))) ;:read-only t))) ;; problème avec le :read-only (defclass edge () ((node0 :type 'node ;;:read-only t :accessor edge-node0 :initarg :node0) (node1 :type 'node ;;:read-only t :accessor edge-node1 :initarg :node1) (marked :type 'boolean :initform nil :accessor edge-marked))) ; O(1) ;; problème avec le :read-only ;;---------------------------------------- ;; classe à ajouter pour que notre type ;; graphe soit aussi orienté sommets (defclass node () ((edges :accessor node-edges :initform nil) (marked :initform nil :accessor node-marked))) ; O(1) ;;---------------------------------------- ;; fonctions... ;; Utilisation du constructeur de graphes: ;; exemples dans graph-data.lisp ;; node + | path*nodes-in-a-path + edge + node * edge + edge ;; | = edge * edge ;; complexité si la valeur de paths n'est pas "n'importe quoi"= ;; N + E + + N*E + E*E ~= max(E*E,N*E) (defun make-graph (nb-nodes paths) (let ((nodes (make-array nb-nodes)) (edges '())) (dotimes (i nb-nodes) (setf (aref nodes i) (make-instance 'node))) (dolist (path paths) (let ((from (pop path))) (dolist (to path) (let ((edge (make-instance 'edge :node0 (aref nodes from) :node1 (aref nodes to)))) (push edge edges) (setf from to))))) (dolist (edge edges) (push edge (node-edges (edge-node0 edge))) (push edge (node-edges (edge-node1 edge)))) (dotimes (i nb-nodes) (setf (node-edges (aref nodes i)) (list-to-array (node-edges (aref nodes i))))) (make-instance 'graph :edges (list-to-array edges) :nodes nodes))) ;; Graphe aléatoire à nb-nodes sommets et nb-edges arêtes. ;; Utile si on veut créer des grands graphes pour ;; montrer les limites d'un algo de complexité ;; élevée. (defun make-random-graph (nb-nodes nb-edges) (let (edges) (dotimes (i nb-edges) (push (list (random nb-nodes) (random nb-nodes)) edges)) (make-graph nb-nodes edges))) ;; O(n) (defun list-to-array (l) (let ((a (make-array (length l))) (i 0)) (dolist (e l) (setf (aref a i) e) (incf i)) a)) ;;---------------------------------------- ;; méthodes... ;; O(1) (defmethod nb-nodes ((G graph)) (car (array-dimensions (graph-nodes G)))) ;; O(1) (defmethod nb-edges ((G graph)) (car (array-dimensions (graph-edges G)))) ;; O(1) (defmethod node ((G graph) (i integer)) (aref (graph-nodes G) i)) ;; O(1) (defmethod edge ((G graph) (i integer)) (aref (graph-edges G) i)) ;; O(1) (defmethod edge-end ((e edge) (i integer)) (cond ((= i 0) (edge-node0 e)) ((= i 1) (edge-node1 e)) (t (error (format nil "~A ~A ~A ~A ~A.~%" "EDGE-END:" "edge number must be" "0 or 1." "You tried" i))))) ;; O(1) (defmethod mark-node ((n node)) (setf (node-marked n) t)) ;; O(1) (defmethod unmark-node ((n node)) (setf (node-marked n) nil)) ;; O(1) (defmethod mark-edge ((e edge)) (setf (edge-marked e) t)) ;; O(1) (defmethod unmark-edge ((e edge)) (setf (edge-marked e) nil)) ;;-------------------------------------- ;; O(1) (defmethod nb-edges ((n node)) (car (array-dimensions (node-edges n)))) ;; O(1) (defmethod edge ((n node) (i integer)) (aref (node-edges n) i)) ;; O(1) (defmethod follow-edge ((n node) (e edge)) (if (eq n (edge-node0 e)) (edge-node1 e) (edge-node0 e)))