def test_generate_sparse6(self):
        # Checked against sage encoder
        assert_equal(nx.generate_sparse6(nx.empty_graph(0)), '>>sparse6<<:?')
        assert_equal(nx.generate_sparse6(nx.empty_graph(1)), '>>sparse6<<:@')
        assert_equal(nx.generate_sparse6(nx.empty_graph(5)), '>>sparse6<<:D')
        assert_equal(nx.generate_sparse6(nx.empty_graph(68)),
                     '>>sparse6<<:[email protected]')
        assert_equal(nx.generate_sparse6(nx.empty_graph(258049)),
                     '>>sparse6<<:[email protected]')

        G1 = nx.complete_graph(4)
        assert_equal(nx.generate_sparse6(G1, header=True),
                     '>>sparse6<<:CcKI')
        assert_equal(nx.generate_sparse6(G1, header=False), ':CcKI')

        # Padding testing
        assert_equal(nx.generate_sparse6(nx.path_graph(4), header=False),
                     ':Cdv')
        assert_equal(nx.generate_sparse6(nx.path_graph(5), header=False),
                     ':DaYn')
        assert_equal(nx.generate_sparse6(nx.path_graph(6), header=False),
                     ':EaYnN')
        assert_equal(nx.generate_sparse6(nx.path_graph(7), header=False),
                     ':FaYnL')
        assert_equal(nx.generate_sparse6(nx.path_graph(8), header=False),
                     ':GaYnLz')

def SBM(nvec,block_probs, directed=True, seed=None):
    """Return a graph sampled from a stochastic block model
    
    Parameters
    ----------
    nvec : array [k,1]
        The number of vertices per block; there are k blocks.
    B : array [k,k] in (0,1)^{k x k}
        Probability for edge creation for each block.
    seed : int, optional
        Seed for random number generator (default=None). 
    
      math
    Notes
    -----    
    loopy : bool, optional (default=True)
        If True return a loopy graph
    
    This algorithm iterates over pairs of blocks and then assigns edges uniformly at random
    between nodes in each block
    """
    
    if (block_probs<0).any():
        raise ValueError('some probability is <0')
    if (block_probs>1).any():
        raise ValueError('some probability is >1')
    if np.shape(block_probs)[0] != len(nvec):
        raise ValueError('nvec must be of length equal to the number of columns/rows of block_probs')
    
    if seed:
        np.random.seed(seed)
    
    Nvertices=nvec.sum()        # total number of vertices
    Nblocks=len(nvec)             # number of groups
    if directed:
        G=nx.empty_graph(Nvertices,create_using=nx.DiGraph())
    else:
        G=nx.empty_graph(Nvertices,create_using=nx.Graph())
    block_idx = np.append(0, nvec).cumsum()
    block = np.zeros(Nvertices, dtype=np.int)
    
    for ii in xrange(Nblocks):
        nodes1 = np.arange(block_idx[ii],block_idx[ii+1])
        block[block_idx[ii]:block_idx[ii+1]] = ii
        if directed:
            add_random_edges_between(G, nodes1, block_probs[ii,ii],nodes1)
        else:
            add_random_edges_between(G, nodes1, block_probs[ii,ii])
            
        for jj in xrange(ii+1,Nblocks):
            nodes2 = np.arange(block_idx[jj],block_idx[jj+1])
            if directed:
                add_random_edges_between(G, nodes1, block_probs[ii,jj],nodes2)
                add_random_edges_between(G, nodes2, block_probs[jj,ii],nodes1)
            else:
                add_random_edges_between(G, nodes1, block_probs[ii,jj],nodes2)

    nx.set_node_attributes(G, 'block', dict(zip(np.arange(Nvertices), block)))
    return G

 def test_empty_subgraph(self):
     # Subgraph of an empty graph is an empty graph. test 1
     nullgraph = nx.null_graph()
     E5 = nx.empty_graph(5)
     E10 = nx.empty_graph(10)
     H = E10.subgraph([])
     assert_true(nx.is_isomorphic(H, nullgraph))
     H = E10.subgraph([1, 2, 3, 4, 5])
     assert_true(nx.is_isomorphic(H, E5))

