def compare(self, g1, g2, alpha, verbose=False):
     """Compute the kernel value (similarity) between two graphs. 
     
     Parameters
     ----------
     g1 : networkx.Graph
         First graph.
     g2 : networkx.Graph
         Second graph.
     alpha : interger < 1
         A rule of thumb for setting it is to take the largest power of 10
         which is samller than 1/d^2, being d the largest degree in the 
         dataset of graphs.    
         
     Returns
     -------        
     k : The similarity value between g1 and g2.
     """
     am1 = nx.adj_matrix(g1)
     am2 = nx.adj_matrix(g2)
     x = np.zeros((len(am1),len(am2)))
     A = self.smt_filter(x,am1,am2,alpha)
     b = np.ones(len(am1)*len(am2))
     tol = 1e-6
     maxit = 20
     pcg(A,b,x,tol,maxit)
     return np.sum(x)

def features(G,G1):
    A = nx.adj_matrix(G)
    n = len(A)
    A1 = nx.adj_matrix(G1)
    
    D = A1[:n,:n]-A
    
    pos = 0
    neg = 0
    
    iz = range(n)
    jz = range(n)
    
    shuffle(iz)
    shuffle(jz)
    
    for i in iz:
        for j in jz:
            
            if D[i,j] == 1:
                pos +=1
                train += [ [dot(A.A[i] , A.A[j]) / norm(A.A[i])* norm(A.A[j]),M[i,j],FF[i,j]]]
                target += [D[i,j]]
            elif neg < c:
                neg +=1
                train += [[dot(A.A[i] , A.A[j]) / norm(A.A[i])* norm(A.A[j]),M[i,j],FF[i,j]]]
                target += [D[i,j]]
    
    return train, target

 def test_adjacency_matrix(self):
     "Conversion to adjacency matrix"
     assert_equal(nx.adj_matrix(self.G).todense(), self.A)
     assert_equal(nx.adj_matrix(self.MG).todense(), self.A)
     assert_equal(nx.adj_matrix(self.MG2).todense(), self.MG2A)
     assert_equal(nx.adj_matrix(self.G, nodelist=[0, 1]).todense(), self.A[:2, :2])
     assert_equal(nx.adj_matrix(self.WG).todense(), self.WA)
     assert_equal(nx.adj_matrix(self.WG, weight=None).todense(), self.A)
     assert_equal(nx.adj_matrix(self.MG2, weight=None).todense(), self.MG2A)
     assert_equal(nx.adj_matrix(self.WG, weight='other').todense(), 0.6 * self.WA)
     assert_equal(nx.adj_matrix(self.no_edges_G, nodelist=[1, 3]).todense(), self.no_edges_A)

def simulate_affiliation_dpe():
    nrange = [400] #50*2**np.arange(3)
    drange = np.arange(1,5)
    
    embed = [Embed.dot_product_embed,
             Embed.dot_product_embed_unscaled,
             Embed.normalized_laplacian_embed,
             Embed.normalized_laplacian_embed_scaled]
    
    k = 2
    p = .15
    q = .1
    
    for n in nrange:
        G = rg.affiliation_model(n, k, p, q)
        for d in drange:
            print n*k,d,
            for e in embed:
                Embed.cluster_vertices_kmeans(G, e, d, k, 'kmeans')
                print num_diffs_w_perms_graph(G, 'block', 'kmeans'),
                
            print
    
    plot.matshow(nx.adj_matrix(G))
    plot.show()

def main(argv):
    
    # graph_fn="./data/7.txt"
    # G = nx.Graph()  #let's create the graph first
    # buildG(G, graph_fn)
    k=5
    G=nx.planted_partition_graph(k,10,0.8,0.02)
    # G.clear()
    bg(G)
    from test import da
    da(G)

    print G.nodes()
    print G.number_of_nodes()
    g=G.copy()
    n = G.number_of_nodes()    #|V|
    A = nx.adj_matrix(G)    #adjacenct matrix

    m_ = 0.0    #the weighted version for number of edges
    for i in range(0,n):
        for j in range(0,n):
            m_ += A[i,j]
    m_ = m_/2.0
    print "m: %f" % m_

    #calculate the weighted degree for each node
    Orig_deg = {}
    Orig_deg = UpdateDeg(A, G.nodes())

    #run Newman alg
    res=runGirvanNewman(G, Orig_deg, m_)
    print res
    shs(g,res)

