Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/relabel.py: 9%

1import networkx as nx 

2 

3__all__ = ["convert_node_labels_to_integers", "relabel_nodes"] 

4 

5 

6@nx._dispatchable( 

7 preserve_all_attrs=True, mutates_input={"not copy": 2}, returns_graph=True 

8) 

9def relabel_nodes(G, mapping, copy=True): 

10 """Relabel the nodes of the graph G according to a given mapping. 

11 

12 The original node ordering may not be preserved if `copy` is `False` and the 

13 mapping includes overlap between old and new labels. 

14 

15 Parameters 

16 ---------- 

17 G : graph 

18 A NetworkX graph 

19 

20 mapping : dictionary 

21 A dictionary with the old labels as keys and new labels as values. 

22 A partial mapping is allowed. Mapping 2 nodes to a single node is allowed. 

23 Any non-node keys in the mapping are ignored. 

24 

25 copy : bool (optional, default=True) 

26 If True return a copy, or if False relabel the nodes in place. 

27 

28 Examples 

29 -------- 

30 To create a new graph with nodes relabeled according to a given 

31 dictionary: 

32 

33 >>> G = nx.path_graph(3) 

34 >>> sorted(G) 

35 [0, 1, 2] 

36 >>> mapping = {0: "a", 1: "b", 2: "c"} 

37 >>> H = nx.relabel_nodes(G, mapping) 

38 >>> sorted(H) 

39 ['a', 'b', 'c'] 

40 

41 Nodes can be relabeled with any hashable object, including numbers 

42 and strings: 

43 

44 >>> import string 

45 >>> G = nx.path_graph(26) # nodes are integers 0 through 25 

46 >>> sorted(G)[:3] 

47 [0, 1, 2] 

48 >>> mapping = dict(zip(G, string.ascii_lowercase)) 

49 >>> G = nx.relabel_nodes(G, mapping) # nodes are characters a through z 

50 >>> sorted(G)[:3] 

51 ['a', 'b', 'c'] 

52 >>> mapping = dict(zip(G, range(1, 27))) 

53 >>> G = nx.relabel_nodes(G, mapping) # nodes are integers 1 through 26 

54 >>> sorted(G)[:3] 

55 [1, 2, 3] 

56 

57 To perform a partial in-place relabeling, provide a dictionary 

58 mapping only a subset of the nodes, and set the `copy` keyword 

59 argument to False: 

60 

61 >>> G = nx.path_graph(3) # nodes 0-1-2 

62 >>> mapping = {0: "a", 1: "b"} # 0->'a' and 1->'b' 

63 >>> G = nx.relabel_nodes(G, mapping, copy=False) 

64 >>> sorted(G, key=str) 

65 [2, 'a', 'b'] 

66 

67 A mapping can also be given as a function: 

68 

69 >>> G = nx.path_graph(3) 

70 >>> H = nx.relabel_nodes(G, lambda x: x**2) 

71 >>> list(H) 

72 [0, 1, 4] 

73 

74 In a multigraph, relabeling two or more nodes to the same new node 

75 will retain all edges, but may change the edge keys in the process: 

76 

77 >>> G = nx.MultiGraph() 

78 >>> G.add_edge(0, 1, value="a") # returns the key for this edge 

79 0 

80 >>> G.add_edge(0, 2, value="b") 

81 0 

82 >>> G.add_edge(0, 3, value="c") 

83 0 

84 >>> mapping = {1: 4, 2: 4, 3: 4} 

85 >>> H = nx.relabel_nodes(G, mapping, copy=True) 

86 >>> print(H[0]) 

87 {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}} 

88 

89 This works for in-place relabeling too: 

90 

91 >>> G = nx.relabel_nodes(G, mapping, copy=False) 

92 >>> print(G[0]) 

93 {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}} 

94 

95 Notes 

96 ----- 

97 Only the nodes specified in the mapping will be relabeled. 

98 Any non-node keys in the mapping are ignored. 

99 

100 The keyword setting copy=False modifies the graph in place. 

101 Relabel_nodes avoids naming collisions by building a 

102 directed graph from ``mapping`` which specifies the order of 

103 relabelings. Naming collisions, such as a->b, b->c, are ordered 

104 such that "b" gets renamed to "c" before "a" gets renamed "b". 

105 In cases of circular mappings (e.g. a->b, b->a), modifying the 

106 graph is not possible in-place and an exception is raised. 

107 In that case, use copy=True. 

108 

109 If a relabel operation on a multigraph would cause two or more 

110 edges to have the same source, target and key, the second edge must 

111 be assigned a new key to retain all edges. The new key is set 

112 to the lowest non-negative integer not already used as a key 

113 for edges between these two nodes. Note that this means non-numeric 

114 keys may be replaced by numeric keys. 

115 

116 See Also 

117 -------- 

118 convert_node_labels_to_integers 

119 """ 

