Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / relabel.py @ 5cef0f13

History | View | Annotate | Download (7.71 KB)

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