Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / voronoi.py @ 5cef0f13

 1 ```# voronoi.py - functions for computing the Voronoi partition of a graph ``` ```# ``` ```# Copyright 2016-2019 NetworkX developers. ``` ```# ``` ```# This file is part of NetworkX. ``` ```# ``` ```# NetworkX is distributed under a BSD license; see LICENSE.txt for more ``` ```# information. ``` ```"""Functions for computing the Voronoi cells of a graph.""" ``` ```import networkx as nx ``` ```from networkx.utils import groups ``` ```__all__ = ['voronoi_cells'] ``` ```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. _ ``` ``` ``` ``` For directed graphs, this will compute the "outward" Voronoi cells, ``` ``` as defined in _, 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 ``` ``` ---------- ``` ``` ..  Erwig, Martin. (2000), ``` ``` "The graph Voronoi diagram with applications." ``` ``` *Networks*, 36: 156--163. ``` ``` 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 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 ```