3.1.9. 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:

G : mixed-edge-graph

Mixed edge causal graph.

x : node

Node in G.

y : node

Node in G.

i : set

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

r : set

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_name : str

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

bidirected_edge_name : str

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

undirected_edge_name : str

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

Returns:

z : set | 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.