Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/relabel.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 import networkx as nx | |
2 | |
3 __all__ = ["convert_node_labels_to_integers", "relabel_nodes"] | |
4 | |
5 | |
6 def relabel_nodes(G, mapping, copy=True): | |
7 """Relabel the nodes of the graph G. | |
8 | |
9 Parameters | |
10 ---------- | |
11 G : graph | |
12 A NetworkX graph | |
13 | |
14 mapping : dictionary | |
15 A dictionary with the old labels as keys and new labels as values. | |
16 A partial mapping is allowed. Mapping 2 nodes to a single node is allowed. | |
17 | |
18 copy : bool (optional, default=True) | |
19 If True return a copy, or if False relabel the nodes in place. | |
20 | |
21 Examples | |
22 -------- | |
23 To create a new graph with nodes relabeled according to a given | |
24 dictionary: | |
25 | |
26 >>> G = nx.path_graph(3) | |
27 >>> sorted(G) | |
28 [0, 1, 2] | |
29 >>> mapping = {0: "a", 1: "b", 2: "c"} | |
30 >>> H = nx.relabel_nodes(G, mapping) | |
31 >>> sorted(H) | |
32 ['a', 'b', 'c'] | |
33 | |
34 Nodes can be relabeled with any hashable object, including numbers | |
35 and strings: | |
36 | |
37 >>> import string | |
38 >>> G = nx.path_graph(26) # nodes are integers 0 through 25 | |
39 >>> sorted(G)[:3] | |
40 [0, 1, 2] | |
41 >>> mapping = dict(zip(G, string.ascii_lowercase)) | |
42 >>> G = nx.relabel_nodes(G, mapping) # nodes are characters a through z | |
43 >>> sorted(G)[:3] | |
44 ['a', 'b', 'c'] | |
45 >>> mapping = dict(zip(G, range(1, 27))) | |
46 >>> G = nx.relabel_nodes(G, mapping) # nodes are integers 1 through 26 | |
47 >>> sorted(G)[:3] | |
48 [1, 2, 3] | |
49 | |
50 To perform a partial in-place relabeling, provide a dictionary | |
51 mapping only a subset of the nodes, and set the `copy` keyword | |
52 argument to False: | |
53 | |
54 >>> G = nx.path_graph(3) # nodes 0-1-2 | |
55 >>> mapping = {0: "a", 1: "b"} # 0->'a' and 1->'b' | |
56 >>> G = nx.relabel_nodes(G, mapping, copy=False) | |
57 >>> sorted(G, key=str) | |
58 [2, 'a', 'b'] | |
59 | |
60 A mapping can also be given as a function: | |
61 | |
62 >>> G = nx.path_graph(3) | |
63 >>> H = nx.relabel_nodes(G, lambda x: x ** 2) | |
64 >>> list(H) | |
65 [0, 1, 4] | |
66 | |
67 In a multigraph, relabeling two or more nodes to the same new node | |
68 will retain all edges, but may change the edge keys in the process: | |
69 | |
70 >>> G = nx.MultiGraph() | |
71 >>> G.add_edge(0, 1, value="a") # returns the key for this edge | |
72 0 | |
73 >>> G.add_edge(0, 2, value="b") | |
74 0 | |
75 >>> G.add_edge(0, 3, value="c") | |
76 0 | |
77 >>> mapping = {1: 4, 2: 4, 3: 4} | |
78 >>> H = nx.relabel_nodes(G, mapping, copy=True) | |
79 >>> print(H[0]) | |
80 {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}} | |
81 | |
82 This works for in-place relabeling too: | |
83 | |
84 >>> G = nx.relabel_nodes(G, mapping, copy=False) | |
85 >>> print(G[0]) | |
86 {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}} | |
87 | |
88 Notes | |
89 ----- | |
90 Only the nodes specified in the mapping will be relabeled. | |
91 | |
92 The keyword setting copy=False modifies the graph in place. | |
93 Relabel_nodes avoids naming collisions by building a | |
94 directed graph from ``mapping`` which specifies the order of | |
95 relabelings. Naming collisions, such as a->b, b->c, are ordered | |
96 such that "b" gets renamed to "c" before "a" gets renamed "b". | |
97 In cases of circular mappings (e.g. a->b, b->a), modifying the | |
98 graph is not possible in-place and an exception is raised. | |
99 In that case, use copy=True. | |
100 | |
101 If a relabel operation on a multigraph would cause two or more | |
102 edges to have the same source, target and key, the second edge must | |
103 be assigned a new key to retain all edges. The new key is set | |
104 to the lowest non-negative integer not already used as a key | |
105 for edges between these two nodes. Note that this means non-numeric | |
106 keys may be replaced by numeric keys. | |
107 | |
108 See Also | |
109 -------- | |
110 convert_node_labels_to_integers | |
111 """ | |
112 # you can pass a function f(old_label)->new_label | |
113 # but we'll just make a dictionary here regardless | |
114 if not hasattr(mapping, "__getitem__"): | |
115 m = {n: mapping(n) for n in G} | |
116 else: | |
117 m = mapping | |
118 if copy: | |
119 return _relabel_copy(G, m) | |
120 else: | |
121 return _relabel_inplace(G, m) | |
122 | |
123 | |
124 def _relabel_inplace(G, mapping): | |
125 old_labels = set(mapping.keys()) | |
126 new_labels = set(mapping.values()) | |
127 if len(old_labels & new_labels) > 0: | |
128 # labels sets overlap | |
129 # can we topological sort and still do the relabeling? | |
130 D = nx.DiGraph(list(mapping.items())) | |
131 D.remove_edges_from(nx.selfloop_edges(D)) | |
132 try: | |
133 nodes = reversed(list(nx.topological_sort(D))) | |
134 except nx.NetworkXUnfeasible as e: | |
135 raise nx.NetworkXUnfeasible( | |
136 "The node label sets are overlapping and no ordering can " | |
137 "resolve the mapping. Use copy=True." | |
138 ) from e | |
139 else: | |
140 # non-overlapping label sets | |
141 nodes = old_labels | |
142 | |
143 multigraph = G.is_multigraph() | |
144 directed = G.is_directed() | |
145 | |
146 for old in nodes: | |
147 try: | |
148 new = mapping[old] | |
149 except KeyError: | |
150 continue | |
151 if new == old: | |
152 continue | |
153 try: | |
154 G.add_node(new, **G.nodes[old]) | |
155 except KeyError as e: | |
156 raise KeyError(f"Node {old} is not in the graph") from e | |
157 if multigraph: | |
158 new_edges = [ | |
159 (new, new if old == target else target, key, data) | |
160 for (_, target, key, data) in G.edges(old, data=True, keys=True) | |
161 ] | |
162 if directed: | |
163 new_edges += [ | |
164 (new if old == source else source, new, key, data) | |
165 for (source, _, key, data) in G.in_edges(old, data=True, keys=True) | |
166 ] | |
167 # Ensure new edges won't overwrite existing ones | |
168 seen = set() | |
169 for i, (source, target, key, data) in enumerate(new_edges): | |
170 if target in G[source] and key in G[source][target]: | |
171 new_key = 0 if not isinstance(key, (int, float)) else key | |
172 while new_key in G[source][target] or (target, new_key) in seen: | |
173 new_key += 1 | |
174 new_edges[i] = (source, target, new_key, data) | |
175 seen.add((target, new_key)) | |
176 else: | |
177 new_edges = [ | |
178 (new, new if old == target else target, data) | |
179 for (_, target, data) in G.edges(old, data=True) | |
180 ] | |
181 if directed: | |
182 new_edges += [ | |
183 (new if old == source else source, new, data) | |
184 for (source, _, data) in G.in_edges(old, data=True) | |
185 ] | |
186 G.remove_node(old) | |
187 G.add_edges_from(new_edges) | |
188 return G | |
189 | |
190 | |
191 def _relabel_copy(G, mapping): | |
192 H = G.__class__() | |
193 H.add_nodes_from(mapping.get(n, n) for n in G) | |
194 H._node.update((mapping.get(n, n), d.copy()) for n, d in G.nodes.items()) | |
195 if G.is_multigraph(): | |
196 new_edges = [ | |
197 (mapping.get(n1, n1), mapping.get(n2, n2), k, d.copy()) | |
198 for (n1, n2, k, d) in G.edges(keys=True, data=True) | |
199 ] | |
200 | |
201 # check for conflicting edge-keys | |
202 undirected = not G.is_directed() | |
203 seen_edges = set() | |
204 for i, (source, target, key, data) in enumerate(new_edges): | |
205 while (source, target, key) in seen_edges: | |
206 if not isinstance(key, (int, float)): | |
207 key = 0 | |
208 key += 1 | |
209 seen_edges.add((source, target, key)) | |
210 if undirected: | |
211 seen_edges.add((target, source, key)) | |
212 new_edges[i] = (source, target, key, data) | |
213 | |
214 H.add_edges_from(new_edges) | |
215 else: | |
216 H.add_edges_from( | |
217 (mapping.get(n1, n1), mapping.get(n2, n2), d.copy()) | |
218 for (n1, n2, d) in G.edges(data=True) | |
219 ) | |
220 H.graph.update(G.graph) | |
221 return H | |
222 | |
223 | |
224 def convert_node_labels_to_integers( | |
225 G, first_label=0, ordering="default", label_attribute=None | |
226 ): | |
227 """Returns a copy of the graph G with the nodes relabeled using | |
228 consecutive integers. | |
229 | |
230 Parameters | |
231 ---------- | |
232 G : graph | |
233 A NetworkX graph | |
234 | |
235 first_label : int, optional (default=0) | |
236 An integer specifying the starting offset in numbering nodes. | |
237 The new integer labels are numbered first_label, ..., n-1+first_label. | |
238 | |
239 ordering : string | |
240 "default" : inherit node ordering from G.nodes() | |
241 "sorted" : inherit node ordering from sorted(G.nodes()) | |
242 "increasing degree" : nodes are sorted by increasing degree | |
243 "decreasing degree" : nodes are sorted by decreasing degree | |
244 | |
245 label_attribute : string, optional (default=None) | |
246 Name of node attribute to store old label. If None no attribute | |
247 is created. | |
248 | |
249 Notes | |
250 ----- | |
251 Node and edge attribute data are copied to the new (relabeled) graph. | |
252 | |
253 There is no guarantee that the relabeling of nodes to integers will | |
254 give the same two integers for two (even identical graphs). | |
255 Use the `ordering` argument to try to preserve the order. | |
256 | |
257 See Also | |
258 -------- | |
259 relabel_nodes | |
260 """ | |
261 N = G.number_of_nodes() + first_label | |
262 if ordering == "default": | |
263 mapping = dict(zip(G.nodes(), range(first_label, N))) | |
264 elif ordering == "sorted": | |
265 nlist = sorted(G.nodes()) | |
266 mapping = dict(zip(nlist, range(first_label, N))) | |
267 elif ordering == "increasing degree": | |
268 dv_pairs = [(d, n) for (n, d) in G.degree()] | |
269 dv_pairs.sort() # in-place sort from lowest to highest degree | |
270 mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N))) | |
271 elif ordering == "decreasing degree": | |
272 dv_pairs = [(d, n) for (n, d) in G.degree()] | |
273 dv_pairs.sort() # in-place sort from lowest to highest degree | |
274 dv_pairs.reverse() | |
275 mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N))) | |
276 else: | |
277 raise nx.NetworkXError(f"Unknown node ordering: {ordering}") | |
278 H = relabel_nodes(G, mapping) | |
279 # create node attribute with the old label | |
280 if label_attribute is not None: | |
281 nx.set_node_attributes(H, {v: k for k, v in mapping.items()}, label_attribute) | |
282 return H |