of the
cutset 
, we compute a Q-DAG node for 
using the polytree
algorithm and then take the 
-sum of the resulting nodes.
The polytree algorithm is a special case of the clustering algorithm as
shown in
[Shachter, Andersen, SzolovitsShachter
et al.1994]. Therefore, the polytree algorithm can also be modified as
suggested above to compute Q-DAGs. This also means that cutset conditioning can
be easily modified to compute Q-DAGs: for each instantiation of the
cutset , we compute a Q-DAG node for using the polytree
algorithm and then take the -sum of the resulting nodes.
Most algorithms for exact inference in belief networks can be adapted to
generate Q-DAGs. In general, an algorithm must satisfy a key condition
to be adaptable for computing Q-DAGs as we suggested above. The condition is
that the behavior of the algorithm should never depend on the
specific evidence obtained, but should only depend on the variables about which
evidence is collected. That is, whether variable 
is instantiated to value
or value 
should not affect the complexity of
the algorithm. Only whether variable is instantiated or not should matter.
Most belief networks algorithms that we are aware of satisfy this property. The
reason for this seems to be the notion of probabilistic independence on which
these algorithms are based. Specifically, what is read from the topology of a
belief network is a relation 
, stating that variables 
and
are independent given variables 
. That is,
for all instantiations 
of these variables. It is possible,
however, for this not to hold for all instantiations of 
but only for
specific ones. Most standard algorithms we are aware of do not take advantage
of this instantiation-specific notion of independence.[+] Therefore, they cannot attach any computational significance
to the specific value to which a variable is instantiated. This property of
existing algorithms is what makes them easily adaptable to the generation of
Q-DAGs.