Source code for networkx.algorithms.voronoi

"""用于计算图的Voronoi单元格的函数。"""

import networkx as nx
from networkx.utils import groups

__all__ = ["voronoi_cells"]




@nx._dispatchable(edge_attrs="weight")
def voronoi_cells(G, center_nodes, weight="weight"):
    """返回以 `center_nodes` 为中心的沃罗诺伊单元，关于最短路径距离度量。

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

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

Parameters
----------
G : NetworkX 图

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

weight : 字符串或函数
    表示边权重的边属性（或任意函数）。此关键字参数如 :func:`~networkx.multi_source_dijkstra_path` 文档中所述。

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

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

Raises
------
ValueError
    如果 `center_nodes` 为空。

References
----------
.. [1] 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
"""
    # Determine the shortest paths from any one of the center nodes to
    # every node in the graph.
    #
    # This raises `ValueError` if `center_nodes` is an empty set.
    paths = nx.multi_source_dijkstra_path(G, center_nodes, weight=weight)
    # Determine the center node from which the shortest path originates.
    nearest = {v: p[0] for v, p in paths.items()}
    # Get the mapping from center node to all nodes closer to it than to
    # any other center node.
    cells = groups(nearest)
    # We collect all unreachable nodes under a special key, if there are any.
    unreachable = set(G) - set(nearest)
    if unreachable:
        cells["unreachable"] = unreachable
    return cells