1import networkx as nx 2 3__all__ = ["convert_node_labels_to_integers", "relabel_nodes"] 4 5 6def relabel_nodes(G, mapping, copy=True): 7 """Relabel the nodes of the graph G according to a given mapping. 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 Any non-node keys in the mapping are ignored. 18 19 copy : bool (optional, default=True) 20 If True return a copy, or if False relabel the nodes in place. 21 22 Examples 23 -------- 24 To create a new graph with nodes relabeled according to a given 25 dictionary: 26 27 >>> G = nx.path_graph(3) 28 >>> sorted(G) 29 [0, 1, 2] 30 >>> mapping = {0: "a", 1: "b", 2: "c"} 31 >>> H = nx.relabel_nodes(G, mapping) 32 >>> sorted(H) 33 ['a', 'b', 'c'] 34 35 Nodes can be relabeled with any hashable object, including numbers 36 and strings: 37 38 >>> import string 39 >>> G = nx.path_graph(26) # nodes are integers 0 through 25 40 >>> sorted(G)[:3] 41 [0, 1, 2] 42 >>> mapping = dict(zip(G, string.ascii_lowercase)) 43 >>> G = nx.relabel_nodes(G, mapping) # nodes are characters a through z 44 >>> sorted(G)[:3] 45 ['a', 'b', 'c'] 46 >>> mapping = dict(zip(G, range(1, 27))) 47 >>> G = nx.relabel_nodes(G, mapping) # nodes are integers 1 through 26 48 >>> sorted(G)[:3] 49 [1, 2, 3] 50 51 To perform a partial in-place relabeling, provide a dictionary 52 mapping only a subset of the nodes, and set the `copy` keyword 53 argument to False: 54 55 >>> G = nx.path_graph(3) # nodes 0-1-2 56 >>> mapping = {0: "a", 1: "b"} # 0->'a' and 1->'b' 57 >>> G = nx.relabel_nodes(G, mapping, copy=False) 58 >>> sorted(G, key=str) 59 [2, 'a', 'b'] 60 61 A mapping can also be given as a function: 62 63 >>> G = nx.path_graph(3) 64 >>> H = nx.relabel_nodes(G, lambda x: x ** 2) 65 >>> list(H) 66 [0, 1, 4] 67 68 In a multigraph, relabeling two or more nodes to the same new node 69 will retain all edges, but may change the edge keys in the process: 70 71 >>> G = nx.MultiGraph() 72 >>> G.add_edge(0, 1, value="a") # returns the key for this edge 73 0 74 >>> G.add_edge(0, 2, value="b") 75 0 76 >>> G.add_edge(0, 3, value="c") 77 0 78 >>> mapping = {1: 4, 2: 4, 3: 4} 79 >>> H = nx.relabel_nodes(G, mapping, copy=True) 80 >>> print(H[0]) 81 {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}} 82 83 This works for in-place relabeling too: 84 85 >>> G = nx.relabel_nodes(G, mapping, copy=False) 86 >>> print(G[0]) 87 {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}} 88 89 Notes 90 ----- 91 Only the nodes specified in the mapping will be relabeled. 92 Any non-node keys in the mapping are ignored. 93 94 The keyword setting copy=False modifies the graph in place. 95 Relabel_nodes avoids naming collisions by building a 96 directed graph from ``mapping`` which specifies the order of 97 relabelings. Naming collisions, such as a->b, b->c, are ordered 98 such that "b" gets renamed to "c" before "a" gets renamed "b". 99 In cases of circular mappings (e.g. a->b, b->a), modifying the 100 graph is not possible in-place and an exception is raised. 101 In that case, use copy=True. 102 103 If a relabel operation on a multigraph would cause two or more 104 edges to have the same source, target and key, the second edge must 105 be assigned a new key to retain all edges. The new key is set 106 to the lowest non-negative integer not already used as a key 107 for edges between these two nodes. Note that this means non-numeric 108 keys may be replaced by numeric keys. 109 110 See Also 111 -------- 112 convert_node_labels_to_integers 113 """ 114 # you can pass a function f(old_label)->new_label 115 # but we'll just make a dictionary here regardless 116 if not hasattr(mapping, "__getitem__"): 117 m = {n: mapping(n) for n in G} 118 else: 119 m = mapping 120 if copy: 121 return _relabel_copy(G, m) 122 else: 123 return _relabel_inplace(G, m) 124 125 126def _relabel_inplace(G, mapping): 127 old_labels = set(mapping.keys()) 128 new_labels = set(mapping.values()) 129 if len(old_labels & new_labels) > 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 e: 137 raise nx.NetworkXUnfeasible( 138 "The node label sets are overlapping and no ordering can " 139 "resolve the mapping. Use copy=True." 140 ) from e 141 else: 142 # non-overlapping label sets 143 nodes = old_labels 144 145 multigraph = G.is_multigraph() 146 directed = G.is_directed() 147 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 189 190 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 ] 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 224def 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 283