Mercurial > repos > guerler > springsuite

annotate planemo/lib/python3.7/site-packages/networkx/relabel.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
1 # Copyright (C) 2006-2019 by
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
2 # Aric Hagberg <hagberg@lanl.gov>
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
3 # Dan Schult <dschult@colgate.edu>
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
4 # Pieter Swart <swart@lanl.gov>
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
5 # All rights reserved.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
6 # BSD license.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
7 import networkx as nx
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
8
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
9 __all__ = ['convert_node_labels_to_integers', 'relabel_nodes']
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
10
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
11
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
12 def relabel_nodes(G, mapping, copy=True):
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
13 """Relabel the nodes of the graph G.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
14
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
15 Parameters
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
16 ----------
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
17 G : graph
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
18 A NetworkX graph
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
19
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
20 mapping : dictionary
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
21 A dictionary with the old labels as keys and new labels as values.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
22 A partial mapping is allowed.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
23
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
24 copy : bool (optional, default=True)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
25 If True return a copy, or if False relabel the nodes in place.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
26
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
27 Examples
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
28 --------
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
29 To create a new graph with nodes relabeled according to a given
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
30 dictionary:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
31
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
32 >>> G = nx.path_graph(3)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
33 >>> sorted(G)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
34 [0, 1, 2]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
35 >>> mapping = {0: 'a', 1: 'b', 2: 'c'}
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
36 >>> H = nx.relabel_nodes(G, mapping)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
37 >>> sorted(H)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
38 ['a', 'b', 'c']
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
39
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
40 Nodes can be relabeled with any hashable object, including numbers
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
41 and strings:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
42
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
43 >>> import string
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
44 >>> G = nx.path_graph(26) # nodes are integers 0 through 25
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
45 >>> sorted(G)[:3]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
46 [0, 1, 2]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
47 >>> mapping = dict(zip(G, string.ascii_lowercase))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
48 >>> G = nx.relabel_nodes(G, mapping) # nodes are characters a through z
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
49 >>> sorted(G)[:3]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
50 ['a', 'b', 'c']
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
51 >>> mapping = dict(zip(G, range(1, 27)))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
52 >>> G = nx.relabel_nodes(G, mapping) # nodes are integers 1 through 26
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
53 >>> sorted(G)[:3]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
54 [1, 2, 3]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
55
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
56 To perform a partial in-place relabeling, provide a dictionary
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
57 mapping only a subset of the nodes, and set the `copy` keyword
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
58 argument to False:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
59
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
60 >>> G = nx.path_graph(3) # nodes 0-1-2
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
61 >>> mapping = {0: 'a', 1: 'b'} # 0->'a' and 1->'b'
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
62 >>> G = nx.relabel_nodes(G, mapping, copy=False)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
63 >>> sorted(G, key=str)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
64 [2, 'a', 'b']
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
65
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
66 A mapping can also be given as a function:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
67
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
68 >>> G = nx.path_graph(3)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
69 >>> H = nx.relabel_nodes(G, lambda x: x ** 2)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
70 >>> list(H)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
71 [0, 1, 4]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
72
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
73 Notes
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
74 -----
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
75 Only the nodes specified in the mapping will be relabeled.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
76
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
77 The keyword setting copy=False modifies the graph in place.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
78 Relabel_nodes avoids naming collisions by building a
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
79 directed graph from ``mapping`` which specifies the order of
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
80 relabelings. Naming collisions, such as a->b, b->c, are ordered
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
81 such that "b" gets renamed to "c" before "a" gets renamed "b".
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
82 In cases of circular mappings (e.g. a->b, b->a), modifying the
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
83 graph is not possible in-place and an exception is raised.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
84 In that case, use copy=True.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
85
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
86 See Also
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
87 --------
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
88 convert_node_labels_to_integers
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
89 """
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
90 # you can pass a function f(old_label)->new_label
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
91 # but we'll just make a dictionary here regardless
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
92 if not hasattr(mapping, "__getitem__"):
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
93 m = {n: mapping(n) for n in G}
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
94 else:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
95 m = mapping
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
96 if copy:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
97 return _relabel_copy(G, m)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
98 else:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
99 return _relabel_inplace(G, m)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
100
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
101
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
102 def _relabel_inplace(G, mapping):
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
103 old_labels = set(mapping.keys())
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
104 new_labels = set(mapping.values())
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
105 if len(old_labels & new_labels) > 0:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
106 # labels sets overlap
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
107 # can we topological sort and still do the relabeling?
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
108 D = nx.DiGraph(list(mapping.items()))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
109 D.remove_edges_from(nx.selfloop_edges(D))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
110 try:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
111 nodes = reversed(list(nx.topological_sort(D)))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
112 except nx.NetworkXUnfeasible:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
113 raise nx.NetworkXUnfeasible('The node label sets are overlapping '
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
114 'and no ordering can resolve the '
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
115 'mapping. Use copy=True.')
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
116 else:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
117 # non-overlapping label sets
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
118 nodes = old_labels
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
119
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
120 multigraph = G.is_multigraph()
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
121 directed = G.is_directed()
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
122
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
123 for old in nodes:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
124 try:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
125 new = mapping[old]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
126 except KeyError:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
127 continue
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
128 if new == old:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
129 continue
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
130 try:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
131 G.add_node(new, **G.nodes[old])
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
132 except KeyError:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
133 raise KeyError("Node %s is not in the graph" % old)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
134 if multigraph:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
135 new_edges = [(new, new if old == target else target, key, data)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
136 for (_, target, key, data)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
137 in G.edges(old, data=True, keys=True)]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
138 if directed:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
139 new_edges += [(new if old == source else source, new, key, data)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
140 for (source, _, key, data)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
141 in G.in_edges(old, data=True, keys=True)]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
142 else:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
143 new_edges = [(new, new if old == target else target, data)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
144 for (_, target, data) in G.edges(old, data=True)]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
145 if directed:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
146 new_edges += [(new if old == source else source, new, data)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
147 for (source, _, data) in G.in_edges(old, data=True)]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
148 G.remove_node(old)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
149 G.add_edges_from(new_edges)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
150 return G
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
151
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
152
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
153 def _relabel_copy(G, mapping):
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
154 H = G.__class__()
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
155 H.add_nodes_from(mapping.get(n, n) for n in G)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
156 H._node.update((mapping.get(n, n), d.copy()) for n, d in G.nodes.items())
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
157 if G.is_multigraph():
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
158 H.add_edges_from((mapping.get(n1, n1), mapping.get(n2, n2), k, d.copy())
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
159 for (n1, n2, k, d) in G.edges(keys=True, data=True))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
160 else:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
161 H.add_edges_from((mapping.get(n1, n1), mapping.get(n2, n2), d.copy())
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
162 for (n1, n2, d) in G.edges(data=True))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
163 H.graph.update(G.graph)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
164 return H
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
165
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
166
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
167 def convert_node_labels_to_integers(G, first_label=0, ordering="default",
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
168 label_attribute=None):
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
169 """Returns a copy of the graph G with the nodes relabeled using
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
170 consecutive integers.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
171
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
172 Parameters
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
173 ----------
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
174 G : graph
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
175 A NetworkX graph
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
176
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
177 first_label : int, optional (default=0)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
178 An integer specifying the starting offset in numbering nodes.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
179 The new integer labels are numbered first_label, ..., n-1+first_label.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
180
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
181 ordering : string
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
182 "default" : inherit node ordering from G.nodes()
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
183 "sorted" : inherit node ordering from sorted(G.nodes())
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
184 "increasing degree" : nodes are sorted by increasing degree
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
185 "decreasing degree" : nodes are sorted by decreasing degree
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
186
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
187 label_attribute : string, optional (default=None)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
188 Name of node attribute to store old label. If None no attribute
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
189 is created.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
190
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
191 Notes
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
192 -----
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
193 Node and edge attribute data are copied to the new (relabeled) graph.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
194
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
195 There is no guarantee that the relabeling of nodes to integers will
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
196 give the same two integers for two (even identical graphs).
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
197 Use the `ordering` argument to try to preserve the order.
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
198
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
199 See Also
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
200 --------
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
201 relabel_nodes
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
202 """
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
203 N = G.number_of_nodes() + first_label
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
204 if ordering == "default":
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
205 mapping = dict(zip(G.nodes(), range(first_label, N)))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
206 elif ordering == "sorted":
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
207 nlist = sorted(G.nodes())
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
208 mapping = dict(zip(nlist, range(first_label, N)))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
209 elif ordering == "increasing degree":
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
210 dv_pairs = [(d, n) for (n, d) in G.degree()]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
211 dv_pairs.sort() # in-place sort from lowest to highest degree
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
212 mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N)))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
213 elif ordering == "decreasing degree":
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
214 dv_pairs = [(d, n) for (n, d) in G.degree()]
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
215 dv_pairs.sort() # in-place sort from lowest to highest degree
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
216 dv_pairs.reverse()
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
217 mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N)))
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
218 else:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
219 raise nx.NetworkXError('Unknown node ordering: %s' % ordering)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
220 H = relabel_nodes(G, mapping)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
221 # create node attribute with the old label
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
222 if label_attribute is not None:
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
223 nx.set_node_attributes(H, {v: k for k, v in mapping.items()},
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
224 label_attribute)
56ad4e20f292 "planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
guerler
parents:
diff changeset
225 return H