Open kenneth-lee-ch opened 5 months ago
I found a recursive behavior in is_dconnected_to
. Suppose we have the following graph D
:
X4->X1 o-o X2<->X5 ; X4->X2
If you call is_dconnected_to(X1, X5, [], D)
, this will make the function to loop forever.
I currently add a list prevent_recursive_ls
to the function is_dconnected_to
to bypass the pair of edge and node that have been previously visited as a workaround to mitigate the issue as shown below:
def is_dconnected_to(node1: Node, node2: Node, z: List[Node], graph: Graph):
if node1 == node2:
return True
edgenode_deque = deque([])
prevent_recursive_ls = [] # MODIFIED HERE
for edge in graph.get_node_edges(node1):
if edge.get_distal_node(node1) == node2:
return True
edgenode_deque.append((edge, node1))
while len(edgenode_deque) > 0:
edge, node_a = edgenode_deque.pop()
node_b = edge.get_distal_node(node_a)
for edge2 in graph.get_node_edges(node_b):
node_c = edge2.get_distal_node(node_b)
# node_a - node_b - node_c
if node_c == node_a:
continue
if reachable(edge, edge2, node_a, z, graph):
if node_c == node2:
return True
else:
if (edge2, node_b) not in prevent_recursive_ls: # MODIFIED HERE
edgenode_deque.append((edge2, node_b))
prevent_recursive_ls.append((edge2, node_b)) # MODIFIED HERE
return False
This is interesting, if I may interject. First of all, this isn't a legal PAG; the tail endpoints at X4 shouldn't be there in a PAG, or at least not both of them, so maybe this was obtained using background knowledge...? Second, the recursion error doesn't occur in Tetrad, even though it's also using a reachability method. Third, for a latent variable model, the right test is m-separation, not d-separation, but you should laugh at anyone who says that since they are the same algorithm (just differently interpreted).
I have the following
GeneralGraph()
object namedD
with the following adjacency matrix (fromD.graph
) and I useis_dseparated_from
to check whether nodes0
and2
are d-separated given an empty set. The functionis_dseparated_from
seems to get stuck somewhere and it never returns. Is this expected?