def main(argv):
    
    graph_fn="./data/7.txt"
    G = nx.Graph()  #let's create the graph first
    buildG(G, graph_fn)

    print G.nodes()
    print G.number_of_nodes()
    
    n = G.number_of_nodes()    #|V|
    A = nx.adj_matrix(G)    #adjacenct matrix

    m_ = 0.0    #the weighted version for number of edges
    for i in range(0,n):
        for j in range(0,n):
            m_ += A[i,j]
    m_ = m_/2.0
    print "m: %f" % m_

    #calculate the weighted degree for each node
    Orig_deg = {}
    Orig_deg = UpdateDeg(A, G.nodes())

    #run Newman alg
    runGirvanNewman(G, Orig_deg, m_)

    def __init__(self, G):
        '''
        Creates a TwoClubProblem for the given graph.

        Parameters
        ----------
        G : networkx.Graph
            The graph to find the 2-clubs of.
        '''

        n = nx.number_of_nodes(G)
        self.drivers, _ = find_drivers_id(G)
        Adj = nx.adj_matrix(G)

        # Create the individual adjacency matrices
        self.A = dict()
        for i in xrange(n):
            self.A[i] = Adj[i,:].transpose() * Adj[i,:]

        # Connectivity matrix
        C = Adj + Adj * Adj
        del Adj

        # First info vector
        info = [0 for i in xrange(n)]
        self.first_node = TwoClubNode(C, info, False)

def prune(net):
    import networkx as nx

    # removes the unconnected components
    G = create_nx_from_network(net)
    connected_component = G.subgraph(nx.connected_components(G)[0])
    return UndirectedNetwork(connected_component.number_of_nodes(), nx.adj_matrix(connected_component))

def barabasi_albert(N, M, seed, verbose=True):
    '''Create random graph using Barabási-Albert preferential attachment model.

    A graph of N nodes is grown by attaching new nodes each with M edges that
    are preferentially attached to existing nodes with high degree.

    Args:
        N (int):Number of nodes

        M (int):Number of edges to attach from a new node to existing nodes

        seed (int) Seed for random number generator

    Returns:
        The NxN adjacency matrix of the network as a numpy array.

    '''

    A_nx = nx.barabasi_albert_graph(N, M, seed=seed)
    A = np.array(nx.adj_matrix(A_nx))

    if verbose:
        print('Barbasi-Albert Network Created: N = {N}, '
              'Mean Degree = {deg}'.format(N=N, deg=meanDegree(A)))

    return A

    def _generate_dependency_list(self):
        """ Generates a dependency list for a list of graphs. Adds the
        following attributes to the pipeline:

        New attributes:
        ---------------

        procs: list (N) of underlying interface elements to be
        processed
        proc_done: a boolean vector (N) signifying whether a process
        has been executed
        proc_pending: a boolean vector (N) signifying whether a
        process is currently running.
        Note: A process is finished only when both proc_done==True and
        proc_pending==False
        depidx: a boolean matrix (NxN) storing the dependency
        structure accross processes. Process dependencies are derived
        from each column.
        """
        if not self._execgraph:
            raise Exception('Execution graph has not been generated')
        self.procs = self._execgraph.nodes()
        self.depidx = nx.adj_matrix(self._execgraph).__array__()
        self.proc_done    = np.zeros(len(self.procs), dtype=bool)
        self.proc_pending = np.zeros(len(self.procs), dtype=bool)