def test_strong_product():
    null=nx.null_graph()
    empty1=nx.empty_graph(1)
    empty10=nx.empty_graph(10)
    K2=nx.complete_graph(2)
    K3=nx.complete_graph(3)
    K5=nx.complete_graph(5)
    K10=nx.complete_graph(10)
    P2=nx.path_graph(2)
    P3=nx.path_graph(3)
    P5=nx.path_graph(5)
    P10=nx.path_graph(10)
    # null graph
    G=strong_product(null,null)
    assert_true(nx.is_isomorphic(G,null))
    # null_graph X anything = null_graph and v.v.
    G=strong_product(null,empty10)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(null,K3)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(null,K10)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(null,P3)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(null,P10)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(empty10,null)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(K3,null)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(K10,null)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(P3,null)
    assert_true(nx.is_isomorphic(G,null))
    G=strong_product(P10,null)
    assert_true(nx.is_isomorphic(G,null))

    G=strong_product(P5,K3)
    assert_equal(nx.number_of_nodes(G),5*3)
    G=strong_product(K3,K5)
    assert_equal(nx.number_of_nodes(G),3*5)

    #No classic easily found classic results for strong product

    G = nx.erdos_renyi_graph(10,2/10.)
    H = nx.erdos_renyi_graph(10,2/10.)
    GH = strong_product(G,H)

    for (u_G,u_H) in GH.nodes_iter():
        for (v_G,v_H) in GH.nodes_iter():
            if (u_G==v_G and H.has_edge(u_H,v_H)) or \
               (u_H==v_H and G.has_edge(u_G,v_G)) or \
               (G.has_edge(u_G,v_G) and H.has_edge(u_H,v_H)):
                assert_true(GH.has_edge((u_G,u_H),(v_G,v_H)))
            else:
                assert_true(not GH.has_edge((u_G,u_H),(v_G,v_H)))

    def extract_graph(self):

        graph = nx.Graph()
        nx.empty_graph(self.n, graph)

	for i in range(self.n):
            graph.node[i] = self.agent[i].opinion
            for j in range(self.agent[i].degree):
                graph.add_edge(i, self.agent[i].neighbors[j])

        return graph

    def __init__(self, n, f, q, id_topology = 'Nan', nmm = 1, noise = 0.00):

        nx.Graph.__init__(self)
        nx.empty_graph(n, self)

        self.init_agents(n, f, q)

        self.init_mass_media(nmm, f, q)

        if id_topology != 'Nan':
            self.set_topology(id_topology)

        self.noise = noise

    def test_generate_graph6(self):
        assert_equal(nx.generate_graph6(nx.empty_graph(0)), '>>graph6<<?')
        assert_equal(nx.generate_graph6(nx.empty_graph(1)), '>>graph6<<@')

        G1 = nx.complete_graph(4)
        assert_equal(nx.generate_graph6(G1, header=True), '>>graph6<<C~')
        assert_equal(nx.generate_graph6(G1, header=False), 'C~')

        G2 = nx.complete_bipartite_graph(6,9)
        assert_equal(nx.generate_graph6(G2, header=False),
                     'N??F~z{~Fw^_~?~?^_?') # verified by Sage

        G3 = nx.complete_graph(67)
        assert_equal(nx.generate_graph6(G3, header=False),
                     '[email protected]' + '~' * 368 + 'w')

def bipartite_alternating_havel_hakimi_graph(aseq, bseq,
                                            create_using=None,
                                            ):
    """
    Return a bipartite graph from two given degree sequences
    using a alternating Havel-Hakimi style construction.

    :Parameters:
       - `aseq`: degree sequence for node set A
       - `bseq`: degree sequence for node set B

    Nodes from the set A are connected to nodes in the set B by
    connecting the highest degree nodes in set A to
    alternatively the highest and the lowest degree nodes in set
    B until all stubs are connected.

    The sum of the two sequences must be equal: sum(aseq)=sum(bseq)
    """
    if create_using==None:
        create_using=NX.MultiGraph()

    G=NX.empty_graph(0,create_using)

    # length of the each sequence
    naseq=len(aseq)
    nbseq=len(bseq)
    suma=sum(aseq)
    sumb=sum(bseq)

    if not suma==sumb:
        raise NX.NetworkXError, \
              'invalid degree sequences, sum(aseq)!=sum(bseq),%s,%s'\
              %(suma,sumb)

    G.add_nodes_from(range(0,naseq)) # one vertex type (a)
    G.add_nodes_from(range(naseq,naseq+nbseq)) # the other type (b)

    if max(aseq)==0: return G  # done if no edges
    # build list of degree-repeated vertex numbers
    astubs=[[aseq[v],v] for v in range(0,naseq)]  
    bstubs=[[bseq[v-naseq],v] for v in range(naseq,naseq+nbseq)]  
    while astubs:
        astubs.sort()
        (degree,u)=astubs.pop() # take of largest degree node in the a set
        if degree==0: break # done, all are zero
        bstubs.sort()
        small=bstubs[0:degree/2]  # add these low degree targets     
        large=bstubs[(-degree+degree/2):] # and these high degree targets
        stubs=[x for z in zip(large,small) for x in z] # combine, sorry
        if len(stubs)<len(small)+len(large): # check for zip truncation
            stubs.append(large.pop())
        for target in stubs:
            v=target[1]
            G.add_edge(u,v)
            target[0] -= 1  # note this updates bstubs too.
            if target[0]==0:
                bstubs.remove(target)

    G.name="bipartite_alternating_havel_hakimi_graph"
    return G

    def firstFitTopo(self, jobs, reservations):
        if len(jobs) != len(reservations):
            raise IndexError("Length of jobs and reservations input lists do no match")

        import networkx as nx
        skeleton = nx.barabasi_albert_graph(780)
        G = nx.empty_graph()

