For computing multiple marginals efficiently in the *Shenoy-Shafer *architecture, a binary join tree has been proposed in [1].

For a given *valuation network* , if we want to compute marginal for a subset , we can use the *Fusion algorithm * .

*Fusion algorithm: Suppose is a VN where is a valuation for , and suppose and satisfy Axioms A1-A3 [1] . Let denote . Suppose , and suppose is a sequence of variables in . Then*

* *

With this fusion Algorithm, we can compute the marginal of the joint valuation one by one. It is obviously inefficient that it involves much repetition of effort. Then they use a join tree with message passing to mimic the fusion algorithm.

A join tree is a tree whose nodes are subsets of such that if a variable is in two distinct nodes, then it is in every node on the path between the two nodes. In [1], a procedure is given out. I follow the algorithm and implement it with Python. The input and are given by the Chest clinic example in [1]. It is worth to noting that the deletion sequence is which is derived by the one-step lookahead heuristic approach. Below is the source code.

```
import JoinTree as jt
variables = set({'A','T','E','X','D','L','S','B'})
valuations = []
valuations.append(jt.Valuation(frozenset({'A'})))
valuations.append(jt.Valuation(frozenset({'A'}),observed=True))
valuations.append(jt.Valuation(frozenset({'S'})))
valuations.append(jt.Valuation(frozenset({'A','T'})))
valuations.append(jt.Valuation(frozenset({'S','L'})))
valuations.append(jt.Valuation(frozenset({'S','B'})))
valuations.append(jt.Valuation(frozenset({'T','L','E'})))
valuations.append(jt.Valuation(frozenset({'E','X'})))
valuations.append(jt.Valuation(frozenset({'E','B','D'})))
valuations.append(jt.Valuation(frozenset({'D'}),observed=True))
subsets = set()
for i in valuations:
subsets.add(i.variables)
def get_superset(superset,t):
for i in superset:
if t in i:
yield i
def construct( variables, subsets,object):
nodes = set()
edges = set()
variables.difference_update(object)
heuristic_count = ['E','L','B','D','S','A','X']
while(len(subsets)>1):
picked=heuristic_count.pop()
s = reduce(frozenset .union,get_superset(subsets,picked))
s_all = set([i for i in get_superset(subsets,picked)])
#update nodes
nodes.update(s_all)
s_set = set()
s_set.add(s)
nodes.update(s_set)
temp = set()
temp.add(picked)
_s=set(s)
s_no_y = set() #{s-{Y}}
s_no_y.add(frozenset(_s.difference(temp)))
nodes.update(s_no_y)
#update edge
u_s = subsets.difference(s_set)
temp = set([ (i,s) for i in get_superset(u_s,picked) ])
single = s.difference(set(picked))
edges.update(temp)
edges.update(set([(s,single)]))
variables.difference_update(set(picked))
subsets.difference_update(s_all)
subsets.update(s_no_y)
nodes.update(subsets)
return nodes,edges
nodes, edges=construct(variables,subsets,'T')
```

By using the visualization tool GraphViz, you can get the graph:

**You can also download the source code from here**

[1] P. P. Shenoy, “Binary join trees for computing marginals in the Shenoy-Shafer architecture,” Int. J. Approx. Reason., vol. 17, no. 2–3, pp. 239–263, Aug. 1997.