def setUp(self):
     self.Gnp = nx.gnp_random_graph(20, 0.8)
     self.Anp = _AntiGraph(nx.complement(self.Gnp))
     self.Gd = nx.davis_southern_women_graph()
     self.Ad = _AntiGraph(nx.complement(self.Gd))
     self.Gk = nx.karate_club_graph()
     self.Ak = _AntiGraph(nx.complement(self.Gk))
     self.GA = [(self.Gnp, self.Anp),
                (self.Gd, self.Ad),
                (self.Gk, self.Ak)]

def test_complement(testgraph):
    """
    Test the Complement of the graph are same
    """

    a = nx.complement(testgraph[0])
    b = sg.digraph_operations.complement(testgraph[2])
    c = nx.complement(testgraph[1])
    d = sg.digraph_operations.complement(testgraph[3])
    digraph_equals(a, b)
    digraph_equals(c, d)

def heuristic_independent_set_finder(Graph,Weight_vector,first_node,second_node_index):

    first_node_neighborhood=Graph[first_node].keys()

    second_node=first_node_neighborhood[second_node_index]
    second_node_neighborhood=Graph[second_node].keys()

    #print 'second node',second_node
    #print 'first node_neighborhood', first_node_neighborhood
    #print 'second node_neighborhood', second_node_neighborhood

    first_node_neighborhood_set=set(first_node_neighborhood)
    second_node_neighborhood_set=set(second_node_neighborhood)

    common_neighbors=first_node_neighborhood_set.intersection(second_node_neighborhood_set)

    #print 'common neighbors:', common_neighbors

    induced_subgraph=nx.subgraph(Graph,common_neighbors)
    complement_induced_subgraph=nx.complement(induced_subgraph)

    #print 'induced_subgraph.nodes()', induced_subgraph.nodes()
    #print 'induced_subgraph.edges()', induced_subgraph.edges()
    #print 'complement_induced_subgraph.nodes()', complement_induced_subgraph.nodes()
    #print 'complement_induced_subgraph.edges()', complement_induced_subgraph.edges()

    current_complement_induced_subgraph=nx.complement(induced_subgraph)
    current_independent_set=[]

    print current_complement_induced_subgraph.nodes()
    print current_complement_induced_subgraph.edges()

    while (len(current_complement_induced_subgraph.edges())>0):
	current_minimum_degree_node=sort_by_degree(current_complement_induced_subgraph)[0][0]
	current_minimum_degree_node_neighborhood=current_complement_induced_subgraph[current_minimum_degree_node].keys()
	current_independent_set.append(current_minimum_degree_node)
	current_complement_induced_subgraph.remove_nodes_from(current_minimum_degree_node_neighborhood)
	current_complement_induced_subgraph.remove_node(current_minimum_degree_node)

	print current_minimum_degree_node
	print current_minimum_degree_node_neighborhood
	print current_independent_set
	print current_complement_induced_subgraph.nodes()

    current_independent_set.extend(current_complement_induced_subgraph.nodes())
    current_independent_set.extend([first_node,second_node])
    maximum_clique=current_independent_set
    return maximum_clique

 def k_color(self):
     '''
     _claw_and_co_free
     finds if graph G is k-is_critical for some k
     requires the G to be claw and co-claw free
     Parameters:
         None
     Returns:
         int: the k-is_critical graph
         None: if graph is not k-is_critical
     '''
     clique = self.clique_number()
     print("Clique number:", clique)
     print(self._g.nodes())
     k = None
     if clique is None:
         # is not a clique
         cycle = self.cycle_nodes()
         if len(cycle) > 3:
             cycle.pop() # don't need the full cycle path just the vertices
         if len(cycle) == 0 or len(cycle) % 2 == 0:
             # no cycle or even hole so done
             k = None
         elif len(cycle) > 5:
             # odd-hole
             if len(cycle) == len(self._g.nodes()):
                 # just an odd-hole
                 k = 3
         if k is None:
             # check for anti-hole
             co_g = DalGraph(nx.complement(nx.Graph.copy(self._g)))
             cycle = co_g.cycle_nodes()
             if len(cycle) > 3:
                 cycle.pop() # don't need the full cycle path just the vertices
             if len(cycle) == 0 or len(cycle) % 2 == 0:
                 # even hole or no hole
                 k = None
             else:
                 co_g._g = nx.complement(co_g._g)
                 co_g.remove_vertices(cycle)
                 k2 = co_g.k_color()
                 if k2 is not None:
                     k = math.ceil(len(cycle) / 2) + k2
                 else:
                     k = None
     else:
         k = clique
     return k

def inter_community_non_edges(G, partition):
    """Returns the number of inter-community non-edges according to the
    given partition of the nodes of `G`.

    `G` must be a NetworkX graph.

    `partition` must be a partition of the nodes of `G`.

    A *non-edge* is a pair of nodes (undirected if `G` is undirected)
    that are not adjacent in `G`. The *inter-community non-edges* are
    those non-edges on a pair of nodes in different blocks of the
    partition.

    Implementation note: this function creates two intermediate graphs,
    which may require up to twice the amount of memory as required to
    store `G`.

    """
    # Alternate implementation that does not require constructing two
    # new graph objects (but does require constructing an affiliation
    # dictionary):
    #
    #     aff = dict(chain.from_iterable(((v, block) for v in block)
    #                                    for block in partition))
    #     return sum(1 for u, v in nx.non_edges(G) if aff[u] != aff[v])
    #
    return inter_community_edges(nx.complement(G), partition)

def add_edge(g,m):
    compl=nx.complement(g)
    if len(compl.edges())>=m:
        aedge=random.sample(compl.edges(),m)
        return aedge
    else:
        print "not enough nodes to add m edges, please check m"

