;; interval.lisp: LISP code to do interval analysis (constructing so-called
;; "Tarjan intervals") on control-flow graphs (brg 21-Oct-2002)

; Here are two example graphs on which this code works:
(defvar graph
  '((start-node 1)
    (adjacency-alist ((1 (2 6))
		      (2 (3 8))
		      (3 (3 4))
		      (4 (2))
		      (5 (7))
		      (6 (8 5))
		      (7 (6))
		      (8 (9))
		      (9 ())))))

(defvar graph2
  '((start-node 1)
    (adjacency-alist
     ((1 (2))
      (2 (3))
      (3 (4 8))
      (4 (5 9))
      (5 (2 6))
      (6 (7 8))
      (7 ())
      (8 (3))
      (9 (6 8))))))

(defun adjacency-alist (graph)
  (cadr (assoc 'adjacency-alist graph)))

(defun start-node (graph)
  (cadr (assoc 'start-node graph)))

(defun children (n graph)
  (cadr (assoc n (adjacency-alist graph))))

(defun nodes (graph)
  (mapcar #'car (adjacency-alist graph)))

(defun check-node (int n graph)
  ;; If all arcs entering N leave nodes in INT return false; otherwise
  ;; return true. That is, if there is an arc entering N which leaves
  ;; a node that is not in I then return true.
  ;; for each node X in graph
  ;;   for each arc X->Y from X
  ;;     if Y is N and X is not in I
  ;;       then return true
  (let ((found nil))
    (dolist (x (nodes graph))
      (dolist (y (children x graph))
	(when (and (eq y n) (not (member x int)))
	  (setq found t))))
    found))

(defun interval (n graph current-interval)
  (let ((candidates 
	 (remove-if #'(lambda (n) (check-node current-interval n graph))
		    (remove (start-node graph)
			    (remove-if
			     #'(lambda (n) (member n current-interval))
			     (nodes graph))))))
    (if (null candidates)
	current-interval
      (interval n graph (append candidates current-interval)))))

(defun pretty-print-interval (n graph)
  (let ((i nil))
    (format t "computing interval of ~A~%" n)
    (setq i (interval n graph (list n)))
    (format t "interval of ~A is: ~A~%" n i)))

(defun pretty-print-all-intervals (graph)
  (mapcar #'(lambda (n) (pretty-print-interval n graph)) (nodes graph)))

; Here is how to run the program:
; (pretty-print-all-intervals graph2)