;; certains algos du livre ;; algorithme 9.1 ;; O(1) (defun ar-degre-moyen (G) (let ((nb-ar (nb-edges G)) (nb-som (nb-nodes G))) (/ (* 2 nb-ar) nb-som))) ;; algorithme 9.2 ;; O(N) (defun som-degre-moyen (G) (let ((nb-som (nb-nodes G)) (accu 0)) (dotimes (i nb-som) (let* ((sommet (node G i)) (degre-sommet (nb-edges sommet))) (incf accu degre-sommet))) (/ accu nb-som))) ;; algorithme 9.5 ;; le s de cet algo est le s' du livre (defun ar-existe-chemin-simple (G ss tt) (when (eq ss tt) (return-from ar-existe-chemin-simple t)) (mark-node ss) (dotimes (i (nb-edges G)) (let* ((e (edge G i)) (s (cond ((eq (edge-end e 0) ss) (edge-end e 1)) ((eq (edge-end e 1) ss) (edge-end e 0))))) (unless (null s) (unless (node-marked s) (when (ar-existe-chemin-simple G s tt) (unmark-node ss) (return-from ar-existe-chemin-simple t)))))) (unmark-node ss) nil) ;; algorithme 9.6 ;; le s de cet algo est le s' du livre (defun som-existe-chemin-simple (G ss tt) (when (eq ss tt) (return-from som-existe-chemin-simple t)) (mark-node ss) (dotimes (i (nb-edges ss)) (let* ((e (edge ss i)) (s (follow-edge ss e))) (unless (node-marked s) (when (som-existe-chemin-simple G s tt) (unmark-node ss) (return-from som-existe-chemin-simple t))))) (unmark-node ss) nil) ;; algorithme 9.8 ;; (defun som-est-connexe (G) (let ((s (node G 0))) (som-mark-all s) (dotimes (i (nb-nodes G)) (let ((s (node G i))) (unless (node-marked s) (return-from som-est-connexe nil)) (unmark-node s))) t)) ;; algorithme 9.9 ;; (defun som-mark-all (s) (unless (node-marked s) (mark-node s) (dotimes (i (nb-edges s)) (let* ((e (edge s i)) (tt (follow-edge s e))) (som-mark-all tt)))))