Adding Edges

The number and type of neighboring configurations that can be obtained from the inclusion in the current RPDAG of an edge between $x$ and $y$ can be determined from the parameters above. The resultant casuistry may be reduced to seven states, which we have labeled from $A$ to $G$. In order to facilitate its description, we shall use the decision tree shown in Figure 10⁶.

Figure 10: The tree of possible states that may result by adding an edge between nodes $x$ and $y$

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 $x$ and $y$). 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 $x$ and $y$ 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.

Table 1: Table of states that may result by adding an edge between nodes $x$ and $y$

State	Number of	Added edges	Directed	Undirected	Completing ?
	configurations		Cycles ?	Cycles ?
A	1	$x$--$y$	No	No	No
B	2	$x\rightarrow y$ $x\leftarrow y$	Yes$^{(1)}$ Yes$^{(2)}$	No No	No No
C	$n_G(x)+n_G(y)+1$	$x$--$y$ $x\rightarrow y\leftarrow z$ $z\rightarrow x\leftarrow y$	No Yes$^{(3)}$ Yes$^{(4)}$	Yes No No	No Yes$^{(3)}$ Yes$^{(4)}$
D	$n_G(y)+1$	$x$--$y$ $x\rightarrow y\leftarrow z$	No No	No No	No Yes$^{(3)}$
E	$n_G(x)+1$	$x$--$y$ $z\rightarrow x\leftarrow y$	No No	No No	No Yes$^{(4)}$
F	$n_G(y)+2$	$x\leftarrow y$ $x\rightarrow y$ $x\rightarrow y\leftarrow z$	No Yes Yes$^{(3)}$	No No No	No Yes Yes$^{(3)}$
G	$n_G(x)+2$	$x\rightarrow y$ $x\leftarrow y$ $z\rightarrow x\leftarrow y$	No Yes Yes$^{(4)}$	No No No	No Yes Yes$^{(4)}$
(1) only if $p_G(x)\neq 0$ and $c_G(y)\neq 0$			(3) only if $n_G(y)\geq 2$
(2) only if $p_G(y)\neq 0$ and $c_G(x)\neq 0$			(4) only if $n_G(x)\geq 2$

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 $y$ has two neighbors. At level 2, the test is also false as $x$ has one parent. At level 3 the test is true, since $x$ 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 ($n_G(y)=2$): $G\cup \{x \leftarrow y\}$, $G\cup \{x \rightarrow y\}$ without new h-h patterns, and two $G\cup \{x \rightarrow y\leftarrow z\}$ 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 $x\mbox{-}y$. 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 $x$ and $y$).

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:

• First, we must maintain the condition 1 ( $p_G(y)\neq 0\Rightarrow n_G(y)=0$). It is therefore necessary to complete the configuration for some of the described states, i.e. some of the links must be converted into arcs. The completing process consists in firing an orientation in cascade, starting from the links $y\mbox{-}t$ such that the arc just introduced is $x\rightarrow y$. Let us consider the situation in Figure 11, where we want to connect the nodes $x$ and $y$, a case corresponding to state D. Among the three possible neighboring configurations, let us suppose that we are testing the one which introduces the h-h pattern $x\rightarrow y\leftarrow z$. The RPDAG obtained from the completing process is also displayed in Figure 11. The sixth column in Table 1 shows which states and neighboring configurations may require the completing process.

Figure 11: Transformation of a configuration after including the pattern $x\rightarrow y\leftarrow z$ and completing

• Secondly, it is possible that some of the neighboring configurations must be rejected, as they give rise to directed or completely undirected cycles (conditions 2 and 3 defining RPDAGs). For example, let us consider the situation displayed in Figure 12, which corresponds to state F. In this case, the configuration obtained after including the arc $x\rightarrow y$ and completing would generate a directed cycle. This configuration must therefore be rejected. The columns four and five in Table 1 show which states and configurations may require a detection of directed or completely undirected cycles, respectively.

Figure 12: Neighboring configuration that gives rise to a directed cycle