ioftools / networkxMiCe / networkxmaster / networkx / relabel.py @ 5cef0f13
History  View  Annotate  Download (7.71 KB)
1 
# Copyright (C) 20062019 by


2 
# Aric Hagberg <hagberg@lanl.gov>

3 
# Dan Schult <dschult@colgate.edu>

4 
# Pieter Swart <swart@lanl.gov>

5 
# All rights reserved.

6 
# BSD license.

7 
import networkx as nx 
8  
9 
__all__ = ['convert_node_labels_to_integers', 'relabel_nodes'] 
10  
11  
12 
def relabel_nodes(G, mapping, copy=True): 
13 
"""Relabel the nodes of the graph G.

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.

23 

24 
copy : bool (optional, default=True)

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

26 

27 
Examples

28 


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

30 
dictionary:

31 

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

33 
>>> sorted(G)

34 
[0, 1, 2]

35 
>>> mapping = {0: 'a', 1: 'b', 2: 'c'}

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

37 
>>> sorted(H)

38 
['a', 'b', 'c']

39 

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

41 
and strings:

42 

43 
>>> import string

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

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

46 
[0, 1, 2]

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

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

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

50 
['a', 'b', 'c']

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

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

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

54 
[1, 2, 3]

55 

56 
To perform a partial inplace relabeling, provide a dictionary

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

58 
argument to False:

59 

60 
>>> G = nx.path_graph(3) # nodes 012

61 
>>> mapping = {0: 'a', 1: 'b'} # 0>'a' and 1>'b'

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

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

64 
[2, 'a', 'b']

65 

66 
A mapping can also be given as a function:

67 

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

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

70 
>>> list(H)

71 
[0, 1, 4]

72 

73 
Notes

74 


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

76 

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

78 
Relabel_nodes avoids naming collisions by building a

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

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

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

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

83 
graph is not possible inplace and an exception is raised.

84 
In that case, use copy=True.

85 

86 
See Also

87 


88 
convert_node_labels_to_integers

89 
"""

90 
# you can pass a function f(old_label)>new_label

91 
# but we'll just make a dictionary here regardless

92 
if not hasattr(mapping, "__getitem__"): 
93 
m = {n: mapping(n) for n in G} 
94 
else:

95 
m = mapping 
96 
if copy:

97 
return _relabel_copy(G, m)

98 
else:

99 
return _relabel_inplace(G, m)

100  
101  
102 
def _relabel_inplace(G, mapping): 
103 
old_labels = set(mapping.keys())

104 
new_labels = set(mapping.values())

105 
if len(old_labels & new_labels) > 0: 
106 
# labels sets overlap

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

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

109 
D.remove_edges_from(nx.selfloop_edges(D)) 
110 
try:

111 
nodes = reversed(list(nx.topological_sort(D))) 
112 
except nx.NetworkXUnfeasible:

113 
raise nx.NetworkXUnfeasible('The node label sets are overlapping ' 
114 
'and no ordering can resolve the '

115 
'mapping. Use copy=True.')

116 
else:

117 
# nonoverlapping label sets

118 
nodes = old_labels 
119  
120 
multigraph = G.is_multigraph() 
121 
directed = G.is_directed() 
122  
123 
for old in nodes: 
124 
try:

125 
new = mapping[old] 
126 
except KeyError: 
127 
continue

128 
if new == old:

129 
continue

130 
try:

131 
G.add_node(new, **G.nodes[old]) 
132 
except KeyError: 
133 
raise KeyError("Node %s is not in the graph" % old) 
134 
if multigraph:

135 
new_edges = [(new, new if old == target else target, key, data) 
136 
for (_, target, key, data)

137 
in G.edges(old, data=True, keys=True)] 
138 
if directed:

139 
new_edges += [(new if old == source else source, new, key, data) 
140 
for (source, _, key, data)

141 
in G.in_edges(old, data=True, keys=True)] 
142 
else:

143 
new_edges = [(new, new if old == target else target, data) 
144 
for (_, target, data) in G.edges(old, data=True)] 
145 
if directed:

146 
new_edges += [(new if old == source else source, new, data) 
147 
for (source, _, data) in G.in_edges(old, data=True)] 
148 
G.remove_node(old) 
149 
G.add_edges_from(new_edges) 
150 
return G

151  
152  
153 
def _relabel_copy(G, mapping): 
154 
H = G.__class__() 
155 
H.add_nodes_from(mapping.get(n, n) for n in G) 
156 
H._node.update((mapping.get(n, n), d.copy()) for n, d in G.nodes.items()) 
157 
if G.is_multigraph():

158 
H.add_edges_from((mapping.get(n1, n1), mapping.get(n2, n2), k, d.copy()) 
159 
for (n1, n2, k, d) in G.edges(keys=True, data=True)) 
160 
else:

161 
H.add_edges_from((mapping.get(n1, n1), mapping.get(n2, n2), d.copy()) 
162 
for (n1, n2, d) in G.edges(data=True)) 
163 
H.graph.update(G.graph) 
164 
return H

165  
166  
167 
def convert_node_labels_to_integers(G, first_label=0, ordering="default", 
168 
label_attribute=None):

169 
"""Returns a copy of the graph G with the nodes relabeled using

170 
consecutive integers.

171 

172 
Parameters

173 


174 
G : graph

175 
A NetworkX graph

176 

177 
first_label : int, optional (default=0)

178 
An integer specifying the starting offset in numbering nodes.

179 
The new integer labels are numbered first_label, ..., n1+first_label.

180 

181 
ordering : string

182 
"default" : inherit node ordering from G.nodes()

183 
"sorted" : inherit node ordering from sorted(G.nodes())

184 
"increasing degree" : nodes are sorted by increasing degree

185 
"decreasing degree" : nodes are sorted by decreasing degree

186 

187 
label_attribute : string, optional (default=None)

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

189 
is created.

190 

191 
Notes

192 


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

194 

195 
There is no guarantee that the relabeling of nodes to integers will

196 
give the same two integers for two (even identical graphs).

197 
Use the `ordering` argument to try to preserve the order.

198 

199 
See Also

200 


201 
relabel_nodes

202 
"""

203 
N = G.number_of_nodes() + first_label 
204 
if ordering == "default": 
205 
mapping = dict(zip(G.nodes(), range(first_label, N))) 
206 
elif ordering == "sorted": 
207 
nlist = sorted(G.nodes())

208 
mapping = dict(zip(nlist, range(first_label, N))) 
209 
elif ordering == "increasing degree": 
210 
dv_pairs = [(d, n) for (n, d) in G.degree()] 
211 
dv_pairs.sort() # inplace sort from lowest to highest degree

212 
mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N))) 
213 
elif ordering == "decreasing degree": 
214 
dv_pairs = [(d, n) for (n, d) in G.degree()] 
215 
dv_pairs.sort() # inplace sort from lowest to highest degree

216 
dv_pairs.reverse() 
217 
mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N))) 
218 
else:

219 
raise nx.NetworkXError('Unknown node ordering: %s' % ordering) 
220 
H = relabel_nodes(G, mapping) 
221 
# create node attribute with the old label

222 
if label_attribute is not None: 
223 
nx.set_node_attributes(H, {v: k for k, v in mapping.items()}, 
224 
label_attribute) 
225 
return H
