connected graph. First we pick up a node U whose probability PG ( u ) is what we seek. We construct a tree G 7 with the root node U from G , by letting other nodes dangling from U .

Figure 14 shows how G1 is transformed to a tree when we select node B as the root node.

![0_image_0.png](0_image_0.png)

Then we examine each node in G 7 one by one. We add for each node X in the graph a corresponding clause to DBGr whose purpose is to visit all nodes connected to X except the one that calls X. Suppose we started from the root node U 1 in Figure 15 where evidence u is given, and have generated clause (24). Now we proceed to an inner node X ( U 1 calls X). In the original graph G, X has parent nodes { U 1 , U 2 , U 3 } and child nodes { V 1 , V 2 }. U 3 is a topmost node in G.

![0_image_1.png](0_image_1.png)

Tree Gr For node X in Figure 15, we add clause (25). When it is called from the parent node U 1 with U 1 being ground, we first generate possible values of U 2 by calling val U 2 (U 2 ),
and then call call_X_U2(U2) to visit all nodes connected to X through U2. U3 is similary treated. After visiting all nodes in G connecting to X through the parent nodes U 2 and U 3 (nodes connected to U 1 have already been visited), the value of random variable X is determined by sampling the msw atom jointly indexed by 'X' and the values of U 1 , U 2 and