def Gen2DLattice(size):
    side = sqrt(size)
    if not side.is_integer():
        print("Error: the size of lattice is not perfect square!")
        sys.exit()

    G = nx.empty_graph(size)

    for i in range(size):
        r = i // side
        c = i % side
        # Now we have to add 4 edges to the neighbours of i_th node
        # Adding edge to the neighbour: (r+1,c)
        l = ((r+1) % side) * side + c
        G.add_edge(i,l)
        # Adding edge to the neighbour: (r-1,c)
        l = ((r-1) % side) * side + c
        G.add_edge(i,l)
        # Adding edge to the neighbour: (r,c+1)
        l = r * side + ((c+1) % side)
        G.add_edge(i,l)
        # Adding edge to the neighbour: (r,c-1)
        l = r * side + ((c-1) % side)
        G.add_edge(i,l)

    return G

def RGG(n, beta, mean_degree):
    G = nx.empty_graph(n)
    powerLawArray = utils.powerLawArray(n, beta, mean_degree)
    powerLawDegreeArray = np.array(powerLawArray, dtype = np.longlong)
    sumOfDegrees = powerLawDegreeArray.sum()
    delimiterArray = np.cumsum(powerLawDegreeArray)
    delimiterArray = np.insert(delimiterArray, 0, 0)
    delimiterArray = np.delete(delimiterArray, n)
    someCounter = 0
    while someCounter < sumOfDegrees/2:
        G.add_edge(np.searchsorted(delimiterArray, rnd.randrange(sumOfDegrees)),
               np.searchsorted(delimiterArray, rnd.randrange(sumOfDegrees)))
        someCounter += 1
    txtname = "generated/adj-%s-%s-%s-.txt" % (str(n), str(beta), str(mean_degree))
    nx.write_adjlist(G, txtname)
    degreeSequence=sorted(nx.degree(G).values(),reverse=True)
    dmax=max(degreeSequence)
    plt.clf()
    plt.cla()
    plt.loglog(degreeSequence,'b-',marker='o')
    plt.title("Degree rank plot")
    plt.ylabel("degree")
    plt.xlabel("rank")
    if n < 1000:
        plt.axes([0.45,0.45,0.45,0.45])
        plt.cla()
        Gcc=nx.connected_component_subgraphs(G)[0]
        pos=nx.spring_layout(Gcc)
        plt.axis('off')
        nx.draw_networkx_nodes(Gcc,pos,node_size=20)
        nx.draw_networkx_edges(Gcc,pos,alpha=0.4)
    pngname = "generated/graph-%s-%s-%s-.png" % (str(n), str(beta), str(mean_degree))
    plt.savefig(pngname)

    def get_graph_of_cluster(self, grids):
        # print '%%%%%%%%%%%%%%%%%%%%%is valid: ', self.is_valid_cluster(grids), ' %%%'
        # print 'graph of cluster grids keys: ', grids.keys()
        indices_list = grids.keys()
        g = nx.empty_graph()
        for i in range(len(indices_list)):
            indices = indices_list[i]
            # print 'indices: ', indices
            for j in range(len(indices_list)):
                other_indices = indices_list[j]
                # print 'other_indices: ', other_indices
                # print 'i, oi: ', indices, other_indices
                if self.are_neighbors(indices, other_indices):
                    # print '***** ', indices, other_indices, ' ARE neighbors'
                    if g.has_edge(indices, other_indices) == False:
                        g.add_edge(indices, other_indices)
                        continue
                g.add_node(other_indices)
            if g.has_node(indices) == False:
                g.add_node(indices)

        # print 'g size {}'.format(g.size())


        return g

