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)

def gnp_survey_benchmark(path, n_array, p_array):
    with open(path, 'w', newline='\n') as f:
        w = csv.writer(f)
        w.writerow(['n', 'p = 0.2', 'p = 0.4', 'p = 0.5', 'p = 0.6', 'p = 0.8'])
        for n in n_array:
            list = [str(n)]
            for p in p_array:
                print("Starting trial n = " + str(n) + ", p = " + str(p) + ".")
                G = nx.gnp_random_graph(n, p)
                for (i, j) in G.edges_iter():
                    G[i][j]['weight'] = 1
                print("Calling GH algorithm")
                ############ TIMING ############
                start = time.time()
                gh = gomory_hu_tree(G)
                end = time.time()
                t = end-start
                ########## END TIMING ##########
                list.append(t)
                print("Completed trial n = " + str(n) + ", p = " + str(p) + ".")
                print("Time = " + str(t))
                nx.write_adjlist(G, 'Graph(' + str(n) + "," + str(p) + ").csv")
                nx.write_adjlist(gh, 'Gomory_Hu(' + str(n) + "," + str(p) + ").csv")
                print()
            w.writerow(list)

def construct_HardTh(fCorr, ffMRI):
    #
    # a function to generate hard thresholding networks
    #
    #
    # some parameters
    Target_K = [10, 20, 30, 40, 50]
    # Output directory is relative to fCorr directory
    CorrDir, fCorrMat = os.path.split(fCorr)
    BaseDir, CorrDirName = os.path.split(CorrDir)
    OutBase = os.path.join(BaseDir, 'Adjlist')
    if not os.path.exists(OutBase):
        os.makedirs(OutBase)
    OutDir = os.path.join(OutBase, 'Network_HardTh')
    if not os.path.exists(OutDir):
        os.makedirs(OutDir)
    # loading the correlation matrix
    R, NodeInd = NetUtil.load_corrmat_sparse(fCorr, ffMRI)
    # loop for generating hard-th networks
    for K in Target_K:
        print "Generating a network with threshold <k>=" + str(K)
        # generating the network
        G, RTh = NetUtil.net_builder_HardTh(R, NodeInd, K)
        # saving the network
        fNetFile = "Network_K" + str(K) + ".adjlist"
        fNet = os.path.join(OutDir,fNetFile)
        nx.write_adjlist(G, fNet)

def construct_HardThE(fCorr, ffMRI):
    #
    # a function to generate hard thresholding networks with the same number
    # of edges as rank-thresholded networks.
    #
    #
    # some parameters
    Target_d = [3, 4, 5, 6, 8, 10, 15, 20, 30]
    # Output directory is relative to fCorr directory
    CorrDir, fCorrMat = os.path.split(fCorr)
    BaseDir, CorrDirName = os.path.split(CorrDir)
    OutBase = os.path.join(BaseDir, 'Adjlist')
    if not os.path.exists(OutBase):
        os.makedirs(OutBase)
    OutDir = os.path.join(OutBase, 'Network_HardThE')
    if not os.path.exists(OutDir):
        os.makedirs(OutDir)
    # directory where rank-th networks are
    RankDir = os.path.join(OutBase, 'Network_RankTh')
    # loading the correlation matrix
    R, NodeInd = NetUtil.load_corrmat_sparse(fCorr, ffMRI)
   # loop for generating hard-th networks
    for d in Target_d:
        print "Generating an equivalent hard thresholded network with d=" + str(d)
        # loading the rank thresholded network to determine the number of edges
        fdNetFile = "Network_d" + str(d) + ".adjlist"
        fdNet = os.path.join(RankDir,fdNetFile)
        tmpG = nx.read_adjlist(fdNet)
        E = len(tmpG.edges())
        # generating the network
        G, RTh = NetUtil.net_builder_HardThE(R, NodeInd, E)
        # saving the network
        fNetFile = "Network_EQd" + str(d) + ".adjlist"
        fNet = os.path.join(OutDir,fNetFile)
        nx.write_adjlist(G, fNet)

