Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/relabel.py @ 0:26e78fe6e8c4 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
author shellac
date Sat, 02 May 2020 07:14:21 -0400
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:26e78fe6e8c4
1 # Copyright (C) 2006-2019 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 in-place 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 0-1-2
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 in-place 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 # non-overlapping 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, ..., n-1+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() # in-place 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() # in-place 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