120 # you can pass any callable e.g. f(old_label) -> new_label or 

121 # e.g. str(old_label) -> new_label, but we'll just make a dictionary here regardless 

122 m = {n: mapping(n) for n in G} if callable(mapping) else mapping 

123 

124 if copy: 

125 return _relabel_copy(G, m) 

126 else: 

127 return _relabel_inplace(G, m) 

128 

129 

130def _relabel_inplace(G, mapping): 

131 if len(mapping.keys() & mapping.values()) > 0: 

132 # labels sets overlap 

133 # can we topological sort and still do the relabeling? 

134 D = nx.DiGraph(list(mapping.items())) 

135 D.remove_edges_from(nx.selfloop_edges(D)) 

136 try: 

137 nodes = reversed(list(nx.topological_sort(D))) 

138 except nx.NetworkXUnfeasible as err: 

139 raise nx.NetworkXUnfeasible( 

140 "The node label sets are overlapping and no ordering can " 

141 "resolve the mapping. Use copy=True." 

142 ) from err 

143 else: 

144 # non-overlapping label sets, sort them in the order of G nodes 

145 nodes = [n for n in G if n in mapping] 

146 

147 multigraph = G.is_multigraph() 

148 directed = G.is_directed() 

149 

150 for old in nodes: 

151 # Test that old is in both mapping and G, otherwise ignore. 

152 try: 

153 new = mapping[old] 

154 G.add_node(new, **G.nodes[old]) 

155 except KeyError: 

156 continue 

157 if new == old: 

158 continue 

159 if multigraph: 

160 new_edges = [ 

161 (new, new if old == target else target, key, data) 

162 for (_, target, key, data) in G.edges(old, data=True, keys=True) 

163 ] 

164 if directed: 

165 new_edges += [ 

166 (new if old == source else source, new, key, data) 

167 for (source, _, key, data) in G.in_edges(old, data=True, keys=True) 

168 ] 

169 # Ensure new edges won't overwrite existing ones 

170 seen = set() 

171 for i, (source, target, key, data) in enumerate(new_edges): 

172 if target in G[source] and key in G[source][target]: 

173 new_key = 0 if not isinstance(key, int | float) else key 

174 while new_key in G[source][target] or (target, new_key) in seen: 

175 new_key += 1 

176 new_edges[i] = (source, target, new_key, data) 

177 seen.add((target, new_key)) 

178 else: 

179 new_edges = [ 

180 (new, new if old == target else target, data) 

181 for (_, target, data) in G.edges(old, data=True) 

182 ] 

183 if directed: 

184 new_edges += [ 

185 (new if old == source else source, new, data) 

186 for (source, _, data) in G.in_edges(old, data=True) 

187 ] 

188 G.remove_node(old) 

189 G.add_edges_from(new_edges) 

190 return G 

191 

192 

193def _relabel_copy(G, mapping): 

194 H = G.__class__() 

195 H.add_nodes_from(mapping.get(n, n) for n in G) 

196 H._node.update((mapping.get(n, n), d.copy()) for n, d in G.nodes.items()) 

197 if G.is_multigraph(): 

198 new_edges = [ 

199 (mapping.get(n1, n1), mapping.get(n2, n2), k, d.copy()) 

200 for (n1, n2, k, d) in G.edges(keys=True, data=True) 

201 ] 

202 

203 # check for conflicting edge-keys 

204 undirected = not G.is_directed() 

205 seen_edges = set() 

206 for i, (source, target, key, data) in enumerate(new_edges): 

207 while (source, target, key) in seen_edges: 

208 if not isinstance(key, int | float): 

209 key = 0 

210 key += 1 

211 seen_edges.add((source, target, key)) 

212 if undirected: 

213 seen_edges.add((target, source, key)) 

214 new_edges[i] = (source, target, key, data) 

215 

216 H.add_edges_from(new_edges) 

217 else: 

218 H.add_edges_from( 

219 (mapping.get(n1, n1), mapping.get(n2, n2), d.copy()) 

220 for (n1, n2, d) in G.edges(data=True) 

221 ) 

222 H.graph.update(G.graph) 

223 return H 

224 

225 

226@nx._dispatchable(preserve_all_attrs=True, returns_graph=True) 

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. 

232 

233 Parameters 

234 ---------- 

235 G : graph 

236 A NetworkX graph 

237 

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. 

241 

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 

247 

248 label_attribute : string, optional (default=None) 

249 Name of node attribute to store old label. If None no attribute 

250 is created. 

251 

252 Notes 

253 ----- 

254 Node and edge attribute data are copied to the new (relabeled) graph. 

255 

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. 

259 

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