Find approximate minimum number of connected components possible
    Each edge represents that two nodes must be separated

    This code doesn't solve the problem. The problem is NP-complete and
    reduces to minimum clique cover (MCC). This is only an approximate
    solution. Not sure what the approximation ratio is.

    CommandLine:
        python -m utool.util_graph approx_min_num_components

    Example:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_graph import *  # NOQA
        >>> import utool as ut
        >>> nodes = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        >>> edges = [(1, 2), (2, 3), (3, 1),
        >>>          (4, 5), (5, 6), (6, 4),
        >>>          (7, 8), (8, 9), (9, 7),
        >>>          (1, 4), (4, 7), (7, 1),
        >>>         ]
        >>> g_pos = nx.Graph()
        >>> g_pos.add_edges_from(edges)
        >>> g_neg = nx.complement(g_pos)
        >>> #import plottool as pt
        >>> #pt.qt4ensure()
        >>> #pt.show_nx(g_pos)
        >>> #pt.show_nx(g_neg)
        >>> negative_edges = g_neg.edges()
        >>> nodes = [1, 2, 3, 4, 5, 6, 7]
        >>> negative_edges = [(1, 2), (2, 3), (4, 5)]
        >>> result = approx_min_num_components(nodes, negative_edges)
        >>> print(result)
        2

def approx_min_num_components(nodes, negative_edges):
    """
    Find approximate minimum number of connected components possible
    Each edge represents that two nodes must be separated

    This code doesn't solve the problem. The problem is NP-complete and
    reduces to minimum clique cover (MCC). This is only an approximate
    solution. Not sure what the approximation ratio is.

    CommandLine:
        python -m utool.util_graph approx_min_num_components

    Example:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_graph import *  # NOQA
        >>> import utool as ut
        >>> nodes = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        >>> edges = [(1, 2), (2, 3), (3, 1),
        >>>          (4, 5), (5, 6), (6, 4),
        >>>          (7, 8), (8, 9), (9, 7),
        >>>          (1, 4), (4, 7), (7, 1),
        >>>         ]
        >>> g_pos = nx.Graph()
        >>> g_pos.add_edges_from(edges)
        >>> g_neg = nx.complement(g_pos)
        >>> #import plottool as pt
        >>> #pt.qt4ensure()
        >>> #pt.show_nx(g_pos)
        >>> #pt.show_nx(g_neg)
        >>> negative_edges = g_neg.edges()
        >>> nodes = [1, 2, 3, 4, 5, 6, 7]
        >>> negative_edges = [(1, 2), (2, 3), (4, 5)]
        >>> result = approx_min_num_components(nodes, negative_edges)
        >>> print(result)
        2
    """
    import utool as ut
    num = 0
    g_neg = nx.Graph()
    g_neg.add_nodes_from(nodes)
    g_neg.add_edges_from(negative_edges)

    # Collapse all nodes with degree 0
    if nx.__version__.startswith('2'):
        deg0_nodes = [n for n, d in g_neg.degree() if d == 0]
    else:
        deg0_nodes = [n for n, d in g_neg.degree_iter() if d == 0]

    for u, v in ut.itertwo(deg0_nodes):
        nx_contracted_nodes(g_neg, v, u, inplace=True)
        # g_neg = nx.contracted_nodes(g_neg, v, u, self_loops=False)

    # Initialize unused nodes to be everything
    unused = list(g_neg.nodes())
    # complement of the graph contains all possible positive edges
    g_pos = nx.complement(g_neg)

    if False:
        from networkx.algorithms.approximation import clique
        maxiset, cliques = clique.clique_removal(g_pos)
        num = len(cliques)
        return num

    # Iterate until we have used all nodes
    while len(unused) > 0:
        # Seed a new "minimum component"
        num += 1
        # Grab a random unused node n1
        #idx1 = np.random.randint(0, len(unused))
        idx1 = 0
        n1 = unused[idx1]
        unused.remove(n1)
        neigbs = list(g_pos.neighbors(n1))
        neigbs = ut.isect(neigbs, unused)
        while len(neigbs) > 0:
            # Find node n2, that n1 could be connected to
            #idx2 = np.random.randint(0, len(neigbs))
            idx2 = 0
            n2 = neigbs[idx2]
            unused.remove(n2)
            # Collapse negative information of n1 and n2
            g_neg = nx.contracted_nodes(g_neg, n1, n2)
            # Compute new possible positive edges
            g_pos = nx.complement(g_neg)
            # Iterate until n1 has no more possible connections
            neigbs = list(g_pos.neighbors(n1))
            neigbs = ut.isect(neigbs, unused)
    print('num = %r' % (num,))
    return num