is_minimal_d_separator#

is_minimal_d_separator(G, u, v, z)[source]#

Determine if a d-separating set is minimal.

A d-separating set, z, in a DAG is a set of nodes that blocks all paths between the two nodes, u and v. This function verifies that a set is “minimal”, meaning there is no smaller d-separating set between the two nodes.

Note: This function checks whether z is a d-separator AND is minimal. One can use the function d_separated to only check if z is a d-separator. See examples below.

Parameters:

Gnx.DiGraph: The graph.
unode: A node in the graph.
vnode: A node in the graph.
zSet of nodes: The set of nodes to check if it is a minimal d-separating set. The function d_separated() is called inside this function to verify that z is in fact a d-separator.

Returns:

bool: Whether or not the set z is a d-separator and is also minimal.

Raises:

NetworkXError: Raises a NetworkXError if the input graph is not a DAG.
NodeNotFound: If any of the input nodes are not found in the graph, a NodeNotFound exception is raised.

Notes

This function only works on verifying a d-separating set is minimal between two nodes. To verify that a d-separating set is minimal between two sets of nodes is not supported.

Uses algorithm 2 presented in [1]. The complexity of the algorithm is \(O(|E_{An}^m|)\), where \(|E_{An}^m|\) stands for the number of edges in the moralized graph of the sub-graph consisting of only the ancestors of u and v.

The algorithm works by constructing the moral graph consisting of just the ancestors of u and v. First, it performs BFS on the moral graph starting from u and marking any nodes it encounters that are part of the separating set, z. If a node is marked, then it does not continue along that path. In the second stage, BFS with markings is repeated on the moral graph starting from v. If at any stage, any node in z is not marked, then z is considered not minimal. If the end of the algorithm is reached, then z is minimal.

For full details, see [1].

https://en.wikipedia.org/wiki/Bayesian_network#d-separation

References

[1] (1,2)

Tian, J., & Paz, A. (1998). Finding Minimal D-separators.

Examples

>>> G = nx.path_graph([0, 1, 2, 3], create_using=nx.DiGraph)
>>> G.add_node(4)
>>> nx.is_minimal_d_separator(G, 0, 2, {1})
True
>>> # since {1} is the minimal d-separator, {1, 3, 4} is not minimal
>>> nx.is_minimal_d_separator(G, 0, 2, {1, 3, 4})
False
>>> # alternatively, if we only want to check that {1, 3, 4} is a d-separator
>>> nx.d_separated(G, {0}, {4}, {1, 3, 4})
True