find_minimal_d_separator

find_minimal_d_separator(G, x, y, *, included=None, restricted=None)

返回一个最小化的d-分离集在 x 和 y 之间，如果可能的话

在一个DAG中的d-分离集是一组节点，它阻断了两个节点集 x 和 y 之间的所有路径。这个函数构建了一个“最小化”的d-分离集，意味着没有任何节点可以被移除而不失去对 x 和 y 的d-分离属性。如果 x 和 y 之间不存在d-分离集，则返回 None 。

在一个DAG中，两个节点集之间可能存在多个最小化的d-分离器。最小化的d-分离器并不总是唯一的。这个函数返回一个最小化的d-分离器，或者如果没有任何d-分离器存在则返回 None 。

使用[1]中提出的算法。该算法的复杂度为 \(O(m)\) ，其中 \(m\) 表示仅由 x 和 y 的祖先组成的G子图中的边数。详细信息请参见[1]。

Parameters:

G图

一个networkx DAG。

x集合 | 节点

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

y集合 | 节点

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

included集合 | 节点 | None

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

restricted集合 | 节点 | None

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

Returns:

z集合 | None

如果至少存在一个d-分离集，则返回最小化的d-分离集，否则返回None。

Raises:

NetworkXError

如果输入图不是DAG或者节点集 x 、 y 和 included 不是不相交的，则引发 NetworkXError 。

NodeNotFound

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

References

[1]

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.