The number and type of neighboring configurations that can be obtained from the inclusion in the current RPDAG of an edge between and can be determined from the parameters above. The resultant casuistry may be reduced to seven states, which we have labeled from to . In order to facilitate its description, we shall use the decision tree shown in Figure 106.
In this tree, the lower box of each non-terminal vertex contains a test (about the number of parents or the number of neighbors of nodes and ). The lower box of each terminal vertex contains the label of the state resulting from following the path from the root to that terminal vertex. The description of each state (i.e. the different neighboring configurations that can be obtained in this case) can be found in Table 1. The upper boxes of all the vertices in the tree show the restrictions imposed on each intermediate or terminal state. For example, state B corresponds to a situation where both nodes and do not have neighbors and at least one of them has some parent. Although the tree has seven different states, there are only five truly different states, since states D and E, and states F and G are symmetrical.
In Table 1, each row corresponds to a state: the first column contains the labels of the states; the second column displays the total number of neighboring configurations that can be obtained for each state; the third column shows the different types of edges that, for each state, can be added to the current configuration; columns four, five and six will be discussed later.
Using the example in Figure 8, we shall explain the use of the decision tree as well as the instantiation of the information in Table 1. Following the decision tree, at level 1 (the root vertex), the test is false since has two neighbors. At level 2, the test is also false as has one parent. At level 3 the test is true, since has no neighbor. At level 4 we reach a terminal vertex. Our current configuration therefore corresponds to state F. Then, by examining state F in Table 1, we can confirm that we reach four different configurations (): , without new h-h patterns, and two which produce new h-h patterns. So, these are the only structures that our algorithm must evaluate when considering the inclusion of the candidate edge . In Figure 14, we show an example for each of the five non-symmetrical states (once again, these examples only display the part of the RPDAGs corresponding to the neighborhood of the nodes and ).
We therefore have a systematic way to explore all the neighboring configurations which result from adding an edge. However, it will sometimes be necessary to perform some additional steps since the configurations obtained must be RPDAGs: