Source code for networkx.algorithms.operators.binary

"""
Operations on graphs including union, intersection, difference.
"""

import networkx as nx

__all__ = [
    "union",
    "compose",
    "disjoint_union",
    "intersection",
    "difference",
    "symmetric_difference",
    "full_join",
]
_G_H = {"G": 0, "H": 1}


[docs] @nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True) def union(G, H, rename=()): """Combine graphs G and H. The names of nodes must be unique. A name collision between the graphs will raise an exception. A renaming facility is provided to avoid name collisions. Parameters ---------- G, H : graph A NetworkX graph rename : iterable , optional Node names of G and H can be changed by specifying the tuple rename=('G-','H-') (for example). Node "u" in G is then renamed "G-u" and "v" in H is renamed "H-v". Returns ------- U : A union graph with the same type as G. See Also -------- compose :func:`~networkx.Graph.update` disjoint_union Notes ----- To combine graphs that have common nodes, consider compose(G, H) or the method, Graph.update(). disjoint_union() is similar to union() except that it avoids name clashes by relabeling the nodes with sequential integers. Edge and node attributes are propagated from G and H to the union graph. Graph attributes are also propagated, but if they are present in both G and H, then the value from H is used. Examples -------- >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)]) >>> H = nx.Graph([(0, 1), (0, 3), (1, 3), (1, 2)]) >>> U = nx.union(G, H, rename=("G", "H")) >>> U.nodes NodeView(('G0', 'G1', 'G2', 'H0', 'H1', 'H3', 'H2')) >>> U.edges EdgeView([('G0', 'G1'), ('G0', 'G2'), ('G1', 'G2'), ('H0', 'H1'), ('H0', 'H3'), ('H1', 'H3'), ('H1', 'H2')]) """ return nx.union_all([G, H], rename)
[docs] @nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True) def disjoint_union(G, H): """Combine graphs G and H. The nodes are assumed to be unique (disjoint). This algorithm automatically relabels nodes to avoid name collisions. Parameters ---------- G,H : graph A NetworkX graph Returns ------- U : A union graph with the same type as G. See Also -------- union compose :func:`~networkx.Graph.update` Notes ----- A new graph is created, of the same class as G. It is recommended that G and H be either both directed or both undirected. The nodes of G are relabeled 0 to len(G)-1, and the nodes of H are relabeled len(G) to len(G)+len(H)-1. Renumbering forces G and H to be disjoint, so no exception is ever raised for a name collision. To preserve the check for common nodes, use union(). Edge and node attributes are propagated from G and H to the union graph. Graph attributes are also propagated, but if they are present in both G and H, then the value from H is used. To combine graphs that have common nodes, consider compose(G, H) or the method, Graph.update(). Examples -------- >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)]) >>> H = nx.Graph([(0, 3), (1, 2), (2, 3)]) >>> G.nodes[0]["key1"] = 5 >>> H.nodes[0]["key2"] = 10 >>> U = nx.disjoint_union(G, H) >>> U.nodes(data=True) NodeDataView({0: {'key1': 5}, 1: {}, 2: {}, 3: {'key2': 10}, 4: {}, 5: {}, 6: {}}) >>> U.edges EdgeView([(0, 1), (0, 2), (1, 2), (3, 4), (4, 6), (5, 6)]) """ return nx.disjoint_union_all([G, H])
[docs] @nx._dispatchable(graphs=_G_H, returns_graph=True) def intersection(G, H): """Returns a new graph that contains only the nodes and the edges that exist in both G and H. Parameters ---------- G,H : graph A NetworkX graph. G and H can have different node sets but must be both graphs or both multigraphs. Raises ------ NetworkXError If one is a MultiGraph and the other one is a graph. Returns ------- GH : A new graph with the same type as G. Notes ----- Attributes from the graph, nodes, and edges are not copied to the new graph. If you want a new graph of the intersection of G and H with the attributes (including edge data) from G use remove_nodes_from() as follows >>> G = nx.path_graph(3) >>> H = nx.path_graph(5) >>> R = G.copy() >>> R.remove_nodes_from(n for n in G if n not in H) >>> R.remove_edges_from(e for e in G.edges if e not in H.edges) Examples -------- >>> G = nx.Graph([(0, 1), (0, 2), (1, 2)]) >>> H = nx.Graph([(0, 3), (1, 2), (2, 3)]) >>> R = nx.intersection(G, H) >>> R.nodes NodeView((0, 1, 2)) >>> R.edges EdgeView([(1, 2)]) """ return nx.intersection_all([G, H])
[docs] @nx._dispatchable(graphs=_G_H, returns_graph=True) def difference(G, H): """Returns a new graph that contains the edges that exist in G but not in H. The node sets of H and G must be the same. Parameters ---------- G,H : graph A NetworkX graph. G and H must have the same node sets. Returns ------- D : A new graph with the same type as G. Notes ----- Attributes from the graph, nodes, and edges are not copied to the new graph. If you want a new graph of the difference of G and H with the attributes (including edge data) from G use remove_nodes_from() as follows: >>> G = nx.path_graph(3) >>> H = nx.path_graph(5) >>> R = G.copy() >>> R.remove_nodes_from(n for n in G if n in H) Examples -------- >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3)]) >>> H = nx.Graph([(0, 1), (1, 2), (0, 3)]) >>> R = nx.difference(G, H) >>> R.nodes NodeView((0, 1, 2, 3)) >>> R.edges EdgeView([(0, 2), (1, 3)]) """ # create new graph if not G.is_multigraph() == H.is_multigraph(): raise nx.NetworkXError("G and H must both be graphs or multigraphs.") R = nx.create_empty_copy(G, with_data=False) if set(G) != set(H): raise nx.NetworkXError("Node sets of graphs not equal") if G.is_multigraph(): edges = G.edges(keys=True) else: edges = G.edges() for e in edges: if not H.has_edge(*e): R.add_edge(*e) return R
[docs] @nx._dispatchable(graphs=_G_H, returns_graph=True) def symmetric_difference(G, H): """Returns new graph with edges that exist in either G or H but not both. The node sets of H and G must be the same. Parameters ---------- G,H : graph A NetworkX graph. G and H must have the same node sets. Returns ------- D : A new graph with the same type as G. Notes ----- Attributes from the graph, nodes, and edges are not copied to the new graph. Examples -------- >>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3)]) >>> H = nx.Graph([(0, 1), (1, 2), (0, 3)]) >>> R = nx.symmetric_difference(G, H) >>> R.nodes NodeView((0, 1, 2, 3)) >>> R.edges EdgeView([(0, 2), (0, 3), (1, 3)]) """ # create new graph if not G.is_multigraph() == H.is_multigraph(): raise nx.NetworkXError("G and H must both be graphs or multigraphs.") R = nx.create_empty_copy(G, with_data=False) if set(G) != set(H): raise nx.NetworkXError("Node sets of graphs not equal") gnodes = set(G) # set of nodes in G hnodes = set(H) # set of nodes in H nodes = gnodes.symmetric_difference(hnodes) R.add_nodes_from(nodes) if G.is_multigraph(): edges = G.edges(keys=True) else: edges = G.edges() # we could copy the data here but then this function doesn't # match intersection and difference for e in edges: if not H.has_edge(*e): R.add_edge(*e) if H.is_multigraph(): edges = H.edges(keys=True) else: edges = H.edges() for e in edges: if not G.has_edge(*e): R.add_edge(*e) return R
[docs] @nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True) def compose(G, H): """Compose graph G with H by combining nodes and edges into a single graph. The node sets and edges sets do not need to be disjoint. Composing preserves the attributes of nodes and edges. Attribute values from H take precedent over attribute values from G. Parameters ---------- G, H : graph A NetworkX graph Returns ------- C: A new graph with the same type as G See Also -------- :func:`~networkx.Graph.update` union disjoint_union Notes ----- It is recommended that G and H be either both directed or both undirected. For MultiGraphs, the edges are identified by incident nodes AND edge-key. This can cause surprises (i.e., edge `(1, 2)` may or may not be the same in two graphs) if you use MultiGraph without keeping track of edge keys. If combining the attributes of common nodes is not desired, consider union(), which raises an exception for name collisions. Examples -------- >>> G = nx.Graph([(0, 1), (0, 2)]) >>> H = nx.Graph([(0, 1), (1, 2)]) >>> R = nx.compose(G, H) >>> R.nodes NodeView((0, 1, 2)) >>> R.edges EdgeView([(0, 1), (0, 2), (1, 2)]) By default, the attributes from `H` take precedent over attributes from `G`. If you prefer another way of combining attributes, you can update them after the compose operation: >>> G = nx.Graph([(0, 1, {"weight": 2.0}), (3, 0, {"weight": 100.0})]) >>> H = nx.Graph([(0, 1, {"weight": 10.0}), (1, 2, {"weight": -1.0})]) >>> nx.set_node_attributes(G, {0: "dark", 1: "light", 3: "black"}, name="color") >>> nx.set_node_attributes(H, {0: "green", 1: "orange", 2: "yellow"}, name="color") >>> GcomposeH = nx.compose(G, H) Normally, color attribute values of nodes of GcomposeH come from H. We can workaround this as follows: >>> node_data = { ... n: G.nodes[n]["color"] + " " + H.nodes[n]["color"] ... for n in G.nodes & H.nodes ... } >>> nx.set_node_attributes(GcomposeH, node_data, "color") >>> print(GcomposeH.nodes[0]["color"]) dark green >>> print(GcomposeH.nodes[3]["color"]) black Similarly, we can update edge attributes after the compose operation in a way we prefer: >>> edge_data = { ... e: G.edges[e]["weight"] * H.edges[e]["weight"] for e in G.edges & H.edges ... } >>> nx.set_edge_attributes(GcomposeH, edge_data, "weight") >>> print(GcomposeH.edges[(0, 1)]["weight"]) 20.0 >>> print(GcomposeH.edges[(3, 0)]["weight"]) 100.0 """ return nx.compose_all([G, H])
[docs] @nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True) def full_join(G, H, rename=(None, None)): """Returns the full join of graphs G and H. Full join is the union of G and H in which all edges between G and H are added. The node sets of G and H must be disjoint, otherwise an exception is raised. Parameters ---------- G, H : graph A NetworkX graph rename : tuple , default=(None, None) Node names of G and H can be changed by specifying the tuple rename=('G-','H-') (for example). Node "u" in G is then renamed "G-u" and "v" in H is renamed "H-v". Returns ------- U : The full join graph with the same type as G. Notes ----- It is recommended that G and H be either both directed or both undirected. If G is directed, then edges from G to H are added as well as from H to G. Note that full_join() does not produce parallel edges for MultiGraphs. The full join operation of graphs G and H is the same as getting their complement, performing a disjoint union, and finally getting the complement of the resulting graph. Graph, edge, and node attributes are propagated from G and H to the union graph. If a graph attribute is present in both G and H the value from H is used. Examples -------- >>> G = nx.Graph([(0, 1), (0, 2)]) >>> H = nx.Graph([(3, 4)]) >>> R = nx.full_join(G, H, rename=("G", "H")) >>> R.nodes NodeView(('G0', 'G1', 'G2', 'H3', 'H4')) >>> R.edges EdgeView([('G0', 'G1'), ('G0', 'G2'), ('G0', 'H3'), ('G0', 'H4'), ('G1', 'H3'), ('G1', 'H4'), ('G2', 'H3'), ('G2', 'H4'), ('H3', 'H4')]) See Also -------- union disjoint_union """ R = union(G, H, rename) def add_prefix(graph, prefix): if prefix is None: return graph def label(x): return f"{prefix}{x}" return nx.relabel_nodes(graph, label) G = add_prefix(G, rename[0]) H = add_prefix(H, rename[1]) for i in G: for j in H: R.add_edge(i, j) if R.is_directed(): for i in H: for j in G: R.add_edge(i, j) return R