is_minimal_d_separator#
- is_minimal_d_separator(G, x, y, z, *, included=None, restricted=None)[源码]#
确定
z是否是x和y的最小 d-分离集。DAG 中的 d-分离集
z是一组节点，它阻塞了从集合x中的节点到集合y中的节点的所有路径。最小 d-分离集是一个 d-分离集z，移除其任何子集都会使其不再是 d-分离集。注意：此函数检查
z是否既是 d-分离集又是最小的。可以使用函数is_d_separator仅检查z是否是 d-分离集。参见下面的示例。- 参数:
- Gnx.DiGraph
一个 NetworkX 有向无环图（DAG）。
- x节点 | 集合
图中的一个节点或一组节点。
- y节点 | 集合
图中的一个节点或一组节点。
- z节点 | 集合
要检查是否是最小 d-分离集的一个节点或一组节点。此函数内部会调用函数
is_d_separator()来验证z实际上是一个 d-分离集。- included集合 | 节点 | None
必须包含在找到的分离集中的一个节点或一组节点，默认为
None，表示空集。- restricted集合 | 节点 | None
要考虑的受限节点或节点集。只有这些节点可以包含在找到的分离集中，默认为
None，表示G中的所有节点。
- 返回:
- bool
集合
z在受限节点restricted和包含节点included的约束下是否是一个最小 d-分离集。
- 引发:
- NetworkXError
如果输入图不是 DAG，则引发
NetworkXError。- NodeNotFound
如果在图中找不到任何输入节点，则会引发
NodeNotFound异常。
说明
此函数用于验证一个集合在两个节点之间是否是最小且 d-分离的。使用了 [1] 第 4 页的判据 (a), (b), (c)。a) closure(
x) 和y是不相交的。b)z包含included中的所有节点，并且包含在restricted节点以及x,y和included的祖先节点的并集中。c)z中不属于included的节点同时包含在 closure(x) 和 closure(y) 中。一个集合的闭包是图中通过有向路径连接到该集合的所有节点的集合。复杂度是 \(O(m)\)，其中 \(m\) 是由
x和y的祖先节点组成的 G 的子图中的边的数量。详细信息，请参阅 [1]。
参考文献
示例
>>> 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