find_minimal_d_separator#
- find_minimal_d_separator(G, x, y, *, included=None, restricted=None)[source]#
Returns a minimal d-separating set between
x
andy
if possibleA d-separating set in a DAG is a set of nodes that blocks all paths between the two sets of nodes,
x
andy
. This function constructs a d-separating set that is “minimal”, meaning no nodes can be removed without it losing the d-separating property forx
andy
. If no d-separating sets exist forx
andy
, this returnsNone
.In a DAG there may be more than one minimal d-separator between two sets of nodes. Minimal d-separators are not always unique. This function returns one minimal d-separator, or
None
if no d-separator exists.Uses the algorithm presented in [1]. The complexity of the algorithm 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].- Parameters:
- Ggraph
A networkx DAG.
- xset | node
A node or set of nodes in the graph.
- yset | node
A node or set of nodes in the graph.
- 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 in
G
.
- Returns:
- zset | None
The minimal d-separating set, if at least one d-separating set exists, otherwise None.
- Raises:
- NetworkXError
Raises a
NetworkXError
if the input graph is not a DAG or if node setsx
,y
, andincluded
are not disjoint.- NodeNotFound
If any of the input nodes are not found in the graph, a
NodeNotFound
exception is raised.
References