find_minimal_d_separator#
- find_minimal_d_separator(G, x, y, *, included=None, restricted=None)[source]#
如果可能，返回
x和y之间的最小 D 分离集有向无环图 (DAG) 中的 D 分离集是一组节点，它阻塞了节点集
x和y之间的所有路径。此函数构建一个“最小”的 D 分离集，这意味着在不失去x和y的 D 分离特性的前提下，不能移除任何节点。如果x和y不存在 D 分离集，则返回None。在有向无环图 (DAG) 中，两个节点集之间可能存在多个最小 D 分离集。最小 D 分离集并不总是唯一的。此函数返回一个最小 D 分离集；如果不存在 D 分离集，则返回
None。使用 [1] 中提出的算法。该算法的复杂度为 \(O(m)\)，其中 \(m\) 是图 G 中仅包含
x和y的祖先的子图中的边数。更多详细信息，请参阅 [1]。- 参数:
- Ggraph
NetworkX 有向无环图 (DAG)。
- xset | node
图中的一个节点或节点集。
- yset | node
图中的一个节点或节点集。
- includedset | node | None
必须包含在找到的分离集中的一个节点或节点集，默认为 None，表示空集。
- restrictedset | node | None
限制要考虑的一个节点或节点集。只有这些节点可以在找到的分离集中，默认为 None，表示图
G中的所有节点。
- 返回:
- zset | None
最小 D 分离集（如果存在至少一个 D 分离集），否则为 None。
- 引发:
- NetworkXError
如果输入图不是有向无环图 (DAG)，或者节点集
x、y和included不相交，则引发NetworkXError。- NodeNotFound
如果在图中未找到任何输入节点，则引发
NodeNotFound异常。
参考文献