## Mercurial > repos > shellac > sam_consensus_v3

### view env/lib/python3.9/site-packages/networkx/relabel.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

line wrap: on

line source

import networkx as nx __all__ = ["convert_node_labels_to_integers", "relabel_nodes"] def relabel_nodes(G, mapping, copy=True): """Relabel the nodes of the graph G. Parameters ---------- G : graph A NetworkX graph mapping : dictionary A dictionary with the old labels as keys and new labels as values. 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. Examples -------- To create a new graph with nodes relabeled according to a given dictionary: >>> G = nx.path_graph(3) >>> sorted(G) [0, 1, 2] >>> mapping = {0: "a", 1: "b", 2: "c"} >>> H = nx.relabel_nodes(G, mapping) >>> sorted(H) ['a', 'b', 'c'] Nodes can be relabeled with any hashable object, including numbers and strings: >>> import string >>> G = nx.path_graph(26) # nodes are integers 0 through 25 >>> sorted(G)[:3] [0, 1, 2] >>> mapping = dict(zip(G, string.ascii_lowercase)) >>> G = nx.relabel_nodes(G, mapping) # nodes are characters a through z >>> sorted(G)[:3] ['a', 'b', 'c'] >>> mapping = dict(zip(G, range(1, 27))) >>> G = nx.relabel_nodes(G, mapping) # nodes are integers 1 through 26 >>> sorted(G)[:3] [1, 2, 3] To perform a partial in-place relabeling, provide a dictionary mapping only a subset of the nodes, and set the `copy` keyword argument to False: >>> G = nx.path_graph(3) # nodes 0-1-2 >>> mapping = {0: "a", 1: "b"} # 0->'a' and 1->'b' >>> G = nx.relabel_nodes(G, mapping, copy=False) >>> sorted(G, key=str) [2, 'a', 'b'] A mapping can also be given as a function: >>> G = nx.path_graph(3) >>> H = nx.relabel_nodes(G, lambda x: x ** 2) >>> 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. The keyword setting copy=False modifies the graph in place. Relabel_nodes avoids naming collisions by building a directed graph from ``mapping`` which specifies the order of relabelings. Naming collisions, such as a->b, b->c, are ordered such that "b" gets renamed to "c" before "a" gets renamed "b". In cases of circular mappings (e.g. a->b, b->a), modifying the 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 """ # you can pass a function f(old_label)->new_label # but we'll just make a dictionary here regardless if not hasattr(mapping, "__getitem__"): m = {n: mapping(n) for n in G} else: m = mapping if copy: return _relabel_copy(G, m) else: return _relabel_inplace(G, m) def _relabel_inplace(G, mapping): old_labels = set(mapping.keys()) new_labels = set(mapping.values()) if len(old_labels & new_labels) > 0: # labels sets overlap # can we topological sort and still do the relabeling? D = nx.DiGraph(list(mapping.items())) D.remove_edges_from(nx.selfloop_edges(D)) try: nodes = reversed(list(nx.topological_sort(D))) except nx.NetworkXUnfeasible as e: raise nx.NetworkXUnfeasible( "The node label sets are overlapping and no ordering can " "resolve the mapping. Use copy=True." ) from e else: # non-overlapping label sets nodes = old_labels multigraph = G.is_multigraph() directed = G.is_directed() for old in nodes: try: new = mapping[old] except KeyError: continue if new == old: continue try: G.add_node(new, **G.nodes[old]) except KeyError as e: raise KeyError(f"Node {old} is not in the graph") from e if multigraph: new_edges = [ (new, new if old == target else target, key, data) for (_, target, key, data) in G.edges(old, data=True, keys=True) ] if directed: new_edges += [ (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) for (_, target, data) in G.edges(old, data=True) ] if directed: new_edges += [ (new if old == source else source, new, data) for (source, _, data) in G.in_edges(old, data=True) ] G.remove_node(old) G.add_edges_from(new_edges) return G def _relabel_copy(G, mapping): H = G.__class__() 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(): 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()) for (n1, n2, d) in G.edges(data=True) ) H.graph.update(G.graph) return H def convert_node_labels_to_integers( G, first_label=0, ordering="default", label_attribute=None ): """Returns a copy of the graph G with the nodes relabeled using consecutive integers. Parameters ---------- G : graph A NetworkX graph first_label : int, optional (default=0) An integer specifying the starting offset in numbering nodes. The new integer labels are numbered first_label, ..., n-1+first_label. ordering : string "default" : inherit node ordering from G.nodes() "sorted" : inherit node ordering from sorted(G.nodes()) "increasing degree" : nodes are sorted by increasing degree "decreasing degree" : nodes are sorted by decreasing degree label_attribute : string, optional (default=None) Name of node attribute to store old label. If None no attribute is created. Notes ----- Node and edge attribute data are copied to the new (relabeled) graph. There is no guarantee that the relabeling of nodes to integers will give the same two integers for two (even identical graphs). Use the `ordering` argument to try to preserve the order. See Also -------- relabel_nodes """ N = G.number_of_nodes() + first_label if ordering == "default": mapping = dict(zip(G.nodes(), range(first_label, N))) elif ordering == "sorted": nlist = sorted(G.nodes()) mapping = dict(zip(nlist, range(first_label, N))) elif ordering == "increasing degree": dv_pairs = [(d, n) for (n, d) in G.degree()] dv_pairs.sort() # in-place sort from lowest to highest degree mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N))) elif ordering == "decreasing degree": dv_pairs = [(d, n) for (n, d) in G.degree()] dv_pairs.sort() # in-place sort from lowest to highest degree dv_pairs.reverse() mapping = dict(zip([n for d, n in dv_pairs], range(first_label, N))) else: raise nx.NetworkXError(f"Unknown node ordering: {ordering}") H = relabel_nodes(G, mapping) # create node attribute with the old label if label_attribute is not None: nx.set_node_attributes(H, {v: k for k, v in mapping.items()}, label_attribute) return H