def go():
    """
    Run the IterF algorithm on some random graphs.
    """
    l = 9
    n = 2**l
    p = 3*math.log(n)/n

    for i in range(100):
        # Generate a random graph:
        g = nx.fast_gnp_random_graph(n,p)
        # Build AlgState from the graph:
        algs = AlgState(g)
        # Run the IterF algorithm until we reach a stationary state:
        algs.run_until_stat()

        # Print the properties of the resulting state:
        print('next_node Injective: {} | '
              'One round cycles: {} | '
              'Is only one cycle: {}'.\
                      format(\
                algs.is_next_node_injection(),\
                algs.is_all_cycles_one_round(),\
                algs.is_only_one_cycle())\
                )

def test_edge_cutset_random_graphs():
    for i in range(5):
        G = nx.fast_gnp_random_graph(50,0.2)
        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 smallWorldness(graph):
	return_values = []
	#Small-worldness criteria
	n = len(nx.nodes(graph))
	e = len(nx.edges(graph))
	#probability of edges: (number of edges in real graph)/possible edges
	p = e/float((n*(n-1)/2.0))	
	##
	#generate random graph using probability
	rand_graph = nx.fast_gnp_random_graph(n, p, seed=1)
	#calculate values for real graph and random graph
	Creal = nx.transitivity(graph) #float
	Crand = nx.transitivity(rand_graph) #float
	Lreal = 0
	Lrand = 0
	real_sum = 0
	rand_sum = 0
	splReal = shortest_path_lengths(graph)
	splRand = shortest_path_lengths(rand_graph)
	for i in range(len(splReal)):
		real_sum += splReal[i]
		rand_sum += splRand[i]
	Lreal = real_sum / len(splReal)
	Lrand = rand_sum / len(splRand)		
	#compare with actual graph
	if(Lreal != 0 and Lrand !=0 and Crand !=0):
		S = (Creal)/(Crand) / (float(Lreal)/(Lrand))
	else:
		S = 0
	return_values.append(S)
	return return_values

def generate_cluster_graph(n,m,in_p,out_p):
	'''Generates graph with 'n' nodes with form m clustures,
	with average in_p within cluster and 'out_degree' between clustures'''
	print "Generating G..."
	if m == 0 or n == 0:
		raise "n or m can not be 0"

	nodes_per_clusture = n/m
	num_of_outer_nodes = math.ceil(nodes_per_clusture * out_p)
	larger_graph = nx.Graph()
	print "\tExpected communities:",m
	print "\tnodes_per_clusture:",nodes_per_clusture,"\n\tnum_of_outer_nodes:",num_of_outer_nodes
	for i in xrange(m):
		# print 'clusture_id',i
		G = nx.fast_gnp_random_graph(nodes_per_clusture,in_p)
		for node in G.nodes():
			larger_graph.add_node((node)+nodes_per_clusture*i)
		for edge in G.edges():
			larger_graph.add_edge((edge[0])+nodes_per_clusture*i,(edge[1])+nodes_per_clusture*i)
		
		chosen_nodes = np.random.choice(G.nodes(),num_of_outer_nodes)
		for node in chosen_nodes:
			node_for_large_graph = node+nodes_per_clusture*i
			larger_graph.add_edge(node_for_large_graph,np.random.choice(larger_graph.nodes()))
	# print larger_graph.nodes()
	# print larger_graph.edges()
	return larger_graph

def main():
    args = parse_arguments()
    # Generate graph for given parameters

    if args.cycle:
        graph = networkx.cycle_graph(args.vertices)
        graph = networkx.path_graph(args.vertices)
    elif args.star:
        graph = networkx.star_graph(args.vertices)
    elif args.wheel:
        graph = networkx.wheel_graph(args.vertices)
    elif args.ladder:
        graph = networkx.ladder_graph(args.vertices)
    elif args.fill_rate:
        if args.fill_rate > 50.0:
            graph = networkx.gnp_random_graph(args.vertices, args.fill_rate / 100.0, None, args.directed)
        else:
            graph = networkx.fast_gnp_random_graph(args.vertices, args.fill_rate / 100.0, None, args.directed)
    else:
        graph = networkx.gnm_random_graph(args.vertices, args.edges, None, args.directed)

    # Print generated graph
    print("{} {}".format(graph.number_of_nodes(), graph.number_of_edges()))
    for edge in graph.edges():
        print("{} {}".format(edge[0] + 1, edge[1] + 1))

    # Export generated graph to .png
    if args.image_path:
        export_to_png(graph, args.image_path)

def get_random_weighted_graph(n, p=0.5, max_weight=10):
	print "n=%d, p=%f, max_weight=%d" % (n, p, max_weight)
	G = nx.fast_gnp_random_graph(n, p)
	for e in G.edges():
		G[e[0]][e[1]]['weight'] = random.randint(1, max_weight)
	# print list(G.edges(data='weight', default=1))
	return G

