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-分离器。请参见下面的示例。

Parameters:

Gnx.DiGraph

一个 NetworkX DAG。

x节点 | 集合

图中的一个节点或节点集合。

y节点 | 集合

图中的一个节点或节点集合。

z节点 | 集合

要检查的节点或节点集合，以确定它是否是最小 d-分离集合。 此函数内部调用 is_d_separator() 函数来验证 z 是否确实是 d-分离器。

included集合 | 节点 | None

必须包含在找到的分离集合中的节点或节点集合，默认为 None ，表示空集。

restricted集合 | 节点 | None

要考虑的受限节点或节点集合。只有这些节点可以包含在找到的分离集合中，默认为 None ，表示 G 中的所有节点。

Returns:

bool

在 restricted 节点和 included 节点约束下，集合 z 是否是最小 d-分离器。

Raises:

NetworkXError

如果输入图不是 DAG，则引发 NetworkXError 。

NodeNotFound

如果输入节点中的任何一个在图中找不到，则引发 NodeNotFound 异常。

Notes

此函数用于验证一个集合是否是两个节点之间的最小且 d-分离的。使用 [1] 第4页上的标准 (a), (b), (c)：a) closure( x ) 和 y 是不相交的。b) z 包含 included 中的所有节点，并且包含在 restricted 节点以及 x , y 和 included 的祖先的并集中。c) z 中不在 included 中的节点包含在 closure(x) 和 closure(y) 中。一个集合的闭包是通过 G 中的有向路径连接到该集合的所有节点的集合。

复杂度为 \(O(m)\) ，其中 \(m\) 表示 G 的子图中仅包含 x 和 y 的祖先的边的数量。

有关详细信息，请参见 [1]。

References

[1] (1,2)

van der Zander, Benito, and Maciej Liśkiewicz. “Finding minimal d-separators in linear time and applications.” In Uncertainty in Artificial Intelligence, pp. 637-647. PMLR, 2020.

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
>>> # 因为 {1} 是最小 d-分离器，{1, 3, 4} 不是最小
>>> nx.is_minimal_d_separator(G, 0, 2, {1, 3, 4})
False
>>> # 或者，如果我们只想检查 {1, 3, 4} 是否是 d-分离器
>>> nx.is_d_separator(G, 0, 2, {1, 3, 4})
True