3.1.13. pywhy_graphs.networkx.minimal_m_separator

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

Find a i-minimal m-separating set ‘z’ between ‘x’ and ‘y’ in mixed-edge causal graph G.

The set which may contain directed, bidirected, and undirected edges. An i-minimal m-separating set is a minimal m-separator that contains i.

This implements the m-separation algorithm FINDSEP presented in [1] for ancestral mixed graphs. The algorithm has runtime \(O(|E| + |V|)\) for number of edges :math`|E|` and number of vertices \(|V|\).

This implementation differs from the specification of FINDMINSEP in [1] in that all nodes in i are removed from the anterior graph \(G'\), in between lines 3 and 4. This change was deemed necessary because otherwise the TESTSEP call in line 7 would fail even if the union of z and i was a valid i-minimal m-separating set.

Parameters:

Gmixed-edge-graph

Mixed edge causal graph.

xnode

Node in G.

ynode

Node in G.

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:

zset | None

If a separating set exists, returns a set of nodes which m-separates x and y, otherwise returns None.

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.