def construct_RankTh(fCorr, ffMRI):
    #
    # a function to generate rank-based thresholding networks
    #
    #
    # some parameters
    Target_d = [3, 4, 5, 6, 8, 10, 15, 20, 30]
    # Output directory is relative to fCorr directory
    CorrDir, fCorrMat = os.path.split(fCorr)
    BaseDir, CorrDirName = os.path.split(CorrDir)
    OutBase = os.path.join(BaseDir, 'Adjlist')
    if not os.path.exists(OutBase):
        os.makedirs(OutBase)
    OutDir = os.path.join(OutBase, 'Network_RankTh')
    if not os.path.exists(OutDir):
        os.makedirs(OutDir)
    # loading the correlation matrix
    R, NodeInd = NetUtil.load_corrmat_sparse(fCorr, ffMRI)
    # loop for generating rank-th networks
    for iTh in range(len(Target_d)):
        print "Generating a network with threshold d=" + str(Target_d[iTh])
        # generating the network
        if iTh==0:
            G, trR = NetUtil.net_builder_RankTh(R, NodeInd, Target_d[iTh])
            R = [] # releasing the memory
        else:
            # just generate the difference between the previous threshold.
            # then combine the resulting graphs
            deltaG, trR = NetUtil.net_builder_RankTh(trR, NodeInd, 
                                                Target_d[iTh]-Target_d[iTh-1])
            G = nx.compose(G, deltaG)
        # saving the network
        fNetFile = "Network_d" + str(Target_d[iTh]) + ".adjlist"
        fNet = os.path.join(OutDir,fNetFile)
        nx.write_adjlist(G, fNet)

def construct_de_bruijn_velvet(kmers, draw, outfile):
	#make list of k-1mers for quick edge construction
	k1mers = [x[:-1] for x in kmers.keys()]
	k1mers_array = np.array(k1mers)

	#find overlaps
	edge_list = []
	for kmer in kmers.keys():
		matches = np.where(k1mers_array==kmer[1:])
		for match in matches[0]:
			#print match
			edge_list.append((kmer, kmers.keys()[match]))

	#make graph
	G = nx.DiGraph()
	#add seq_kmers as nodes and overlaps as edges
	for kmer in kmers.items():
		G.add_node(kmer[0], num=kmer[1])
	G.add_edges_from(edge_list)

	# draw the graph if desired
	if draw == "True":
		nx.draw_spring(G)
		plt.show()

	#output adjacency list format of the graph if desired
	if outfile != "":
		nx.write_adjlist(G, outfile)

	return G

def createMergedGraph(groupSampleDict, processedDataDir, rawModelDir):

    print 'Merging genomes from specified taxonomic group'

# Loop over the keys of the dictionary, one for each group
    for group in groupSampleDict:

# Create an empty graph object
        mergedGraph = nx.DiGraph()

# Read in the graph of the group and merge with the graph from the previous
# iteration
        for sample in groupSampleDict[group]:

# Read in adjacency list and convert to digraph object
            myDiGraph = nx.read_adjlist(rawModelDir+'/'+sample+'/'+sample+'AdjList.txt',
                                create_using=nx.DiGraph())

# Append to the previous graph
            mergedGraph = nx.compose(mergedGraph, myDiGraph)

# Check that the proper output directory exists. It not, create it.
        if not os.path.exists(processedDataDir+'/'+group):
            os.makedirs(processedDataDir+'/'+group)

        nx.write_adjlist(mergedGraph, processedDataDir+'/'+group+'/'+group+'AdjList.txt')
        nx.write_graphml(mergedGraph, processedDataDir+'/'+group+'/'+group+'Graph.xml')

    return

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 test_adjlist_delimiter(self):
     fh = io.BytesIO()
     G = nx.path_graph(3)
     nx.write_adjlist(G, fh, delimiter=':')
     fh.seek(0)
     H = nx.read_adjlist(fh, nodetype=int, delimiter=':')
     assert_nodes_equal(list(H), list(G))
     assert_edges_equal(list(H.edges()), list(G.edges()))

def issues_network(out, repo, github):
    """Builds issues netowrk"""

    interactions = datautil.get_issues_interaction(repo, github)

    graph = networkutil.create_interaction_network(interactions,
            repo_name=repo)

    nx.write_adjlist(graph, out)

def allFiles(groupName):
    fdRead = open('%s' % groupName, 'r')  #open file with edge list
    lines = fdRead.readlines()  #read all lines
    fdRead.close()  #close file

    G = nx.parse_edgelist(lines, nodetype=int)  #builte graph with edge list file
    nx.write_adjlist(G, 'adj_list.txt')  #write graph as adjacency matrix to file
    getPartitions(G)  #get partitions graph
    edgesInCommunitiesGraph('adj_list.txt', 'partitions.txt')  #add edges to graph of partitions

 def test_adjlist_integers(self):
     (fd, fname) = tempfile.mkstemp()
     G = nx.convert_node_labels_to_integers(self.G)
     nx.write_adjlist(G, fname)
     H = nx.read_adjlist(fname, nodetype=int)
     H2 = nx.read_adjlist(fname, nodetype=int)
     assert_nodes_equal(list(H), list(G))
     assert_edges_equal(list(H.edges()), list(G.edges()))
     os.close(fd)
     os.unlink(fname)

def convert_graph_to_text(graph, filename):
    """
    given a graph object, write a file containing the adjacency list.
    this is the minimum data required to reconstruct the graph.
    :param graph: the graph object to get the list from.
    :param filename: the name of the file to write to.
    :return:
    """
    networkx.write_adjlist(graph, filename)
    return