def random_tree(n, create_using=None,seed=None):
    """ Returns a random tree of size n

    Proceeds by creating nodes and selecting uniformly at random
    an existing node to connect to.

    Parameters:
    -----------
    n : int
        Number of nodes
    create_using: networkx graph
                  graph to determine type
    seed: int
          Random seed value

    Returns:
    --------
    G: networkx Graph
       A random tree
    """

    if seed is not None:
        random.seed(seed)

    G = nx.empty_graph(0,create_using)

    G.add_node(0)
    for i in range(1,n):
        u = random.choice(G.nodes())
        G.add_node(i)
        G.add_edge(i,u)
    return G

def binomial_tree(n):
    """Returns the Binomial Tree of order n.
    
    The binomial tree of order 0 consists of a single vertex. A binomial tree of order k 
    is defined recursively by linking two binomial trees of order k-1: the root of one is 
    the leftmost child of the root of the other.

    Parameters
    ----------
    n : int
        Order of the binomial tree.

    Returns
    -------
    G : NetworkX graph
        A binomial tree of $2^n$ vertices and $2^n - 1$ edges.

    """
    G = nx.empty_graph(1)
    N = 1
    for i in range(n):
        edges = [(u + N, v + N)  for (u, v) in G.edges]
        G.add_edges_from(edges)
        G.add_edge(0,N)
        N *= 2
    return G

def draw_graph(label_flag=True, remove_isolated=True, different_size=True, iso_level=10, node_size=40):
    G=build_graph(fb.get_friends_network())
    betweenness=nx.betweenness_centrality(G)
    degree=nx.degree_centrality(G)
    degree_num=[ degree[v] for v in G]
    maxdegree=max(degree_num);mindegree=min(degree_num);
    print maxdegree,mindegree
    clustering=nx.clustering(G)
    print nx.transitivity(G)
    # Judge whether remove the isolated point from graph
    if remove_isolated is True:
        H = nx.empty_graph()
        for SG in nx.connected_component_subgraphs(G):
            if SG.number_of_nodes() > iso_level:
                H = nx.union(SG, H)
        G = H
    # Ajust graph for better presentation
    if different_size is True:
        L = nx.degree(G)
        G.dot_size = {}
        for k, v in L.items():
            G.dot_size[k] = v
        #node_size = [betweenness[v] *1000 for v in G]
        node_size = [G.dot_size[v] * 10 for v in G]
        node_color= [((degree[v]-mindegree))/(maxdegree-mindegree) for v in G]
        #edge_width = [getcommonfriends(u,v) for u,v in G.edges()]
    pos = nx.spring_layout(G, iterations=15)
    nx.draw_networkx_edges(G, pos, alpha=0.05)
    nx.draw_networkx_nodes(G, pos, node_size=node_size, node_color=node_color, vmin=0.0,vmax=1.0, alpha=0.3)
    # Judge whether shows label
    if label_flag is True:
        nx.draw_networkx_labels(G, pos, font_size=6,alpha=0.1)
    #nx.draw_graphviz(G)
    plt.show()
    return G

    def __init__(self, blockHeights):
        """
        Creates an occurence graph based on navigatable nodes (nodes at height 0)
        """
        self.width = len(blockHeights)
        self.height = len(blockHeights[0])
        self.g = nx.empty_graph(self.width * self.height)
        self.blockHeights = blockHeights
        self.prob = np.zeros(len(self.g.nodes())) #[0.0] * len(self.g.nodes())

        def isNavigabaleNode(nodeId):
            """ Returns false if a block is present else returns true """
            x, y = self.getCood(nodeId)
            return False if self.blockHeights[x][y] > 0 else True

        def getNeighbouringNodes(nodeId):
            """ Returns a list of nodes in all 8 directions from the given node """
            x, y = self.getCood(nodeId)
            neighbouringNodes = []
            for xoffset in range(-1, 2):
                for yoffset in range(-1, 2):
                    if xoffset == 0 and yoffset == 0:
                        continue
                    xn = x + xoffset
                    yn = y + yoffset
                    if xn < 0 or xn >= self.width or yn < 0 or yn >= self.height:
                        continue
                    neighbouringNodes.append(self.getNodeId(xn, yn))
            return neighbouringNodes

        for nodeId in self.g.nodes():
            neighbouringNodes = getNeighbouringNodes(nodeId)
            navigatableNodes = filter(isNavigabaleNode, neighbouringNodes)
            #print nodeId, len(navigatableNodes)
            self.g.add_edges_from([(nodeId, navigatableNode) for navigatableNode in navigatableNodes])