def get_T(G):
    ''' Return diffusion operator of a graph.

    The diffusion operator is defined as T = I - L, where L is the normalized
    Laplacian.

    Parameters
    ----------
    G : NetworkX graph
    
    Returns
    -------
    T : NumPy array
    Ln : NumPy array
      Normalized Laplacian of G.

    Notes
    -----
    Computing the normalized laplacian by hand. It seems there are some
    inconsistencies using nx.normalized_laplacian when G has selfloops.
    '''
    A = nx.adj_matrix(G, nodelist=sorted(G.nodes()))
    D = np.array(np.sum(A,1)).flatten()

    Disqrt = np.array(1 / np.sqrt(D))
    Disqrt = np.diag(Disqrt)
    L = np.diag(D) - A
    Ln = np.dot(np.dot(Disqrt, L), Disqrt)
    T =  np.eye(len(G)) - Ln
    T = (T + T.T) / 2 # Iron out numerical wrinkles
    
    return T, L

    def test_from_numpy_matrix_type(self):
        A = np.matrix([[1]])
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), int)

        A = np.matrix([[1]]).astype(np.float)
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), float)

        A = np.matrix([[1]]).astype(np.str)
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), str)

        A = np.matrix([[1]]).astype(np.bool)
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), bool)

        A = np.matrix([[1]]).astype(np.complex)
        G = nx.from_numpy_matrix(A)
        assert_equal(type(G[0][0]['weight']), complex)

        A = np.matrix([[1]]).astype(np.object)
        assert_raises(TypeError, nx.from_numpy_matrix, A)

        G = nx.cycle_graph(3)
        A = nx.adj_matrix(G).todense()
        H = nx.from_numpy_matrix(A)
        assert_true(all(type(m) == int and type(n) == int for m, n in H.edges()))
        H = nx.from_numpy_array(A)
        assert_true(all(type(m) == int and type(n) == int for m, n in H.edges()))

def cluster(matrix):
    G = nx.Graph()
    for i in xrange(len(matrix)):
        for j in xrange(len(matrix)):
            if matrix[i][j] != 0:
                G.add_edge(i, j, weight=1/matrix[i][j])

    n = G.number_of_nodes()    #|V|
    A = nx.adj_matrix(G)
    m_ = 0.0    #the weighted version for number of edges
    for i in range(0,n):
        for j in range(0,n):
            m_ += A[i,j]
    m_ = m_/2.0

#calculate the weighted degree for each node
    Orig_deg = {}
    UpdateDeg(Orig_deg, A)

#let's find the best split of the graph
    BestQ = 0.0
    Q = 0.0
    Bestcomps = None
    while True:    
        CmtyGirvanNewmanStep(G)
        Q = _GirvanNewmanGetModularity(G, Orig_deg);
        if Q > BestQ:
            BestQ = Q
            Bestcomps = nx.connected_components(G)    #Best Split
        if G.number_of_edges() == 0:
            break
    return Bestcomps

def MCL_cluster(G,ex,r,tol,threshold):
    """
    Computes a clustering of graph G using the MCL algorithm 
    with power parameter ex and inflation parameter r
    The algorithm runs until the relative decrease in norm 
    is lower than tol or after 10,000 iterations
    Returns an array whose values are greater than threshold
    Leaves the graph G unchanged
    """

    M = np.array(nx.adj_matrix(G.copy()))
    M = inflate(M,1)

    norm_old = 0
    norm_new = np.linalg.norm(M)
    it = -1
    itermax = 10000
    while it < itermax:
        it += 1
        norm_old = norm_new
        M = M**ex
        M = inflate(M,r)
        norm_new = np.linalg.norm(M)
        if __name__ == '__main__':
            # debugging
            print "iteration %s" %it
            print "prop. decrease %s" %(abs(norm_old-norm_new)/norm_old)
        if abs(norm_old-norm_new)/norm_old < tol:
            print it
            break
    M[M < threshold] = 0
    return M

def main(argv):
    if len(argv) < 2:
        sys.stderr.write("Usage: %s <input graph>\n" % (argv[0],))
        return 1
    graph_fn = argv[1]
    G = nx.Graph()  #let's create the graph first
    buildG(G, graph_fn, ',')

    print G.nodes()
    print G.number_of_nodes()
    
    n = G.number_of_nodes()    #|V|
    A = nx.adj_matrix(G)    #adjacenct matrix

    m_ = 0.0    #the weighted version for number of edges
    for i in range(0,n):
        for j in range(0,n):
            m_ += A[i,j]
    m_ = m_/2.0
    print "m: %f" % m_

    #calculate the weighted degree for each node
    Orig_deg = {}
    Orig_deg = UpdateDeg(A, G.nodes())

    #run Newman alg
    runGirvanNewman(G, Orig_deg, m_)

	def modularity(self):
		"""
		Compute the modularity. 

		Returns:
			Numerical value of the modularity of the graph. 
		"""
		g = self.gr
		A = nx.adj_matrix(g)
		degDict = nx.degree_centrality(g)

		adjDict = {}
		n = A.shape[0]
		B = A.sum(axis=1)
		for i in range(n):
			adjDict[g.nodes()[i]] = B[i,0]

		m = len(g.edges())

		connComponents = nx.connected_components(g)

		mod = 0

		for c in connComponents:
			edgesWithinCommunity = 0
			randomEdges = 0
			for u in c:
				edgesWithinCommunity += adjDict[u]
				randomEdges += degDict[u]
			mod += (float(edgesWithinCommunity) - float(randomEdges * randomEdges)/float(2 * m))	
		mod = mod/float(2 * m)
			
		return mod	