def main():
    badges = user_badge_extract('Badges.xml')
    G = create_graph(badges)
    
#    draw_graph(G)
    
    # Saving the graph in Pajek format
    nx.write_pajek(G, "graph.net")
    
    # Saving the graph as AdjList
    nx.write_adjlist(G, "graph.adjlist")

 def test_adjlist_graph(self):
     G=self.G
     (fd,fname)=tempfile.mkstemp()
     nx.write_adjlist(G,fname)  
     H=nx.read_adjlist(fname)
     H2=nx.read_adjlist(fname)
     assert_not_equal(H,H2) # they should be different graphs
     assert_equal(sorted(H.nodes()),sorted(G.nodes()))
     assert_equal(sorted(H.edges()),sorted(G.edges()))
     os.close(fd)
     os.unlink(fname)

 def test_adjlist_digraph(self):
     G = self.DG
     (fd, fname) = tempfile.mkstemp()
     nx.write_adjlist(G, fname)
     H = nx.read_adjlist(fname, create_using=nx.DiGraph())
     H2 = nx.read_adjlist(fname, create_using=nx.DiGraph())
     assert_not_equal(H, H2)  # they should be different graphs
     assert_nodes_equal(list(H), list(G))
     assert_edges_equal(list(H.edges()), list(G.edges()))
     os.close(fd)
     os.unlink(fname)

def RGG(n, beta, mean_degree):
    G = nx.empty_graph(n)
    degreeArray = utils.degreeDistribution(beta, n, mean_degree)
    utils.randPairings(G, degreeArray)
    txtName = "generated/adj-%s-%s-%s-.txt" % (str(n), str(beta), str(mean_degree))
    nx.write_adjlist(G, txtName)
    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)

def commit_networks(in_pattern, out_dir, languages):
    """ Builds commit network.

    It retrieves commits from the top most-watched
    repos of the given language. Then, for each repo,
    it builds interaction network from the commit history
    of each blob.

    param:
    in_pattern: The path pattern of file containing top
        most watched repos.
    out_dir: The pattern of the output dir for both
        raw data and graph data.
    lang: List of language.

    Here is the example of each param:
    in_pattern = "../data/most_watched/{0}.txt"
    out_dir = "../data/network/commit/{0}"
    lang = ['python', 'java']

    It should be noted that in out_dir, it is expected
    that there will be sub-dir graph/ and raw/.

    """

    graph_out = out_dir + "/graph/{1}.txt"
    raw_out = out_dir + "/raw/{1}.pickle"

    github = Github(requests_per_second=1)

    for lang in languages:
        with open(in_pattern.format(lang), "r") as f:
            for line in f:
                repo = line.strip()
                f_name = repo.replace('/', '_')

                print "Starting {0} at {1}".format(repo, raw_out.format(
                    lang, f_name))

                commits = get_commits_from_repo(repo, github)

                with open(raw_out.format(lang, f_name), "w") as pickle_f:
                        pickle.dump(commits, pickle_f)

                print "Starting {0} at {1}".format(repo, graph_out.format(
                    lang, f_name))

                commit_interactions = commit_interactions_from_repo(commits)
                g = networkutil.create_interaction_network(
                        commit_interactions, repo_name=repo)

                nx.write_adjlist(g, graph_out.format(lang, f_name))

def files_to_R2(G):
    #adjacency list
    nx.write_adjlist(G,"file_output/20120711adjlistFULL.csv")
    #node list
    text_file = open("file_output/20120710nodes2FULL.csv", "a")#
    for node in G:
        text_file.write(str.format(str(node), '10.2f') + ',' + str.format(str(G.position[node][0]), '10.2f') + ', ' + str.format(str(G.position[node][1]), '10.2f') + '\n')
    text_file.close()
    #capacity of each edge
    text_file = open("file_output/20120626edgesFULL.csv", "a")#
    for edge in G.edges(data=True):
        text_file.write(str.format(str(edge[0]), '10.2f') + ',' + str.format(str(edge[1]), '10.2f') + ', ' + str.format(str(edge[2]['capacity']), '10.2f') + '\n')
    text_file.close()

 def work(self):
     with open('data/connected_synonyms.txt', 'r') as f:
         connected_synonyms_dict = ujson.loads(f.read())
     g = nx.Graph()
     for key in connected_synonyms_dict:
         g.add_node(key)
     for key in connected_synonyms_dict:
         for synonym in connected_synonyms_dict[key]:
             g.add_edge(key, synonym)
     # data = json_graph.node_link_data(g)
     with open('data/connected_synonyms_graph.adjlist', 'wb') as f:
         # f.write(ujson.dumps(data))
         nx.write_adjlist(g, f, delimiter='=-=')