def test(test_functions,V,p):
    print V
    G = nx.fast_gnp_random_graph(V,p)
    for f in test_functions:
        time,runtime = f(G)
        fp = open(f.__name__+".res","a")
        fp.write("%i,%f,%f\n" % (V,time,runtime))

def main():
	import networkx as nx
	from complex_systems.pgg import PublicGoodGames
	import pylab as plt
	import numpy as np
	
	nb_node = 1000
	edge_prob = 10.0/nb_node
	coop_ratio = 0.5
	synergy = 8
	nb_round = 100
	nb_game_per_round = 10
	nb_def = []
	nb_coop = []
	
	# Generate a Random Graph 
	G = nx.fast_gnp_random_graph(nb_node, edge_prob)
	# initialize the game 
	PGG = PublicGoodGames(G=G, synergy=synergy,nb_simulation_step=nb_game_per_round, cooperator_ratio=coop_ratio)
	for i in range(nb_round):
		PGG.run_game()
		nb_def.append(PGG.defector_counter())
		nb_coop.append(PGG.cooperator_counter())
		#print nb_coop, nb_def
	plt.figure()
	plt.plot(nb_def,'b-*')
	plt.plot(nb_coop,'r-*')
	plt.figure()
	print np.mean([val for key, val in G.degree().iteritems()])
	nx.draw_networkx(G, node_size=20, with_labels = False)
	plt.show()

def gen_gnp_graph(i):
    """
    Generate a gnp random graph with 2**i nodes.
    """
    n = 2**i
    p = 2*i / (2**i)
    return nx.fast_gnp_random_graph(n,p)

def get_graph(objects, properties):
    graph_type = properties['graph_type']
    n = len(objects)-1
    if 'num_nodes_to_attach' in properties.keys():
        k = properties['num_nodes_to_attach']
    else:
        k = 3
    r = properties['connection_probability']

    tries = 0
    while(True):
        if graph_type == 'random':
            x = nx.fast_gnp_random_graph(n,r)
        elif graph_type == 'erdos_renyi_graph':
            x = nx.erdos_renyi_graph(n,r)
        elif graph_type == 'watts_strogatz_graph':
            x = nx.watts_strogatz_graph(n, k, r)
        elif graph_type == 'newman_watts_strogatz_graph':
            x = nx.newman_watts_strogatz_graph(n, k, r)
        elif graph_type == 'barabasi_albert_graph':
            x = nx.barabasi_albert_graph(n, k, r)
        elif graph_type == 'powerlaw_cluster_graph':
            x = nx.powerlaw_cluster_graph(n, k, r)
        elif graph_type == 'cycle_graph':
            x = nx.cycle_graph(n)
        else: ##Star by default
            x = nx.star_graph(len(objects)-1)
        tries += 1
        cc_conn = nx.connected_components(x)
        if len(cc_conn) == 1 or tries > 5: 
            ##best effort to create a connected graph!
            break
    return x, cc_conn

 def test__init__(self):
     from social_meaning.agent import Agent
     society = nx.watts_strogatz_graph(10, 2, 0)
     a = Agent(mental_graph=nx.fast_gnp_random_graph(10, .1),
               social_network=society,
               node_name=society.nodes()[0])
     repr(a)

def testSerialRandom():
    """ 50 Random serial test cases
    """

    N = 10
    p = .7
    runs = 0
    while runs < 50:

        # a random graph
        G = nx.fast_gnp_random_graph(N, p)
        try:
            nx.shortest_path(G, source=0, target=N-1)
        except:
            continue
        # convert to plain ndarray
        nw1 = nx2nw(G)

        # copy and join network
        nw2 = serialCopy(nw1)

        # compute effective resistance
        ER1 = ResNetwork(
            nw1, silence_level=3).effective_resistance(0, len(nw1)-1)
        ER2 = ResNetwork(
            nw2, silence_level=3).effective_resistance(0, len(nw2)-1)

        # increment runs
        runs += 1
        # assertion
        print (ER1*2-ER2)
        assert (ER1*2-ER2) < 1E-6

def getRandomPageRanks(filename):
	Ga=nx.read_graphml(sys.argv[1])

	# create a copy of the graph and extract giant component
	# get component size distribution
	cc=nx.connected_components(Ga)
	cc_dict={}
	for x in range(0,len(cc)):
		try:
			cc_dict[len(cc[x])].append(x)
		except KeyError:
			cc_dict[len(cc[x])]=[]
			cc_dict[len(cc[x])].append(x)

	isolates=nx.isolates(Ga)

	rg=nx.fast_gnp_random_graph(Ga.number_of_nodes(),2.0*Ga.number_of_edges()/(Ga.number_of_nodes()*(Ga.number_of_nodes()-1)))
	c_rg=nx.average_clustering(rg)
	rg_cc=nx.connected_component_subgraphs(rg)[0]
	rg_asp=nx.algorithms.shortest_paths.generic.average_shortest_path_length(rg_cc)

	p_rg=community.best_partition(rg_cc)
	m_rg=community.modularity(p_rg,rg_cc)

	pageranks = nx.pagerank_numpy(rg)
	return pageranks

