ioftools / networkxMiCe / networkxmaster / 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 20162019 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 shortestpath 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 shortestpath 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: 156163.

76 
<dx.doi.org/10.1002/10970037(200010)36:3<156::AIDNET2>3.0.CO;2L>

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
