diff options
author | Nikos Chan <nik0sc@users.noreply.github.com> | 2020-08-15 12:56:35 +0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-08-14 21:56:35 -0700 |
commit | 1dd8288e01b19126a141c62b128c336be0ef8cea (patch) | |
tree | 36d8e54eefbf0010a3f23bc5469399bc874d3433 /networkx/relabel.py | |
parent | 5638e1ff3d01e21c7d950615a699eb1f99987b8d (diff) | |
download | networkx-1dd8288e01b19126a141c62b128c336be0ef8cea.tar.gz |
relabel_nodes now preserves edges in multigraphs (#4066)
* relabel_nodes now preserves edges in multigraphs
* fix pep8 and doctest
* Add tests that show trouble with inplace edge overwriting
* fix errors shown by tests for inplace overwriting
Co-authored-by: Dan Schult <dschult@colgate.edu>
Diffstat (limited to 'networkx/relabel.py')
-rw-r--r-- | networkx/relabel.py | 58 |
1 files changed, 55 insertions, 3 deletions
diff --git a/networkx/relabel.py b/networkx/relabel.py index 737b5af3..26f50d24 100644 --- a/networkx/relabel.py +++ b/networkx/relabel.py @@ -13,7 +13,7 @@ def relabel_nodes(G, mapping, copy=True): mapping : dictionary A dictionary with the old labels as keys and new labels as values. - A partial mapping is allowed. + A partial mapping is allowed. Mapping 2 nodes to a single node is allowed. copy : bool (optional, default=True) If True return a copy, or if False relabel the nodes in place. @@ -64,6 +64,27 @@ def relabel_nodes(G, mapping, copy=True): >>> list(H) [0, 1, 4] + In a multigraph, relabeling two or more nodes to the same new node + will retain all edges, but may change the edge keys in the process: + + >>> G = nx.MultiGraph() + >>> G.add_edge(0, 1, value="a") # returns the key for this edge + 0 + >>> G.add_edge(0, 2, value="b") + 0 + >>> G.add_edge(0, 3, value="c") + 0 + >>> mapping = {1: 4, 2: 4, 3: 4} + >>> H = nx.relabel_nodes(G, mapping, copy=True) + >>> print(H[0]) + {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}} + + This works for in-place relabeling too: + + >>> G = nx.relabel_nodes(G, mapping, copy=False) + >>> print(G[0]) + {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}} + Notes ----- Only the nodes specified in the mapping will be relabeled. @@ -77,6 +98,13 @@ def relabel_nodes(G, mapping, copy=True): graph is not possible in-place and an exception is raised. In that case, use copy=True. + If a relabel operation on a multigraph would cause two or more + edges to have the same source, target and key, the second edge must + be assigned a new key to retain all edges. The new key is set + to the lowest non-negative integer not already used as a key + for edges between these two nodes. Note that this means non-numeric + keys may be replaced by numeric keys. + See Also -------- convert_node_labels_to_integers @@ -136,6 +164,15 @@ def _relabel_inplace(G, mapping): (new if old == source else source, new, key, data) for (source, _, key, data) in G.in_edges(old, data=True, keys=True) ] + # Ensure new edges won't overwrite existing ones + seen = set() + for i, (source, target, key, data) in enumerate(new_edges): + if (target in G[source] and key in G[source][target]): + new_key = 0 if not isinstance(key, (int, float)) else key + while (new_key in G[source][target] or (target, new_key) in seen): + new_key += 1 + new_edges[i] = (source, target, new_key, data) + seen.add((target, new_key)) else: new_edges = [ (new, new if old == target else target, data) @@ -156,10 +193,25 @@ def _relabel_copy(G, mapping): H.add_nodes_from(mapping.get(n, n) for n in G) H._node.update((mapping.get(n, n), d.copy()) for n, d in G.nodes.items()) if G.is_multigraph(): - H.add_edges_from( + new_edges = [ (mapping.get(n1, n1), mapping.get(n2, n2), k, d.copy()) for (n1, n2, k, d) in G.edges(keys=True, data=True) - ) + ] + + # check for conflicting edge-keys + undirected = not G.is_directed() + seen_edges = set() + for i, (source, target, key, data) in enumerate(new_edges): + while (source, target, key) in seen_edges: + if not isinstance(key, (int, float)): + key = 0 + key += 1 + seen_edges.add((source, target, key)) + if undirected: + seen_edges.add((target, source, key)) + new_edges[i] = (source, target, key, data) + + H.add_edges_from(new_edges) else: H.add_edges_from( (mapping.get(n1, n1), mapping.get(n2, n2), d.copy()) |