Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.voronoi

# voronoi.py - functions for computing the Voronoi partition of a graph
#
#
# This file is part of NetworkX.
#
# information.
"""Functions for computing the Voronoi cells of a graph."""
import networkx as nx
from networkx.utils import groups

__all__ = ['voronoi_cells']

[docs]def voronoi_cells(G, center_nodes, weight='weight'):
"""Returns the Voronoi cells centered at center_nodes with respect
to the shortest-path distance metric.

If *C* is a set of nodes in the graph and *c* is an element of *C*,
the *Voronoi cell* centered at a node *c* is the set of all nodes
*v* that are closer to *c* than to any other center node in *C* with
respect to the shortest-path distance metric. [1]_

For directed graphs, this will compute the "outward" Voronoi cells,
as defined in [1]_, in which distance is measured from the center
nodes to the target node. For the "inward" Voronoi cells, use the
:meth:DiGraph.reverse method to reverse the orientation of the
edges before invoking this function on the directed graph.

Parameters
----------
G : NetworkX graph

center_nodes : set
A nonempty set of nodes in the graph G that represent the
center of the Voronoi cells.

weight : string or function
The edge attribute (or an arbitrary function) representing the
weight of an edge. This keyword argument is as described in the
documentation for :func:~networkx.multi_source_dijkstra_path,
for example.

Returns
-------
dictionary
A mapping from center node to set of all nodes in the graph
closer to that center node than to any other center node. The
keys of the dictionary are the element of center_nodes, and
the values of the dictionary form a partition of the nodes of
G.

Examples
--------
To get only the partition of the graph induced by the Voronoi cells,
take the collection of all values in the returned dictionary::

>>> 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
If center_nodes is empty.

References
----------
.. [1] Erwig, Martin. (2000),
"The graph Voronoi diagram with applications."
*Networks*, 36: 156--163.
<dx.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