find_induced_nodes

find_induced_nodes(G, s, t, treewidth_bound=9223372036854775807)

返回从 s 到 t 路径中的诱导节点集合。

参数：

G图

一个弦图类型的 NetworkX 图

s节点

查找诱导节点的源节点

t节点

查找诱导节点的目标节点

treewidth_bound: 浮点数

图 H 可接受的最大树宽。一旦超过 treewidth_bound，查找诱导节点的搜索将立即停止。

返回值：

induced_nodes节点集合

图 G 中从 s 到 t 路径中的诱导节点集合

引发异常：

NetworkXError

该算法不支持 DiGraph、MultiGraph 和 MultiDiGraph。如果输入图是这些类之一的实例，则会引发 NetworkXError。该算法仅适用于弦图。如果发现输入图不是弦图，则会引发 NetworkXError。

注意

G 必须是弦图，且 (s,t) 必须是不在 G 中的一条边。

如果提供了 treewidth_bound，一旦超过 treewidth_bound，查找诱导节点的搜索将立即停止。

该算法的灵感来自 [1] 中的算法 4。诱导节点的正式定义也可以在该参考文献中找到。

忽略自环

参考文献

[1]

Learning Bounded Treewidth Bayesian Networks. Gal Elidan, Stephen Gould; JMLR, 9(Dec):2699–2731, 2008. http://jmlr.csail.mit.edu/papers/volume9/elidan08a/elidan08a.pdf

示例

>>> G = nx.Graph()
>>> G = nx.generators.classic.path_graph(10)
>>> induced_nodes = nx.find_induced_nodes(G, 1, 9, 2)
>>> sorted(induced_nodes)
[1, 2, 3, 4, 5, 6, 7, 8, 9]