# Junction Tree Algorithm

 Algorithm 3 The sum-product algorithm Input: an undirected, tree-structured graphical model $\mathcal{X}$ with cliques $\mathcal{C}$ $\{$the cliques are simply edges in this case$\}$1: define $m_{A\to B}\left(\mathcal{x}_{A\cap B}\right)$ to be the “message” from an edge $A$ to an adjacent edge $B$ {for example if $A=(a,b)$ and $B=(b,c)$ then we have $m_{(a,b) \to (b,c)}(\mathcal{x}_b)$}2: while there exist adjacent edges $A,B \in \mathcal{C}$ for which $m_{A\to B}$ has not been computed do 3: find some $A\in \mathcal{C}$ such that $m_{C \to B}$ has been computed for every neighbor $C \in \Gamma(A)$ except $B\; \{\Gamma(A)$ returns the edges neighboring $A$; initially the condition is satisfied by all leaf-edges$\}$ 4: $m_{A\to B}\left(\mathcal{x}_{A \cap B}\right):=\sum_{\mathcal{x}_{A / B}}\{\Psi_A(\mathcal{x}_A)\prod_{C\in A \Gamma (A) / B}m_{C \to A} \left(\mathcal{x}_{A\cap B} \right)\}$ 5: end while 6: for $A \in \mathcal{C}'$ do 7: $marginal_A(\mathcal{x_A}):=\Psi_A(\mathcal{x}_A)\prod_{C\in \Gamma(A)}m_{C \to A} \left(\mathcal{x}_{A\cap C}\right)$ 8: end for