#|
Given: single query variable X
       vector of evidence variables/values E/e
       Bayes net
Produce: conditional distribution P(X|E=e)

(It is assumed that X is not one of the evidence variables.)

Pseudo-code (based on Figure 14.9):

function ENUMERATION-ASK(X,E/e,bn) returns a distribution over X
  inputs: X, a list of query variables
          E/e, a list of observed variable/value pairs
          bn, a Bayes net with variables X + E + Y (Y = hidden vars)

  Q(X) <- a distribution over X, initially empty
  for each combination of values x for X do
    augment E/e with variable/value pairs X/x
    Q(x_i) <- ENUMERATE-ALL(SORTED-VARS[bn],e)
  return NORMALIZE(Q(X))

function ENUMERATE-ALL(vars,E/e) returns a real number
  if EMPTY?(vars) then return 1.0
  Y <- FIRST(vars)
  if Y has value y in E/e
    then return P(Y=y|parents(Y)) * ENUMERATE-ALL(REST(vars),E/e)
    else return sum_y P(Y=y|parents(Y)) * ENUMERATE-ALL(REST(vars),E/e_y),
         where E/e_y is E/e extended with Y=y

In the above, SORTED-VARS[bn] lists the variables in an order for which
parents(Y) occur earlier than Y for all variables Y (i.e., it performs
a topological sort).  This is not discussed in the book, but it clearly
seems necessary in order to guarantee that when determining the probability
for a variable values have already been assigned for its parents.
|#

;; Main program.  Assumes that query-var is not among the evidence
;; variables (but it could be modified easily to handle this possibility).
;; It could also be modified (with somewhat more effort) to return a
;; joint conditional distribution given a list of query variables.
;; 
;; The "evidence" input is assumed to be a list of variable/value pairs
;; (2-element lists, not dotted pairs).
;;
;; The returned value has the form ((val-1 prob-1) ... (val-n prob-1)),
;; where n is the number of different values the query variable can take on.
;;
#| Sample call:
(query-by-enumeration 'Burglary '((JohnCalls true) (MaryCalls true))
		      *burglar-alarm-net*)
|#

(defun query-by-enumeration (query-var evidence bn)
  (let* ((vals (get-values query-var bn))
	 (sorted-vars (topological-sort-vars bn))
	 (distribution nil)
	 )
    (dolist (val vals (normalize (reverse distribution)))
      (push (list val
		  (enumerate-all sorted-vars
				 (cons (list query-var val) evidence)
				 bn))
	    distribution))
    ))

(defun enumerate-all (vars vars-with-vals bn)
  (if (null vars)
      1.0
      (let* ((var (first vars))
	     (val (second (assoc var vars-with-vals))))
	(if val
	    (* (prob-given-parents var val vars-with-vals bn)
	       (enumerate-all (rest vars) vars-with-vals bn))
	    (let ((sum 0.0)
		  (vals (get-values var bn)))
	      (dolist (val vals sum)
		(let ((new-vars-vals (cons (list var val) vars-with-vals)))
		  (incf sum (* (prob-given-parents var val vars-with-vals bn)
			       (enumerate-all (rest vars)
					      new-vars-vals
					      bn))))))
	    ))))