Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/relabel.py: 9%
88 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1import networkx as nx
3__all__ = ["convert_node_labels_to_integers", "relabel_nodes"]
6@nx._dispatch(preserve_all_attrs=True)
7def relabel_nodes(G, mapping, copy=True):
8 """Relabel the nodes of the graph G according to a given mapping.
10 The original node ordering may not be preserved if `copy` is `False` and the
11 mapping includes overlap between old and new labels.
13 Parameters
14 ----------
15 G : graph
16 A NetworkX graph
18 mapping : dictionary
19 A dictionary with the old labels as keys and new labels as values.
20 A partial mapping is allowed. Mapping 2 nodes to a single node is allowed.
21 Any non-node keys in the mapping are ignored.
23 copy : bool (optional, default=True)
24 If True return a copy, or if False relabel the nodes in place.
26 Examples
27 --------
28 To create a new graph with nodes relabeled according to a given
29 dictionary:
31 >>> G = nx.path_graph(3)
32 >>> sorted(G)
33 [0, 1, 2]
34 >>> mapping = {0: "a", 1: "b", 2: "c"}
35 >>> H = nx.relabel_nodes(G, mapping)
36 >>> sorted(H)
37 ['a', 'b', 'c']
39 Nodes can be relabeled with any hashable object, including numbers
40 and strings:
42 >>> import string
43 >>> G = nx.path_graph(26) # nodes are integers 0 through 25
44 >>> sorted(G)[:3]
45 [0, 1, 2]
46 >>> mapping = dict(zip(G, string.ascii_lowercase))
47 >>> G = nx.relabel_nodes(G, mapping) # nodes are characters a through z
48 >>> sorted(G)[:3]
49 ['a', 'b', 'c']
50 >>> mapping = dict(zip(G, range(1, 27)))
51 >>> G = nx.relabel_nodes(G, mapping) # nodes are integers 1 through 26
52 >>> sorted(G)[:3]
53 [1, 2, 3]
55 To perform a partial in-place relabeling, provide a dictionary
56 mapping only a subset of the nodes, and set the `copy` keyword
57 argument to False:
59 >>> G = nx.path_graph(3) # nodes 0-1-2
60 >>> mapping = {0: "a", 1: "b"} # 0->'a' and 1->'b'
61 >>> G = nx.relabel_nodes(G, mapping, copy=False)
62 >>> sorted(G, key=str)
63 [2, 'a', 'b']
65 A mapping can also be given as a function:
67 >>> G = nx.path_graph(3)
68 >>> H = nx.relabel_nodes(G, lambda x: x ** 2)
69 >>> list(H)
70 [0, 1, 4]
72 In a multigraph, relabeling two or more nodes to the same new node
73 will retain all edges, but may change the edge keys in the process:
75 >>> G = nx.MultiGraph()
76 >>> G.add_edge(0, 1, value="a") # returns the key for this edge
77 0
78 >>> G.add_edge(0, 2, value="b")
79 0
80 >>> G.add_edge(0, 3, value="c")
81 0
82 >>> mapping = {1: 4, 2: 4, 3: 4}
83 >>> H = nx.relabel_nodes(G, mapping, copy=True)
84 >>> print(H[0])
85 {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}}
87 This works for in-place relabeling too:
89 >>> G = nx.relabel_nodes(G, mapping, copy=False)
90 >>> print(G[0])
91 {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}}
93 Notes
94 -----
95 Only the nodes specified in the mapping will be relabeled.
96 Any non-node keys in the mapping are ignored.
98 The keyword setting copy=False modifies the graph in place.
99 Relabel_nodes avoids naming collisions by building a
100 directed graph from ``mapping`` which specifies the order of
101 relabelings. Naming collisions, such as a->b, b->c, are ordered
102 such that "b" gets renamed to "c" before "a" gets renamed "b".
103 In cases of circular mappings (e.g. a->b, b->a), modifying the
104 graph is not possible in-place and an exception is raised.
105 In that case, use copy=True.
107 If a relabel operation on a multigraph would cause two or more
108 edges to have the same source, target and key, the second edge must
109 be assigned a new key to retain all edges. The new key is set
110 to the lowest non-negative integer not already used as a key
111 for edges between these two nodes. Note that this means non-numeric
112 keys may be replaced by numeric keys.
114 See Also
115 --------
116 convert_node_labels_to_integers
117 """
118 # you can pass any callable e.g. f(old_label) -> new_label or
119 # e.g. str(old_label) -> new_label, but we'll just make a dictionary here regardless
120 m = {n: mapping(n) for n in G} if callable(mapping) else mapping
122 if copy:
123 return _relabel_copy(G, m)
124 else:
125 return _relabel_inplace(G, m)
128def _relabel_inplace(G, mapping):
129 if len(mapping.keys() & mapping.values()) > 0:
130 # labels sets overlap
131 # can we topological sort and still do the relabeling?
132 D = nx.DiGraph(list(mapping.items()))
133 D.remove_edges_from(nx.selfloop_edges(D))
134 try:
135 nodes = reversed(list(nx.topological_sort(D)))
136 except nx.NetworkXUnfeasible as err:
137 raise nx.NetworkXUnfeasible(
138 "The node label sets are overlapping and no ordering can "
139 "resolve the mapping. Use copy=True."
140 ) from err
141 else:
142 # non-overlapping label sets, sort them in the order of G nodes
143 nodes = [n for n in G if n in mapping]
145 multigraph = G.is_multigraph()
146 directed = G.is_directed()
148 for old in nodes:
149 # Test that old is in both mapping and G, otherwise ignore.
150 try:
151 new = mapping[old]
152 G.add_node(new, **G.nodes[old])
153 except KeyError:
154 continue
155 if new == old:
156 continue
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
191def _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 ]
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)
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
224@nx._dispatch(
225 preserve_edge_attrs=True, preserve_node_attrs=True, preserve_graph_attrs=True
226)
227def convert_node_labels_to_integers(
228 G, first_label=0, ordering="default", label_attribute=None
229):
230 """Returns a copy of the graph G with the nodes relabeled using
231 consecutive integers.
233 Parameters
234 ----------
235 G : graph
236 A NetworkX graph
238 first_label : int, optional (default=0)
239 An integer specifying the starting offset in numbering nodes.
240 The new integer labels are numbered first_label, ..., n-1+first_label.
242 ordering : string
243 "default" : inherit node ordering from G.nodes()
244 "sorted" : inherit node ordering from sorted(G.nodes())
245 "increasing degree" : nodes are sorted by increasing degree
246 "decreasing degree" : nodes are sorted by decreasing degree
248 label_attribute : string, optional (default=None)
249 Name of node attribute to store old label. If None no attribute
250 is created.
252 Notes
253 -----
254 Node and edge attribute data are copied to the new (relabeled) graph.
256 There is no guarantee that the relabeling of nodes to integers will
257 give the same two integers for two (even identical graphs).
258 Use the `ordering` argument to try to preserve the order.
260 See Also
261 --------
262 relabel_nodes
263 """
264 N = G.number_of_nodes() + first_label
265 if ordering == "default":
266 mapping = dict(zip(G.nodes(), range(first_label, N)))
267 elif ordering == "sorted":
268 nlist = sorted(G.nodes())
269 mapping = dict(zip(nlist, range(first_label, N)))
270 elif ordering == "increasing degree":
271 dv_pairs = [(d, n) for (n, d) in G.degree()]
272 dv_pairs.sort() # in-place sort from lowest to highest degree
273 mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N)))
274 elif ordering == "decreasing degree":
275 dv_pairs = [(d, n) for (n, d) in G.degree()]
276 dv_pairs.sort() # in-place sort from lowest to highest degree
277 dv_pairs.reverse()
278 mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N)))
279 else:
280 raise nx.NetworkXError(f"Unknown node ordering: {ordering}")
281 H = relabel_nodes(G, mapping)
282 # create node attribute with the old label
283 if label_attribute is not None:
284 nx.set_node_attributes(H, {v: k for k, v in mapping.items()}, label_attribute)
285 return H