Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/algorithms/voronoi.py: 46%

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

2 

3import networkx as nx 

4from networkx.utils import groups 

5 

6__all__ = ["voronoi_cells"] 

7 

8 

9@nx._dispatchable(edge_attrs="weight") 

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

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

12 to the shortest-path distance metric. 

13 

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

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

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

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

18 

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

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

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

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

23 edges before invoking this function on the directed graph. 

24 

25 Parameters 

26 ---------- 

27 G : NetworkX graph 

28 

29 center_nodes : set 

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

31 center of the Voronoi cells. 

32 

33 weight : string or function 

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

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

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

37 for example. 

38 

39 Returns 

40 ------- 

41 dictionary 

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

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

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

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

46 `G`. 

47 

48 Examples 

49 -------- 

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

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

52 

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

54 >>> center_nodes = {0, 3} 

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

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

57 >>> sorted(map(sorted, partition)) 

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

59 

60 Raises 

61 ------ 

62 ValueError 

63 If `center_nodes` is empty. 

64 

65 References 

66 ---------- 

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

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

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

70 

71 """ 

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

73 # every node in the graph. 

74 # 

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

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

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

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

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

80 # any other center node. 

81 cells = groups(nearest) 

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

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

84 if unreachable: 

85 cells["unreachable"] = unreachable 

86 return cells