Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.32 KB)

1
# voronoi.py - functions for computing the Voronoi partition of a graph
2
#
3
# Copyright 2016-2019 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Functions for computing the Voronoi cells of a graph."""
10
import networkx as nx
11
from networkx.utils import groups
12

    
13
__all__ = ['voronoi_cells']
14

    
15

    
16
def voronoi_cells(G, center_nodes, weight='weight'):
17
    """Returns the Voronoi cells centered at `center_nodes` with respect
18
    to the shortest-path distance metric.
19

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

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

31
    Parameters
32
    ----------
33
    G : NetworkX graph
34

35
    center_nodes : set
36
        A nonempty set of nodes in the graph `G` that represent the
37
        center of the Voronoi cells.
38

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

45
    Returns
46
    -------
47
    dictionary
48
        A mapping from center node to set of all nodes in the graph
49
        closer to that center node than to any other center node. The
50
        keys of the dictionary are the element of `center_nodes`, and
51
        the values of the dictionary form a partition of the nodes of
52
        `G`.
53

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

59
        >>> G = nx.path_graph(6)
60
        >>> center_nodes = {0, 3}
61
        >>> cells = nx.voronoi_cells(G, center_nodes)
62
        >>> partition = set(map(frozenset, cells.values()))
63
        >>> sorted(map(sorted, partition))
64
        [[0, 1], [2, 3, 4, 5]]
65

66
    Raises
67
    ------
68
    ValueError
69
        If `center_nodes` is empty.
70

71
    References
72
    ----------
73
    .. [1] Erwig, Martin. (2000),
74
           "The graph Voronoi diagram with applications."
75
           *Networks*, 36: 156--163.
76
           <dx.doi.org/10.1002/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L>
77

78
    """
79
    # Determine the shortest paths from any one of the center nodes to
80
    # every node in the graph.
81
    #
82
    # This raises `ValueError` if `center_nodes` is an empty set.
83
    paths = nx.multi_source_dijkstra_path(G, center_nodes, weight=weight)
84
    # Determine the center node from which the shortest path originates.
85
    nearest = {v: p[0] for v, p in paths.items()}
86
    # Get the mapping from center node to all nodes closer to it than to
87
    # any other center node.
88
    cells = groups(nearest)
89
    # We collect all unreachable nodes under a special key, if there are any.
90
    unreachable = set(G) - set(nearest)
91
    if unreachable:
92
        cells['unreachable'] = unreachable
93
    return cells