is_minimal_d_separator#
- is_minimal_d_separator(G, x, y, z, *, included=None, restricted=None)[source]#
Determine if
z
is a minimal d-separator forx
andy
.A d-separator,
z
, in a DAG is a set of nodes that blocks all paths from nodes in setx
to nodes in sety
. A minimal d-separator is a d-separatorz
such that removing any subset of nodes makes it no longer a d-separator.Note: This function checks whether
z
is a d-separator AND is minimal. One can use the functionis_d_separator
to only check ifz
is a d-separator. See examples below.- Parameters:
- Gnx.DiGraph
A NetworkX DAG.
- xnode | set
A node or set of nodes in the graph.
- ynode | set
A node or set of nodes in the graph.
- znode | set
The node or set of nodes to check if it is a minimal d-separating set. The function
is_d_separator()
is called inside this function to verify thatz
is in fact a d-separator.- includedset | node | None
A node or set of nodes which must be included in the found separating set, default is
None
, which means the empty set.- restrictedset | node | None
Restricted node or set of nodes to consider. Only these nodes can be in the found separating set, default is
None
meaning all nodes inG
.
- Returns:
- bool
Whether or not the set
z
is a minimal d-separator subject torestricted
nodes andincluded
node constraints.
- 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 works on verifying that a set is minimal and d-separating between two nodes. Uses criterion (a), (b), (c) on page 4 of [1]. a) closure(
x
) andy
are disjoint. b)z
contains all nodes fromincluded
and is contained in therestricted
nodes and in the union of ancestors ofx
,y
, andincluded
. c) the nodes inz
not inincluded
are contained in both closure(x) and closure(y). The closure of a set is the set of nodes connected to the set by a directed path in G.The complexity is \(O(m)\), where \(m\) stands for the number of edges in the subgraph of G consisting of only the ancestors of
x
andy
.For full details, see [1].
References
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.is_d_separator(G, 0, 2, {1, 3, 4}) True