def run_er_algo():
    """
    run homework
    """
    nodes = 10000
    prob = 0.1

    # er_graph= er_algorithm(nodes, prob)

    time0 = time.time()
    G = nx.fast_gnp_random_graph(nodes, prob, directed=True)
    digraph = nx.to_dict_of_lists(G)
    time1 = time.time()
    print('NetworkX took {} second'.format(time1 - time0))

    time0 = time.time()
    digraph2 = er_algorithm(nodes, prob)
    time1 = time.time()
    print('Mine took {} second'.format(time1 - time0))

    norm_dist1 = normal_degree_distribution(digraph, 'in')
    norm_dist2 = normal_degree_distribution(digraph2, 'in')
    plt.plot(list(norm_dist1.keys()), list(norm_dist1.values()), 'o',
             list(norm_dist2.keys()), list(norm_dist2.values()), 'g^')



    plt.show()

def get_er_graph(n, p):
    """
    Function to get an ER graph
    :param n: number of nodes
    :param p: probability of connection between the nodes
    :return: ER graph
    """
    return nx.fast_gnp_random_graph(n, p)

def generate_ER_graph_with_trust(N, p, trust_list, filename):
    N_VALS = len(trust_list)
    G = nx.fast_gnp_random_graph(N, p)
    for (u,v) in G.edges_iter():
        val = random.randint(0,N_VALS-1)
        G.edge[u][v]['t'] = trust_list[val]
        
    nx.write_edgelist(G, filename, '#', '\t', True, 'utf-8')

def main():
    numTraders = int(raw_input("Enter the number of traders : "))
    numItems = int(raw_input("Enter the number of items : "))
    G = nx.fast_gnp_random_graph(numTraders, 0.5)
    nx.draw(G, with_labels = True)
    plt.show()
    gen_data(G, numItems)
    market(G)

def construct(G1,G2): #返回一个随机ER网络,G1为现实网络，G2为在线网络
	G1 = nx.fast_gnp_random_graph(nodeNumber, probDegree)
	G2 = nx.fast_gnp_random_graph(nodeNumber, probDegree)
	r = Random()	#随机数生成器
	#现实网络
	Y = []
	for edge in G1.edges():	#边赋予权值
		id1 = edge[0]
		id2 = edge[1]
		weight = r.gauss(0.15,0.05)
		G1.edge[id1][id2]['weight'] = weight
		weight = 1 if weight>1 else weight #边界检查
		weight = 0 if weight<0 else weight
		Y.append(weight)
	displayFigure(Y,'Real LT network\'s edges\'weight distribution')

	Y = []
	for node in G1.nodes(): #点赋予阈值
		threshold = r.gauss(0.31,0.1)
		threshold = 1 if threshold>1 else threshold #边界检查
		threshold = 0 if threshold<0 else threshold
		G1.node[node]['threshold'] = threshold
		Y.append(threshold)	
		G1.node[node]['active'] = False	#点初始为不激活
	displayFigure(Y,'Real LT network\'s node\'s threshold distribution')

	#在线网络
	Y = []	
	for edge in G2.edges():#每条边赋予激活概率
		id1 = edge[0]
		id2 = edge[1]
		prob = r.gauss(0.15,0.05)
		prob = 1 if prob>1 else prob #边界检查
		prob = 0 if prob<0 else prob
		G2.edge[id1][id2]['actProb'] = prob	#边的激活高斯分布
		Y.append(prob)

		G2[id1][id2]['unuse'] = True 	#初始化为未使用过 

	for node in G2.nodes():	
		G2.node[node]['active'] = False #点初始化为不激活
		G2.node[node]['selfProb'] = 1
	displayFigure(Y,'Online IC network\'s edge\'s activate probability distribution')

	return (G1,G2)

def random_sdf_graph(n = 5, m = 15, sumrange = (2, 5), phaserange = (1, 3), wcetrange = (1, 1), seed = None):
    p = m / (n * (n - 1))
    g = nx.fast_gnp_random_graph(n, p, seed, directed = True)
    cycle = [scc.pop() for scc in nx.strongly_connected_components(g)]
    if len(cycle) > 1:
        g.add_edge( cycle[-1], cycle[0] )
        for i in range(1, len(cycle)):
            g.add_edge( cycle[i - 1], cycle[i] )

    return make_sdf_graph(g, sumrange, phaserange, wcetrange)

def test_ER_random_graph(N = 200, p = 0.2):
    
    G = nx.fast_gnp_random_graph(N, p)
    
    k = 1
    eig_vals, eig_vecs = compute_spectral_coordinate(G, k)
    
    rel_NR = graph_NR_relative(G, eig_vals, k)
    
    print "ER random graph, rel_NR =", rel_NR