Skip to main content
`Ctrl`+`K`

# 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}

    @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)

    @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])

    @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])

    @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

    @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

    @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])

    @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