Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/voronoi.py: 42%

1"""Functions for computing the Voronoi cells of a graph.""" 

2import networkx as nx 

3from networkx.utils import groups 

4 

5__all__ = ["voronoi_cells"] 

6 

7 

8@nx._dispatch(edge_attrs="weight") 

9def voronoi_cells(G, center_nodes, weight="weight"): 

10 """Returns the Voronoi cells centered at `center_nodes` with respect 

11 to the shortest-path distance metric. 

12 

13 If $C$ is a set of nodes in the graph and $c$ is an element of $C$, 

14 the *Voronoi cell* centered at a node $c$ is the set of all nodes 

15 $v$ that are closer to $c$ than to any other center node in $C$ with 

16 respect to the shortest-path distance metric. [1]_ 

17 

18 For directed graphs, this will compute the "outward" Voronoi cells, 

19 as defined in [1]_, in which distance is measured from the center 

20 nodes to the target node. For the "inward" Voronoi cells, use the 

21 :meth:`DiGraph.reverse` method to reverse the orientation of the 

22 edges before invoking this function on the directed graph. 

23 

24 Parameters 

25 ---------- 

26 G : NetworkX graph 

27 

28 center_nodes : set 

29 A nonempty set of nodes in the graph `G` that represent the 

30 center of the Voronoi cells. 

31 

32 weight : string or function 

33 The edge attribute (or an arbitrary function) representing the 

34 weight of an edge. This keyword argument is as described in the 

35 documentation for :func:`~networkx.multi_source_dijkstra_path`, 

36 for example. 

37 

38 Returns 

39 ------- 

40 dictionary 

41 A mapping from center node to set of all nodes in the graph 

42 closer to that center node than to any other center node. The 

43 keys of the dictionary are the element of `center_nodes`, and 

44 the values of the dictionary form a partition of the nodes of 

45 `G`. 

46 

47 Examples 

48 -------- 

49 To get only the partition of the graph induced by the Voronoi cells, 

50 take the collection of all values in the returned dictionary:: 

51 

52 >>> G = nx.path_graph(6) 

53 >>> center_nodes = {0, 3} 

54 >>> cells = nx.voronoi_cells(G, center_nodes) 

55 >>> partition = set(map(frozenset, cells.values())) 

56 >>> sorted(map(sorted, partition)) 

57 [[0, 1], [2, 3, 4, 5]] 

58 

59 Raises 

60 ------ 

61 ValueError 

62 If `center_nodes` is empty. 

63 

64 References 

65 ---------- 

66 .. [1] Erwig, Martin. (2000),"The graph Voronoi diagram with applications." 

67 *Networks*, 36: 156--163. 

68 https://doi.org/10.1002/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L 

69 

70 """ 

71 # Determine the shortest paths from any one of the center nodes to 

72 # every node in the graph. 

73 # 

74 # This raises `ValueError` if `center_nodes` is an empty set. 

75 paths = nx.multi_source_dijkstra_path(G, center_nodes, weight=weight) 

76 # Determine the center node from which the shortest path originates. 

77 nearest = {v: p[0] for v, p in paths.items()} 

78 # Get the mapping from center node to all nodes closer to it than to 

79 # any other center node. 

80 cells = groups(nearest) 

81 # We collect all unreachable nodes under a special key, if there are any. 

82 unreachable = set(G) - set(nearest) 

83 if unreachable: 

84 cells["unreachable"] = unreachable 

85 return cells