%COMPUTEEXACTMARGINALSBP Runs exact inference and returns the marginals
%over all the variables (if isMax == 0) or the max-marginals (if isMax == 1).
%
%   M = COMPUTEEXACTMARGINALSBP(F, E, isMax) takes a list of factors F,
%   evidence E, and a flag isMax, runs exact inference and returns the
%   final marginals for the variables in the network. If isMax is 1, then
%   it runs exact MAP inference, otherwise exact inference (sum-prod).
%   It returns an array of size equal to the number of variables in the
%   network where M(i) represents the ith variable and M(i).val represents
%   the marginals of the ith variable.
%
% Copyright (C) Daphne Koller, Stanford University, 2012


function M = ComputeExactMarginalsBP(F, E, isMax)

% initialization
% you should set it to the correct value in your code
M = [];

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% YOUR CODE HERE
%
% Implement Exact and MAP Inference.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cardVars = [];

for j = 1:length(F)
  for k = 1:length(F(j).var)
    cardVars(F(j).var(k)) = F(j).card(k);
  endfor
endfor

P = CreateCliqueTree(F, E);
P = CliqueTreeCalibrate(P, isMax);

for i = 1:length(cardVars)
  for k = 1:length(P.cliqueList)
    if ismember(i, P.cliqueList(k).var)
      vars = setdiff(P.cliqueList(k).var, [i]);
      if isMax == 0
        Fmarg = FactorMarginalization(P.cliqueList(k), vars);
        M(i,1).var = i;
        M(i,1).card = cardVars(i);
        M(i,1).val = Fmarg.val / sum(Fmarg.val);
      else
        Fmarg = FactorMaxMarginalization(P.cliqueList(k), vars);
        M(i,1).var = i;
        M(i,1).card = cardVars(i);
        M(i,1).val = Fmarg.val;
      endif
    endif
  endfor

end
