voronoi_cells#

voronoi_cells(G, center_nodes, weight='weight')[source]#

返回以 center_nodes 为中心的沃罗诺伊单元，关于最短路径距离度量。

如果 \(C\) 是图中的节点集合，且 \(c\) 是 \(C\) 的一个元素，那么以节点 \(c\) 为中心的 沃罗诺伊单元 是所有节点 \(v\) 的集合，这些节点 \(v\) 到 \(c\) 的距离比到 \(C\) 中任何其他中心节点的距离都短，关于最短路径距离度量。[1]

对于有向图，这将计算 [1] 中定义的“向外”沃罗诺伊单元，其中距离是从中心节点到目标节点测量的。对于“向内”沃罗诺伊单元，使用 DiGraph.reverse() 方法在调用此函数之前反转有向图的边方向。

Parameters:
GNetworkX 图
center_nodes集合

图 G 中表示沃罗诺伊单元中心的非空节点集合。

weight字符串或函数

表示边权重的边属性（或任意函数）。此关键字参数如 multi_source_dijkstra_path() 文档中所述。

Returns:
字典

从中心节点到图中所有比其他中心节点更接近该中心节点的节点的映射。字典的键是 center_nodes 的元素，字典的值构成了 G 的节点的分区。

Raises:
ValueError

如果 center_nodes 为空。

References

[1] (1,2)

Erwig, Martin. (2000), “The graph Voronoi diagram with applications.” Networks, 36: 156–163. https://doi.org/10.1002/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L

Examples

要仅获取由沃罗诺伊单元诱导的图的分区，取返回字典中所有值的集合:

>>> G = nx.path_graph(6)
>>> center_nodes = {0, 3}
>>> cells = nx.voronoi_cells(G, center_nodes)
>>> partition = set(map(frozenset, cells.values()))
>>> sorted(map(sorted, partition))
[[0, 1], [2, 3, 4, 5]]
On this page