def random_social_graph(g, l, S, k, a):
    N = g*2**l
    G = nx.empty_graph(N)
    # create the social coordinates vs
    vs = np.zeros((S,N,l), dtype=int)
    # for every characteristic
    for s in range(S):
        # want to choose g elements at random for every coordinate
        random_nodes = list(range(N))
        random.shuffle(random_nodes)
        for ch in all_coordinates(l):
            for node in random_nodes[0:g]:
                vs[s, node, :] = ch
            del random_nodes[0:g]

    # collect all distances in a matrix
    social_matrix = social_distance_matrix(vs)
    # now add edges until the average degree is greater or equal to k
    while nx.number_of_edges(G) < N*k/2:
        # choose random node
        node1 = np.random.randint(N)
        # and random characteristic
        s = np.random.randint(S)
        # create probabilities
        probs = [ np.exp( -a * social_matrix[s, node1, node2] ) for node2 in range(N) ]
        # finally pick a node to connect to
        node2 = node1
        while node2 == node1 or G.has_edge(node1, node2): node2 = random_pick( list(range(N)), probs )
        #while node2 == node1: node2 = random_pick( list(range(N)), probs )
        G.add_edge(node1, node2)
    # done constructing the graph
    return G, social_matrix, vs

def setup_graph(ingredients, cuisine_name):
   # dict with random values for the position of the nodes
   p = dict((i,(random.gauss(0,2),random.gauss(0,2))) for i in range(len(ingredients)))

   # creating the graph
   G = nx.empty_graph()
   G.add_nodes_from(p) 
   
   # Setting an attribute with the position of each node in the graph
   pos = nx.set_node_attributes(G,'pos', p)

   # Creating the nodes
   node_trace = Scatter(
       x = [], 
       y = [], 
       text = [],
       name = cuisine_name,
       mode = 'markers', 
       hoverinfo = 'text')

   # adding positions for the nodes
   for node in G.nodes():
       x, y = G.node[node]['pos']
       node_trace['x'].append(x)
       node_trace['y'].append(y)

   # naming the nodes
   node_trace['text'].extend(ingredients)
    
   return node_trace

def create_c11_graph(N, g, l, S, k, alpha):
	G = nx.empty_graph(N)
	vs = np.zeros((S,N,l)) -1
	for s in range(S):
		distinct = int(N/g + 0.5)
		vs_distinct = np.zeros((distinct, l))
		
		for i in range(distinct):
			for j in range(l):
				vs_distinct[i,j] = i/(2**(l-j-1))%2
		
		for i in range(distinct):
			for gg in range(int(g)):
				node = -1
				while node == -1:
					node = np.random.randint(N)
					if vs[s, node,0] != -1:
						node = -1
				vs[s, node,:] = vs_distinct[i,:]
	
	x = social_distance_matrix(vs)
	while nx.number_of_edges(G) < N*k:
		i = np.random.randint(N)
		s = np.random.randint(S)
		j = i
		probabilities = np.zeros(N)
		for q in range(N):
			probabilities[q] = np.exp(-alpha*x[s, i, q])
		while j == i:
			j = random_pick(range(N), probabilities)
		G.add_edge(i,j)
	return G, x, vs

def generate_graph(n, beta, mean_degree):
    """
    Test Graph generation
    """
    G = nx.empty_graph(n)
    
    degreeArray = utils.degreeDistribution(beta, n, mean_degree)
    
    utils.randPairings(G, degreeArray)
    
    # output of the RGG
    if not os.path.exists('generated'):
        os.mkdir('generated')
    
    txtName = "generated/adj-%s-%s-%s-.txt" % (str(n), str(beta), str(mean_degree))
    nx.write_adjlist(G, txtName)
    
    # plotting
    utils.drawDegreeHistogram(G)
    if n < 1000:
        utils.drawGraph(G)
    pngname = "generated/graph-%s-%s-%s-.png" % (str(n), str(beta), str(mean_degree))
    plt.savefig(pngname)
    
    if not os.path.exists('feed'):
        os.mkdir('feed')
    
    utils.generateFeed(n)