voronoi_cells

voronoi_cells(G, center_nodes, weight='weight')

返回以 center_nodes 为中心，基于最短路径距离度量的 Voronoi 单元。

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

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

参数:

GNetworkX 图

center_nodes集合

图中 G 的一个非空节点集合，代表 Voronoi 单元的中心。

weight字符串或函数

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

返回:

字典

一个映射，将中心节点映射到图中所有比其他任何中心节点更接近该中心节点的节点集合。字典的键是 center_nodes 中的元素，字典的值构成了 G 节点的一个划分。

引发:

ValueError

如果 center_nodes 为空。

参考文献

[1] (1,2)

Erwig, Martin. (2000),“带应用的图 Voronoi 图.” Networks, 36: 156–163. https://doi.org/10.1002/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L

示例

要仅获取由 Voronoi 单元导出的图划分，请获取返回字典中的所有值集合

>>> 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]]