r"""
    Get edges between two components or within a single component

    Args:
        graph (nx.Graph): the graph
        nodes1 (set): list of nodes
        nodes2 (set): (default=None) if None it is equivlanet to nodes2=nodes1
        assume_disjoint (bool): skips expensive check to ensure edges arnt
            returned twice (default=False)

    CommandLine:
        python -m utool.util_graph --test-nx_edges_between

    Example:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_graph import *  # NOQA
        >>> import utool as ut
        >>> edges = [
        >>>     (1, 2), (2, 3), (3, 4), (4, 1), (4, 3),  # cc 1234
        >>>     (1, 5), (7, 2), (5, 1),  # cc 567 / 5678
        >>>     (7, 5), (5, 6), (8, 7),
        >>> ]
        >>> digraph = nx.DiGraph(edges)
        >>> graph = nx.Graph(edges)
        >>> nodes1 = [1, 2, 3, 4]
        >>> nodes2 = [5, 6, 7]
        >>> n2 = sorted(nx_edges_between(graph, nodes1, nodes2))
        >>> n4 = sorted(nx_edges_between(graph, nodes1))
        >>> n5 = sorted(nx_edges_between(graph, nodes1, nodes1))
        >>> n1 = sorted(nx_edges_between(digraph, nodes1, nodes2))
        >>> n3 = sorted(nx_edges_between(digraph, nodes1))
        >>> print('n2 == %r' % (n2,))
        >>> print('n4 == %r' % (n4,))
        >>> print('n5 == %r' % (n5,))
        >>> print('n1 == %r' % (n1,))
        >>> print('n3 == %r' % (n3,))
        >>> assert n2 == ([(1, 5), (2, 7)]), '2'
        >>> assert n4 == ([(1, 2), (1, 4), (2, 3), (3, 4)]), '4'
        >>> assert n5 == ([(1, 2), (1, 4), (2, 3), (3, 4)]), '5'
        >>> assert n1 == ([(1, 5), (5, 1), (7, 2)]), '1'
        >>> assert n3 == ([(1, 2), (2, 3), (3, 4), (4, 1), (4, 3)]), '3'
        >>> n6 = sorted(nx_edges_between(digraph, nodes1 + [6], nodes2 + [1, 2], assume_sparse=True))
        >>> print('n6 = %r' % (n6,))
        >>> n6 = sorted(nx_edges_between(digraph, nodes1 + [6], nodes2 + [1, 2], assume_sparse=False))
        >>> print('n6 = %r' % (n6,))
        >>> assert n6 == ([(1, 2), (1, 5), (2, 3), (4, 1), (5, 1), (5, 6), (7, 2)]), '6'

    Timeit:
        from utool.util_graph import *  # NOQA
        # ut.timeit_compare()
        import networkx as nx
        import utool as ut
        graph = nx.fast_gnp_random_graph(1000, .001)
        list(nx.connected_components(graph))
        rng = np.random.RandomState(0)
        nodes1 = set(rng.choice(list(graph.nodes()), 500, replace=False))
        nodes2 = set(graph.nodes()) - nodes1
        edges_between = ut.nx_edges_between
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=False, assume_disjoint=True))
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=False, assume_disjoint=False))
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=True, assume_disjoint=False))
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=True, assume_disjoint=True))

        graph = nx.fast_gnp_random_graph(1000, .1)
        rng = np.random.RandomState(0)
        print(graph.number_of_edges())
        nodes1 = set(rng.choice(list(graph.nodes()), 500, replace=False))
        nodes2 = set(graph.nodes()) - nodes1
        edges_between = ut.nx_edges_between
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=True, assume_disjoint=True))
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=False, assume_disjoint=True))

    Ignore:
        graph = nx.DiGraph(edges)
        graph = nx.Graph(edges)
        nodes1 = [1, 2, 3, 4]
        nodes2 = nodes1

def nx_edges_between(graph, nodes1, nodes2=None, assume_disjoint=False,
                     assume_sparse=True):
    r"""
    Get edges between two components or within a single component

    Args:
        graph (nx.Graph): the graph
        nodes1 (set): list of nodes
        nodes2 (set): (default=None) if None it is equivlanet to nodes2=nodes1
        assume_disjoint (bool): skips expensive check to ensure edges arnt
            returned twice (default=False)

    CommandLine:
        python -m utool.util_graph --test-nx_edges_between

    Example:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_graph import *  # NOQA
        >>> import utool as ut
        >>> edges = [
        >>>     (1, 2), (2, 3), (3, 4), (4, 1), (4, 3),  # cc 1234
        >>>     (1, 5), (7, 2), (5, 1),  # cc 567 / 5678
        >>>     (7, 5), (5, 6), (8, 7),
        >>> ]
        >>> digraph = nx.DiGraph(edges)
        >>> graph = nx.Graph(edges)
        >>> nodes1 = [1, 2, 3, 4]
        >>> nodes2 = [5, 6, 7]
        >>> n2 = sorted(nx_edges_between(graph, nodes1, nodes2))
        >>> n4 = sorted(nx_edges_between(graph, nodes1))
        >>> n5 = sorted(nx_edges_between(graph, nodes1, nodes1))
        >>> n1 = sorted(nx_edges_between(digraph, nodes1, nodes2))
        >>> n3 = sorted(nx_edges_between(digraph, nodes1))
        >>> print('n2 == %r' % (n2,))
        >>> print('n4 == %r' % (n4,))
        >>> print('n5 == %r' % (n5,))
        >>> print('n1 == %r' % (n1,))
        >>> print('n3 == %r' % (n3,))
        >>> assert n2 == ([(1, 5), (2, 7)]), '2'
        >>> assert n4 == ([(1, 2), (1, 4), (2, 3), (3, 4)]), '4'
        >>> assert n5 == ([(1, 2), (1, 4), (2, 3), (3, 4)]), '5'
        >>> assert n1 == ([(1, 5), (5, 1), (7, 2)]), '1'
        >>> assert n3 == ([(1, 2), (2, 3), (3, 4), (4, 1), (4, 3)]), '3'
        >>> n6 = sorted(nx_edges_between(digraph, nodes1 + [6], nodes2 + [1, 2], assume_sparse=True))
        >>> print('n6 = %r' % (n6,))
        >>> n6 = sorted(nx_edges_between(digraph, nodes1 + [6], nodes2 + [1, 2], assume_sparse=False))
        >>> print('n6 = %r' % (n6,))
        >>> assert n6 == ([(1, 2), (1, 5), (2, 3), (4, 1), (5, 1), (5, 6), (7, 2)]), '6'

    Timeit:
        from utool.util_graph import *  # NOQA
        # ut.timeit_compare()
        import networkx as nx
        import utool as ut
        graph = nx.fast_gnp_random_graph(1000, .001)
        list(nx.connected_components(graph))
        rng = np.random.RandomState(0)
        nodes1 = set(rng.choice(list(graph.nodes()), 500, replace=False))
        nodes2 = set(graph.nodes()) - nodes1
        edges_between = ut.nx_edges_between
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=False, assume_disjoint=True))
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=False, assume_disjoint=False))
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=True, assume_disjoint=False))
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=True, assume_disjoint=True))

        graph = nx.fast_gnp_random_graph(1000, .1)
        rng = np.random.RandomState(0)
        print(graph.number_of_edges())
        nodes1 = set(rng.choice(list(graph.nodes()), 500, replace=False))
        nodes2 = set(graph.nodes()) - nodes1
        edges_between = ut.nx_edges_between
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=True, assume_disjoint=True))
        %timeit list(edges_between(graph, nodes1, nodes2, assume_sparse=False, assume_disjoint=True))

    Ignore:
        graph = nx.DiGraph(edges)
        graph = nx.Graph(edges)
        nodes1 = [1, 2, 3, 4]
        nodes2 = nodes1

    """
    if assume_sparse:
        # Method 1 is where we check the intersection of existing edges
        # and the edges in the second set (faster for sparse graphs)

        # helpers nx_edges between
        def _node_combo_lower(graph, both):
            both_lower = set([])
            for u in both:
                neighbs = set(graph.adj[u])
                neighbsBB_lower = neighbs.intersection(both_lower)
                for v in neighbsBB_lower:
                    yield (u, v)
                both_lower.add(u)

        def _node_combo_upper(graph, both):
            both_upper = both.copy()
            for u in both:
                neighbs = set(graph.adj[u])
                neighbsBB_upper = neighbs.intersection(both_upper)
                for v in neighbsBB_upper:
                    yield (u, v)
                both_upper.remove(u)

        def _node_product(graph, only1, only2):
            for u in only1:
                neighbs = set(graph.adj[u])
                neighbs12 = neighbs.intersection(only2)
                for v in neighbs12:
                    yield (u, v)

        # Test for special cases
        if nodes2 is None or nodes2 is nodes1:
            # Case where we just are finding internal edges
            both = set(nodes1)
            if graph.is_directed():
                edge_sets = (
                    _node_combo_upper(graph, both),  # B-to-B (upper)
                    _node_combo_lower(graph, both),  # B-to-B (lower)
                )
            else:
                edge_sets = (
                    _node_combo_upper(graph, both),  # B-to-B (upper)
                )
        elif assume_disjoint:
            # Case where we find edges between disjoint sets
            only1 = set(nodes1)
            only2 = set(nodes2)
            if graph.is_directed():
                edge_sets = (
                    _node_product(graph, only1, only2),  # 1-to-2
                    _node_product(graph, only2, only1),  # 2-to-1
                )
            else:
                edge_sets = (
                    _node_product(graph, only1, only2),  # 1-to-2
                )
        else:
            # Full general case
            nodes1_ = set(nodes1)
            if nodes2 is None:
                nodes2_ = nodes1_
            else:
                nodes2_ = set(nodes2)
            both = nodes1_.intersection(nodes2_)
            only1 = nodes1_ - both
            only2 = nodes2_ - both

            # This could be made faster by avoiding duplicate
            # calls to set(graph.adj[u]) in the helper functions
            if graph.is_directed():
                edge_sets = (
                    _node_product(graph, only1, only2),  # 1-to-2
                    _node_product(graph, only1, both),   # 1-to-B
                    _node_combo_upper(graph, both),      # B-to-B (u)
                    _node_combo_lower(graph, both),      # B-to-B (l)
                    _node_product(graph, both, only1),   # B-to-1
                    _node_product(graph, both, only2),   # B-to-2
                    _node_product(graph, only2, both),   # 2-to-B
                    _node_product(graph, only2, only1),  # 2-to-1
                )
            else:
                edge_sets = (
                    _node_product(graph, only1, only2),  # 1-to-2
                    _node_product(graph, only1, both),   # 1-to-B
                    _node_combo_upper(graph, both),      # B-to-B (u)
                    _node_product(graph, only2, both),   # 2-to-B
                )

        for u, v in it.chain.from_iterable(edge_sets):
            yield u, v

    else:
        # Method 2 is where we enumerate all possible edges and just take the
        # ones that exist (faster for very dense graphs)
        if nodes2 is None or nodes2 is nodes1:
            edge_iter = it.combinations(nodes1, 2)
        else:
            if assume_disjoint:
                # We assume len(isect(nodes1, nodes2)) == 0
                edge_iter = it.product(nodes1, nodes2)
            else:
                # make sure a single edge is not returned twice
                # in the case where len(isect(nodes1, nodes2)) > 0
                nodes1_ = set(nodes1)
                nodes2_ = set(nodes2)
                nodes_isect = nodes1_.intersection(nodes2_)
                nodes_only1 = nodes1_ - nodes_isect
                nodes_only2 = nodes2_ - nodes_isect
                edge_sets = [it.product(nodes_only1, nodes_only2),
                             it.product(nodes_only1, nodes_isect),
                             it.product(nodes_only2, nodes_isect),
                             it.combinations(nodes_isect, 2)]
                edge_iter = it.chain.from_iterable(edge_sets)

        if graph.is_directed():
            for n1, n2 in edge_iter:
                if graph.has_edge(n1, n2):
                    yield n1, n2
                if graph.has_edge(n2, n1):
                    yield n2, n1
        else:
            for n1, n2 in edge_iter:
                if graph.has_edge(n1, n2):
                    yield n1, n2