def generate_simple_graph(sfunction, N, avg_degree):
    """generate a simple random graph with sfunction degree sequence"""

    graphical_deg_seq = False
    is_connected_graph = False
    while is_connected_graph == False:
        while graphical_deg_seq == False:
            seq = sfunction(N, avg_degree, seqtype="simple_degree")
            graphical_deg_seq = nx.is_valid_degree_sequence(seq)
        G = nx.havel_hakimi_graph(seq)
        G.remove_edges_from(G.selfloop_edges())

        if not nx.is_connected(G):
            try:
                connect_simple_graph(G)
                is_connected_graph = True
                randomize_graph(G)
            except (IndexError):
                is_connected_graph = False

        if not nx.is_connected(G):
            try:
                connect_simple_graph(G)
                is_connected_graph = True

            except (IndexError):
                is_connected_graph = False
                graphical_deg_seq = False

    return G

def test_brandes_erlebach_book():
    # Figure 1 chapter 7: Connectivity
    # http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
    G = nx.Graph()
    G.add_edges_from([(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 6), (3, 4),
                      (3, 6), (4, 6), (4, 7), (5, 7), (6, 8), (6, 9), (7, 8),
                      (7, 10), (8, 11), (9, 10), (9, 11), (10, 11)])
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge cutsets
        assert_equal(3, len(nx.minimum_edge_cut(G, 1, 11, **kwargs)),
                     msg=msg.format(flow_func.__name__))
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
        # Node 5 has only two edges
        assert_equal(2, len(edge_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_edges_from(edge_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
        # node cuts
        assert_equal(set([6, 7]), minimum_st_node_cut(G, 1, 11, **kwargs),
                     msg=msg.format(flow_func.__name__))
        assert_equal(set([6, 7]), nx.minimum_node_cut(G, 1, 11, **kwargs),
                     msg=msg.format(flow_func.__name__))
        node_cut = nx.minimum_node_cut(G, **kwargs)
        assert_equal(2, len(node_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_nodes_from(node_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))

def number_of_3partition(G):
    edge_list = G.edges()
    count = 0
    for n in powerset(range(len(G.nodes()))):
        if len(n) == 0:
            continue
        H1 = G.subgraph(n)
        if not nx.is_connected(H1):
            continue
        nbar1 = []
        for i in range(0, len(G.nodes())):
            if i not in n:
                nbar1.append(i)
        for n2 in powerset(nbar1):
            if len(n2) == 0:
                continue
            H2 = G.subgraph(n2)
            if not nx.is_connected(H2):
                continue
            nbar = []
            for i in range(0, len(G.nodes())):
                if i not in n and i not in n2:
                    nbar.append(i)
            if len(nbar) == 0:
                continue
            H3 = G.subgraph(nbar)
            if not nx.is_connected(H3):
                continue
            count += 1
    return count / 6

def test_solution(sets, G, new_G):
    for g in sets.values():
        if nx.is_connected(G.subgraph(g)) and \
        not nx.is_connected(new_G.subgraph(g)) and len(g)>=2:
            print 'Disconnect:',g, G.subgraph(g).edges(), new_G.subgraph(g).edges()
            return False
    return True

    def test_vertex_separator(self):
        sep, part1, part2 = nxmetis.vertex_separator(self.G)

        # The two separator nodes must not be present in the
        # two bisected chains
        nose.tools.ok_(sep[0] not in part1)
        nose.tools.ok_(sep[0] not in part2)
        nose.tools.ok_(sep[1] not in part1)
        nose.tools.ok_(sep[1] not in part2)

        # There should be two different separator nodes
        nose.tools.assert_equal(len(sep), 2)
        nose.tools.assert_not_equal(sep[0], sep[1])

        # The lists should be exhaustive with the node list of the Graph
        nose.tools.assert_equal(set(sep) | set(part1) | set(part2),
                                set(self.G))

        # The parts must be disjoint sets
        nose.tools.assert_equal(set(), set(part1) & set(part2))

        # Non-empty set
        nose.tools.assert_not_equal(len(part1), 0)
        nose.tools.assert_not_equal(len(part2), 0)

        # Duplicate-free
        nose.tools.assert_equal(len(part1), len(set(part1)))
        nose.tools.assert_equal(len(part2), len(set(part2)))

        # Connected
        nose.tools.ok_(nx.is_connected(self.G.subgraph(part1)))
        nose.tools.ok_(nx.is_connected(self.G.subgraph(part2)))

 def generateNewExtractionPool(self, network):
     #Generate extraction candidates for each key in the extraction map
     import time
     totalstart = time.time()
     self.extractionPool = {}
     connected = 0
     
     #***************************************
     for element in self.extractionMap:
         if nx.is_connected(element[0]):
             connected += 1
     print "Total number of extracted subgraphs: " + str(len(self.extractionMap))
     print "Number of connected subgraphs: " + str(connected)   
     #***************************************
     
     for element in self.extractionMap: 
         substart = time.time()
         if nx.is_connected(element[0]):
             connected += 1
         extractionCandidates = self.util.findSubgraphInstances(network, element[0])
         print "Subpool size: " + str(len(extractionCandidates))
         subelapsed = time.time() - substart
         print "Subpool elapsed time: " + str(subelapsed)
         self.extractionPool[element[0]] = extractionCandidates
     
     print "Number of connected subgraphs: " + str(connected) 
     totalelapsed = time.time()- totalstart
     print "Total elapsed pool time: " + str(totalelapsed)
     import sys
     print "Total size of extraction pool in Bytes: " + str(sys.getsizeof(self.extractionPool))

def test_white_harary_paper():
    # Figure 1b white and harary (2001)
    # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
    # A graph with high adhesion (edge connectivity) and low cohesion
    # (node connectivity)
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.remove_node(7)
    for i in range(4, 7):
        G.add_edge(0, i)
    G = nx.disjoint_union(G, nx.complete_graph(4))
    G.remove_node(G.order() - 1)
    for i in range(7, 10):
        G.add_edge(0, i)
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge cuts
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
        assert_equal(3, len(edge_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_edges_from(edge_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
        # node cuts
        node_cut = nx.minimum_node_cut(G, **kwargs)
        assert_equal(set([0]), node_cut, msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_nodes_from(node_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))

def test_edge_cutset_random_graphs():
    for i in range(5):
        G = nx.fast_gnp_random_graph(50,0.2)
        if not nx.is_connected(G):
            ccs = iter(nx.connected_components(G))
            start = next(ccs)[0]
            G.add_edges_from( (start,c[0]) for c in ccs )
        cutset = nx.minimum_edge_cut(G)
        assert_equal(nx.edge_connectivity(G), len(cutset))
        G.remove_edges_from(cutset)
        assert_false(nx.is_connected(G))

def main():
    LOG = True

    #if (len(sys.argv) != 3):
     #       print "ERROR: genRandomGeorml <nodes> <raio>"
      #      sys.exit(1)

    NMAX = int(sys.argv[1])
    RAIO = float(sys.argv[2])
    #NMAX=40
    #RAIO=0.1
    ALCANCE=250

    G=nx.random_geometric_graph(NMAX,RAIO,2)

    while not nx.is_connected(G):
         RAIO=RAIO+.005
         G=nx.random_geometric_graph(NMAX,RAIO,2)
         if LOG: print "Graph is not full connected"

    pos=nx.get_node_attributes(G,'pos')
    network(G,pos,1)

    #Remove vizinhos que estejam demasiado perto
    while nodeNear(G)<1000 :
        G.remove_node(nodeNear(G))

    if nx.is_connected(G):
        pos=nx.get_node_attributes(G,'pos')
        network(G,pos,2)

        #Remove no que tem mais vizinhos
        T=G
        if not nodeSolo(T,nodeMaxDegree(T)): T.remove_node(nodeMaxDegree(T))
        if nx.is_connected(T):
                G=T

        pos=nx.get_node_attributes(G,'pos')
        network(G,pos,3)



        for n in G.neighbors(nodeMaxDegree(G)):
            if nx.degree(G,n)== 2 :
                degree=nx.degree(G,n)
                node=n
                print "node=",n
                if not nodeSolo(G,n): G.remove_node(n)
                break
        
        pos=nx.get_node_attributes(G,'pos')
        network(G,pos,4)
    else:
        if LOG: print "SubGraph is not full connected"

def check_adj_list_connectivity(adj_graph_file):
    g = read_weighted_adj_graph(adj_graph_file)
    print 'finished reading in adjacency list file...'
    edges = list()
    for k, v in g.items():
        for val in v[0]:
            edges.append((k, val))
    print 'finished appending edges'
    G = networkx.Graph()
    # print len(edges)
    G.add_edges_from(edges)
    print networkx.is_connected(G)

def simple_query(GLearnt, trials):
	i = 1
	
	global Degree_Node
	global NodeList

	G = nx.Graph(GLearnt)
	G = G.subgraph(nx.connected_components(G)[0])
	print nx.is_connected(G)
	print G.number_of_nodes()

	Degree_Node = G.degree()
	NodeList = G.nodes()

	for i in NodeList:
		Degree_Node[i] = [Degree_Node[i], GLearnt.neighbors(i)]

	PlainAdamicFullPaths = []
	TwoWayAdamicFullPaths = []

	djk_time = 0
	TwoWayAdamic_time = 0
	PlainAdamic_time = 0

	count = 0

	for i in range(trials):
		A = random.choice(NodeList)
		B = random.choice(NodeList)
	#for A in NodeList:
		#for B in NodeList[NodeList.index(A):]:
		if A != B :	
			src = A #raw_input("Enter source name:")
			dstn = B #raw_input("Enter destination name:")
			start = time.time()
			TwoWayAdamicFullPath = TwoWayAdamicWalk(G,src,dstn)
			finish = time.time()
			TwoWayAdamic_time+=(finish-start)


			start = time.time()
			PlainAdamicFullPath = OneWayAdamicWalk(G,src,dstn)
			finish = time.time()
			PlainAdamic_time+=(finish-start)
			
			count += 1
	                sys.stdout.write(" "*20 + "\b"*50) 
			sys.stdout.write( "Progress: " + str(float(count)/trials))

	print "\n"
	print "Plain Adamic Time : ", PlainAdamic_time
	print "Two Way Adamic Time : ", TwoWayAdamic_time
	return [PlainAdamic_time, TwoWayAdamic_time]

def test_edge_cutset_random_graphs():
    for flow_func in flow_funcs:
        for i in range(3):
            G = nx.fast_gnp_random_graph(50, 0.25)
            if not nx.is_connected(G):
                ccs = iter(nx.connected_components(G))
                start = arbitrary_element(next(ccs))
                G.add_edges_from((start, arbitrary_element(c)) for c in ccs)
            cutset = nx.minimum_edge_cut(G, flow_func=flow_func)
            assert_equal(nx.edge_connectivity(G), len(cutset), msg=msg.format(flow_func.__name__))
            G.remove_edges_from(cutset)
            assert_false(nx.is_connected(G), msg=msg.format(flow_func.__name__))

def main():
    LOG = True

    if (len(sys.argv) != 5):
            print "ERROR: genMina3.py <nodes> <radius> <delta> <maxdegree>"
            sys.exit(1)

    NMAX = int(sys.argv[1])
    RAIO = float(sys.argv[2])
    delta = float(sys.argv[3])
    degree = float(sys.argv[4])
    #NMAX=40
    #RAIO=0.1
    ALCANCE=250
    c=0
    run=True
    first=True
    while run:
        c+=1
        G=nx.random_geometric_graph(NMAX,RAIO,2)

        while not nx.is_connected(G):
            if first:
                RAIO=RAIO+.005
            G=nx.random_geometric_graph(NMAX,RAIO,2)
            if LOG: print c,"- Radius: Graph is not full connected R=",RAIO
        first=False

        #Remove vizinhos que estejam demasiado pertoc
        candidate=nodeNear(G,delta)
        
        while not candidate==10000 :
                G.remove_node(candidate)
                candidate=nodeNear(G,delta)
        if nx.is_connected(G):
            #Remove no que tem mais vizinhos
            candidate=nodeMaxDegree(G)
            while nx.degree(G,candidate)> degree :
                    G.remove_node(candidate)
                    candidate=nodeMaxDegree(G)    
            if nx.is_connected(G):
                run=False
            else:
                if LOG: print c,"- MaxDegree: Split Graph"
        else:
            if LOG: print c,"- nodeNear: Split Graph"

    pos=nx.get_node_attributes(G,'pos')
    network(G,pos,5)
    if LOG: print "Raio =",RAIO
    if LOG: print "NMAX =",NMAX
    if LOG: print "Nodes =",nx.number_of_nodes(G)

    def undirected_stats(self):
        if nx.is_connected(self.nx_graph):
            conl = nx.connected_components(self.nx_graph) #needs work-around for unconnected subgraphs
            conl = conl.pop()
        else:
            conl = 'NA - graph is not connected'

        result = { #"""returns boolean"""
            'con': nx.is_connected(self.nx_graph),
            'conn': nx.number_connected_components(self.nx_graph), 
            'conl': conl,
            'Conl': g.subgraph(conl)
            }
        return result

def test_octahedral_cutset():
    G=nx.octahedral_graph()
    # edge cuts
    edge_cut = nx.minimum_edge_cut(G)
    assert_equal(4, len(edge_cut))
    H = G.copy()
    H.remove_edges_from(edge_cut)
    assert_false(nx.is_connected(H))
    # node cuts
    node_cut = nx.minimum_node_cut(G)
    assert_equal(4,len(node_cut))
    H = G.copy()
    H.remove_nodes_from(node_cut)
    assert_false(nx.is_connected(H))

def random_1kc(G0, nswap=1, max_tries=100):     #保持连通性下随机断边重连的1阶零模型
    """
    在random_1k()的基础上增加连通性判断，若置乱后的网络不保持连通性则撤销该置乱操作
    注：G0为连通网络
    """
    if not nx.is_connected(G0):
       raise nx.NetworkXError("Graph not connected")
    if len(G0) < 4:
        raise nx.NetworkXError("Graph has less than four nodes.")
    G = copy.deepcopy(G0)
    n=0
    swapcount=0
    keys,degrees=zip(*G.degree().items()) 
    cdf=nx.utils.cumulative_distribution(degrees)  
    while swapcount < nswap:
        swapped=[]
        (ui,xi)=nx.utils.discrete_sequence(2,cdistribution=cdf)
        if ui==xi:
            continue 
        u=keys[ui] 
        x=keys[xi]
        v=random.choice(list(G[u]))
        y=random.choice(list(G[x]))
        if v==y:
            continue
        if len(set([u,v,x,y]))<4:
            continue
        if (y not in G.neighbors(u)) and (v not in G.neighbors(x)) and ((u,v) in G.edges()) and ((x,y) in G.edges()):
            G.add_edge(u,y)         
            G.add_edge(v,x)
            G.remove_edge(u,v)      
            G.remove_edge(x,y)
            swapped.append((u,v,x,y))
            swapcount+=1
        if not nx.is_connected(G):      
            while swapped:
                (u, v, x, y) = swapped.pop()
                G.add_edge(u,v)         #撤销断边操作
                G.add_edge(x,y)
                G.remove_edge(u,x)      #撤销连新边操作
                G.remove_edge(v,y)
                swapcount -= 1
        if n >= max_tries:
            e=('Maximum number of swap attempts (%s) exceeded '%n +
            'before desired swaps achieved (%s).'%nswap)
            print e
            break
        n+=1
    return G

def sensi_diameter(G):
    import networkx as nx
    
    """
    Compute graph sensitivity to node removal, in terms of
    the difference in graph diameter on the removal of each
    node in turn.
     
    This uses local function x_diameter(G), which is modified
    from networkx.diamter(G) to work on XGraphs.
    
    DL Urban (9 Feb 2007)
    """
    
    # Starting diameter for full graph:
    
    if nx.is_connected(G):
        d0 = x_diameter(G)
    else:
        G0 = nx.connected_component_subgraphs(G) [0] # the largest subgraph
        d0 = x_diameter(G0)
        nc = nx.number_connected_components(G)	     # how many are there?
    
    sensi = {}
    
    for node in G.nodes():
        ex = G.edges(node) 		# a set of edges adjacent to node; 
        G.delete_edges_from(ex)		# remove all of these,
        G.delete_node(node)		# and then kill the node, too
        if nx.is_connected(G):
            dx = x_diameter(G)
            cuts = 0
        else:
            Gx = nx.connected_component_subgraphs(G) [0]	# the biggest
            ncx = nx.number_connected_components(G)
            if nc == ncx:
                cuts = 0
            else:
                cuts = 1
            dx = x_diameter(Gx)
        delta = d0 - dx
        G.add_node(node)		# put the node and edges back again
        G.add_edges_from(ex)
        sensi[node] = (cuts, delta)
 

    # create and return a tuple (cuts, delta)
    return sensi

def basic_local_search(graph, solution):

    original = solution.copy()
    before = count_leaves(solution)
    best_solution = solution.copy()
    best_leaves = count_leaves(best_solution)
    for i in range(10):
        best = count_leaves(solution)
        candidates = set(get_vertices_with_degree(solution, 2))
        leaves = set(get_vertices_with_degree(solution, 1))
        leaf_neighbors = []
        for leaf in leaves:
            leaf_neighbors.extend(nx.neighbors(solution, leaf))
        leaf_neighbors = set(leaf_neighbors)
        vs = candidates.intersection(leaf_neighbors)
        for v in vs:
            leafs = [l for l in nx.neighbors(solution, v) if l in leaves]
            if leafs:
                leaf = leafs[0]
            else:
                break
            solution.remove_edge(v, leaf)
            neighbors = nx.neighbors(graph, leaf)
            for neighbor in neighbors:
                solution.add_edge(leaf, neighbor)
                new = count_leaves(solution)
                if new > best:
                    best = new
                else:
                    solution.remove_edge(leaf, neighbor)
            if not nx.is_connected(solution):
                solution.add_edge(v, leaf)
        if count_leaves(solution) < best_leaves:
            solution = best_solution.copy()
        elif count_leaves(solution) > best_leaves:
            best_solution = solution.copy()
            best_leaves = count_leaves(best_solution)

    after = count_leaves(solution)
    if before > after:
        solution = original.copy()
    if before != after:
        print 'before/after: ', before, after
    if before > after:
        raise Exception('you dun goofed')
    if not nx.is_connected(solution):
        raise Exception('you dun goofed')
    return solution

def start(G, name):
	#pega somente o maior subgrafo
	if(not(nx.is_connected(G))):
		G = nx.connected_component_subgraphs(G)[0]

	# tuple of all parallel python servers to connect with
	ppservers = ()
	#ppservers = ("a3.ft.unicamp.br","a9.ft.unicamp.br","a7.ft.unicamp.br","a8.ft.unicamp.br","a10.ft.unicamp.br")
        job_server = pp.Server(ppservers=ppservers)
        job_server.set_ncpus(1)

	job = []
	capacities = []
	damage = []
	ran = 30 #range
	print "server e variaveis carregados"

	for i in xrange(1,ran):
		#Aqui faz-se um range de para 50 valores diferentes de capacidade inicial na rede
		capacity = 1.0+(1.0/float(ran)*float(i))
		job.append(job_server.submit(Attack, (cp.copy(G),capacity),(GlobalEfficiency,setCapacity), ("networkx as nx",)))
		capacities.append(capacity)

	job_server.wait()

	for i in xrange(len(job)):
		damage.append(job[i]())

	#Salva o arquivo da estrategia testada
        res = (capacities, damage)
        pickle.dump(res, open("dados/planejada/"+name+".pickle","w"))
        job_server.print_stats()

def number_of_partition(G):
    count = 0
    for n in powerset(range(len(G.nodes()))):
        if len(n) >= 1 and len(n) < G.number_of_nodes():
            H1 = G.subgraph(n)
            if not nx.is_connected(H1):
                continue
            nbar = []
            for i in range(0, len(G.nodes())):
                if i not in n:
                    nbar.append(i)
            H2 = G.subgraph(nbar)
            if not nx.is_connected(H2):
                continue
            count += 1
    return count / 2