Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/voronoi.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions for computing the Voronoi cells of a graph.""" | |
2 import networkx as nx | |
3 from networkx.utils import groups | |
4 | |
5 __all__ = ["voronoi_cells"] | |
6 | |
7 | |
8 def voronoi_cells(G, center_nodes, weight="weight"): | |
9 """Returns the Voronoi cells centered at `center_nodes` with respect | |
10 to the shortest-path distance metric. | |
11 | |
12 If *C* is a set of nodes in the graph and *c* is an element of *C*, | |
13 the *Voronoi cell* centered at a node *c* is the set of all nodes | |
14 *v* that are closer to *c* than to any other center node in *C* with | |
15 respect to the shortest-path distance metric. [1]_ | |
16 | |
17 For directed graphs, this will compute the "outward" Voronoi cells, | |
18 as defined in [1]_, in which distance is measured from the center | |
19 nodes to the target node. For the "inward" Voronoi cells, use the | |
20 :meth:`DiGraph.reverse` method to reverse the orientation of the | |
21 edges before invoking this function on the directed graph. | |
22 | |
23 Parameters | |
24 ---------- | |
25 G : NetworkX graph | |
26 | |
27 center_nodes : set | |
28 A nonempty set of nodes in the graph `G` that represent the | |
29 center of the Voronoi cells. | |
30 | |
31 weight : string or function | |
32 The edge attribute (or an arbitrary function) representing the | |
33 weight of an edge. This keyword argument is as described in the | |
34 documentation for :func:`~networkx.multi_source_dijkstra_path`, | |
35 for example. | |
36 | |
37 Returns | |
38 ------- | |
39 dictionary | |
40 A mapping from center node to set of all nodes in the graph | |
41 closer to that center node than to any other center node. The | |
42 keys of the dictionary are the element of `center_nodes`, and | |
43 the values of the dictionary form a partition of the nodes of | |
44 `G`. | |
45 | |
46 Examples | |
47 -------- | |
48 To get only the partition of the graph induced by the Voronoi cells, | |
49 take the collection of all values in the returned dictionary:: | |
50 | |
51 >>> G = nx.path_graph(6) | |
52 >>> center_nodes = {0, 3} | |
53 >>> cells = nx.voronoi_cells(G, center_nodes) | |
54 >>> partition = set(map(frozenset, cells.values())) | |
55 >>> sorted(map(sorted, partition)) | |
56 [[0, 1], [2, 3, 4, 5]] | |
57 | |
58 Raises | |
59 ------ | |
60 ValueError | |
61 If `center_nodes` is empty. | |
62 | |
63 References | |
64 ---------- | |
65 .. [1] Erwig, Martin. (2000), | |
66 "The graph Voronoi diagram with applications." | |
67 *Networks*, 36: 156--163. | |
68 <dx.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 |