3.1.12. pywhy_graphs.networkx.is_minimal_m_separator

pywhy_graphs.networkx.is_minimal_m_separator(G, x, y, z, i=None, r=None, directed_edge_name='directed', bidirected_edge_name='bidirected', undirected_edge_name='undirected')

Check if a set ‘z’ is a i-minimal m-separator between ‘x’ and ‘y’.

The function will first check if ‘z’ is a m-separator, and then check if it is minimal. An i-minimal m-separating set is a minimal m-separator that contains i.

This implements the algorithm TESTMINSEP presented in [1] for ancestral mixed graphs, but has been tested to work with non-ancestral graphs.

This implementation differs from the specification of TESTMINSEP in [1] in that we replace the check in line 6 with \(z - i \neq R_x\), and similarly in line 8 with \(z - i \neq R_y\). This change was deemed necessary because in line 4 all nodes in i are removed, so there cannot be paths from x to i in the augmented moralized graph, causing the algorithm to return false when a minimal m-separator existed.

Parameters:

Gmixed-edge-graph

Mixed edge causal graph.

xnode

Node in G.

ynode

Node in G.

zset

Set of nodes in G representing the candidate minimal m-separator of x and y.

iset

Set of nodes which are always included in the found separating set, default is None, which is later set to empty set.

rset

Largest set of nodes which may be included in the found separating set, default is None, which is later set to all vertices in G.

directed_edge_namestr

Name of the directed edge, default is ‘directed’.

bidirected_edge_namestr

Name of the bidirected edge, default is ‘bidirected’.

undirected_edge_namestr

Name of the undirected edge, default is ‘undirected’.

Returns:

is_minimal_m_sepbool

If the set z is a minimal m-separator, returns True, else returns False.

References

[1] (1,2)

B. van der Zander, M. Liśkiewicz, and J. Textor, “Separators and Adjustment Sets in Causal Graphs: Complete Criteria and an Algorithmic Framework,” Artificial Intelligence, vol. 270, pp. 1–40, May 2019, doi: 10.1016/j.artint.2018.12.006.