def modularDecomposition(G):
    """ Computes the cotree of a cograph.
    This is done by modular decomposition - http://en.wikipedia.org/wiki/Modular_decomposition
    As the algorithm only works for initial connected graphs, for non-connected graphs the algorithm is applied to the complement graph.

    Parameters
    ----------
    G : graph
        A networkx graph
        As cotrees can only be computed for cographs an error is raised if the input graph is not a cograph

    Returns
    -------
    out : graph
        The resulting cotree
    """
    if hasattr(G, 'graph') and isinstance(G.graph, dict):
        Gres = nx.DiGraph()
        if nx.is_connected(G):
            decomp(G, Gres, 1)
        else:
            # The cotree T' of G', is exactly T with 0 and 1 nodes interchanged.
            # http://www.lirmm.fr/~paul/Biblio/Postscript/wg03.pdf Section 1.2 observation 2
            decomp(nx.complement(G), Gres, 0)
        return Gres
    else:
        raise nx.NetworkXError("Input is not a correct NetworkX graph.")

def evolve(g, p_c, p):
    """ 

   Do one markovian evolution where existing edge disappears with prob
p (stays with prob 1-p) and a non-existing one appears with prob q
(and stays off with prob 1-q). Arbitrary values of p and q however
change the density of edges in the cluster. It turns out however if we
set q= p*p_c/(1-p_c) then the density of the cluster stays the same on
average.

    """
    g_new = nx.Graph()
    for e in g.edges_iter(data=True):
        if random.random() <= 1-p:  # edge remains on with prob 1-p
            g_new.add_edge(e[0], e[1], weight=1.0)
        

    # q is chosen so as to keep density invariant
    # set fraction of edges turning on equal to those turning off
    # Solve p *p_c = (1-p_c) q
    # Check this logic!!

    # note p_c <= 1/(1+p) for q <= 1
    q = (p_c*p)/(1-p_c)

    g_complement = nx.complement(g)  
    for e in g_complement.edges_iter():
        if random.random() <= q:  # add edge from g_complement with prob q
            g_new.add_edge(e[0], e[1], weight=1.0)

    return g_new

def SingleEdgeRewiring(Input_Graph):
	
	max_count=1000
	N=Input_Graph.order()
	m=Input_Graph.size()
	G=Input_Graph.copy()
	
	#############################################################################
	#############################DOUBLE REWIRINGS################################
	#############################################################################
	
	EdgeList=G.edges()
	K=nx.complement(G)
	NonEdgeList=K.edges()
	
	ConnectedGraph=0
	trial_count=0
	while ConnectedGraph==0:
		H=G.copy()
		trial_count+=1
		OldEdge=random.choice(EdgeList)
		NewEdge=random.choice(NonEdgeList)		
		H.remove_edges_from([OldEdge])
		H.add_edges_from([NewEdge])
		
		if nx.is_connected(H):ConnectedGraph=1
		if trial_count>max_count:
			print 'A connected graph could not be found.'
			return -1
			break
			
	return H

def independence_number(graph):
    """
    Compute the independence number of 'graph'.
    """
    if graph.number_of_nodes() == 0:
        return 0
    else:
        return graph_clique_number(complement(graph))

def make_2K2():
    '''
    a function which assembles a 2K2
    Parameters:
        None
    Returns:
        g: 2K2 graph (network)
    '''
    return nx.complement(make_cycle(4))

 def solve(self, *args, **kw):
     import networkx as nx
     graph = nx.complement(self.graph)
     from openopt import STAB
     KW = self.__init_kwargs
     KW.update(kw)
     P = STAB(graph, **KW)
     r = P.solve(*args)
     return r

def make_co_cycle(n):
    '''
    a function the creates an complement of a cycle of size n
    Parameters:
        n: the size of the anti cycle
    Returns:
        co_cycle: a networkx graph (networkx)
    '''
    return nx.complement(make_cycle(n))

def isCographAux(G):
    modules = nx.connected_component_subgraphs(nx.complement(G))
    if len(modules) == 1:
        if len(modules[0]) == 1:
            # return leaf node
            return True
        else:
            return False
    else:
        return all(isCographAux(module) for module in modules)

def make_co_claw():
    '''
    make_co_claw
    assembles a co-claw
    Parameters:
        None
    Returns:
        co_claw: the co_claw (Graph)
    '''
    return nx.complement(make_claw())

def even_hole_free(G):
    i_set = graph_clique_number(complement(G))
    free = True
    i = 4
    while i <= i_set * 2 and free:
        g = make_cycle(i)
        if induced_subgraph(G, g):
            free = False
        i += 2
    return free

def make_co_diamond():
    '''
    make_co_diamond
    assembles a co-diamond
    Parameters:
        None
    Returns:
        co_diamond: the co-diamond graph (networkx)
    '''
    return nx.complement(make_diamond())

 def alpha_number(self):
     '''
     returns the stabe set number of the graph
         Parameters:
             None
         Returns:
             stable: the max size of the stable set (int)
                     None if no stable set
     '''
     complement = nx.complement(self._g)
     return len(list(nx.find_cliques(complement)))

def even_hole_free(G):
    i_set = graph_clique_number(complement(G))
    free = None
    i = 4
    while i <= i_set * 2 and free is None:
        g = make_cycle(i)
        induced = induced_subgraph(G, g) 
        if induced is not None:
            free = induced
        i += 2
    return free

def balance_triade_in_graph(G, triade, p):
    edges = triade.edges().copy()
    nodes = triade.nodes().copy()
    if len(edges) == 0: 
        G.add_edge(*np.random.choice(nodes, size=2, replace=False))
    else:
        if np.random.random() < p:
            comp = nx.complement(triade)
            G.add_edge(*comp.edges()[0])
        else:
            G.remove_edge(*rd.choice(edges))