def MAWe(G):
    """Eigenvalue approximation of maximum average degree. This is conjectured
    to be an upper bound on MAW.
    """
    eigenvalues, eigenvectors = scipy.linalg.eig(nx.adj_matrix(G) )
    MAWe = float(max(eigenvalues))
    return MAWe

def rand_spanning_tree(N, rand_weights=False):
    '''Creats a random minimal tree on N nodes

    Args:
        N (int): Number of nodes

    Returns:
        A NxN numpy array representing the adjacency matrix of the graph.

    '''

    # Create Random Graph
    A_rand = rand.rand(N, N)
    G_rand = nx.Graph()
    G_rand.add_nodes_from(xrange(N))
    for i in xrange(N):
        for j in xrange(i+1):
            G_rand.add_edge(i, j, weight=A_rand[i, j])
    # Find minimal spanning tree
    spanning_tree = nx.minimum_spanning_tree(G_rand)
    # Create adjacency matrix
    final_graph = nx.adj_matrix(spanning_tree).toarray()
    final_graph[final_graph > 0] = 1
    # Randomize weights if requested
    if rand_weights:
        R = np.tril(rand.rand(N, N))
        R = R + np.transpose(R)
        final_graph = final_graph * R
    return final_graph

def modularity_matrix(G,edec=None):
    '''
    Computes the 'master' modularity matrix, without subgraph corrections.  The
    modularity matrix is defined as

                    Q(i,j) = A(i,j) - (k_i*k_j)/sum(k_i)

    where A is the adjacency matrix (weighted) of G and k_i are the (weighted)
    node degrees.

    INPUT
    -------

    G: networkx graph, required
        input graph for which modularity matrix is desired

    edec : string, optional
        edge decorator (name for weights) in weighted graphs

    OUTPUT:

    Q : numpy array
        Q will be of size len(G.nodes()) X len(G.nodes())
    '''
    # adjacency matrix piece (ordered according to G.nodes())
    Q = nx.adj_matrix(G,weight=edec)
    # degree-product portion (same order as adj_matrix!)
    nodes = G.nodes()
    ki = G.degree(weight=edec)
    kvec = np.zeros((len(nodes),1))
    for i in xrange(0,len(nodes)):
        kvec[i] = ki[nodes[i]]
    return Q - np.dot(kvec,kvec.T)/sum(ki.values())

def generate_crescent_edges_graphs(n_graphs, n_nodes, p_edges, min_p_edges=None):
    """Creates a set of n graphs with a fixed n nodes and choice of
    possible edges with crescent probability p.

    """

    adj_matrix_dict = defaultdict()

    if min_p_edges:
        min_p_edges = math.log1p(n_nodes) / n_nodes

    filename = 'edges_' + str(n_graphs) + 'G_' + str(n_nodes) + 'N'
    filename += '_from_' + str(min_p_edges) + '_to_' + str(p_edges) + 'P'

    j = (p_edges - min_p_edges) / n_graphs  # p increment

    p_edges = min_p_edges

    for i in range(0, n_graphs):
    
        G = nx.erdos_renyi_graph(n_nodes, p_edges)
    
        if nx.is_connected(G):
            adj_matrix_dict[p_edges] = nx.adj_matrix(G)

        p_edges += j

    write_to_file(adj_matrix_dict, filename + '.dat', BENCHMARKS_FILE_DIR)

    return filename