def gen_single_graph(pos, attr, dist_key):
	global group_counter
	global config
	global attribute

	s_levels = range(1, 6)
	u_levels = range(1, 6)

	G = nx.gnm_random_graph(18, 25)
	while not nx.is_connected(G):
		G = nx.gnm_random_graph(18, 25)
	for e in G.edges():
		G[e[0]][e[1]]['strength'] = random.choice(s_levels)
		G[e[0]][e[1]]['certainty'] = random.choice(u_levels)
	
	counter = 0
	attr_values = list(dist_template[dist_key])
	random.shuffle(attr_values)
	for e in G.edges():
		G[e[0]][e[1]][attr] = attr_values[counter]
		counter += 1

	# write json formatted data
	d = json_graph.node_link_data(G) # node-link format to serialize
	# write json
	output_name = 'task_cp_' + attribute + '_' + config + '_' + str(group_counter) + '_' + pos + '.json'
	output = open(output_name, 'w')
	json.dump(d, output, indent=2, separators=(', ', ':' ))
	print('Wrote node-link JSON data to ' + output_name)

 def randomize_graph(self, n, e):
     """
     Creates 1000 random graphs with
     networkx.gnm_random_graph(nodecount, edgecount),
     and computes average_clustering_coefficient and
     average_shortest_path_length, to compare with drama-graph.
     Returns a tuple:
     randavgpathl, randcluster = (float or "NaN", float or "NaN")
     """
     randcluster = 0
     randavgpathl = 0
     # what is c, what is a, what is n, what is e?
     # e=edges?, c=clustering_coefficient?, a=average_shortest_path_length?
     c = 0
     a = 0
     if not self.randomization:  # hack so that quartett poster works
         self.randomization = 50
     for i in tqdm(range(self.randomization), desc="Randomization",
                   mininterval=1):
         R = nx.gnm_random_graph(n, e)
         try:
             randcluster += nx.average_clustering(R)
             c += 1
         except ZeroDivisionError:
             pass
         j = 0
         while True:
             j += 1
             try:
                 R = nx.gnm_random_graph(n, e)
                 randavgpathl += nx.average_shortest_path_length(R)
                 a += 1
             except:
                 pass
             else:
                 break
             if j > 50:
                 randavgpathl = "NaN"
                 break
     try:
         randcluster = randcluster / c
     except:
         randcluster = "NaN"
     try:
         randavgpathl = randavgpathl / a
     except:
         randavgpathl = "NaN"
     return randavgpathl, randcluster

def test_layouts():
    G =nx.gnm_random_graph(10,15)

    rand = [nx.random_layout(G)]
    circ = [nx.circular_layout(G)]
    #shell = [nx.shell_layout(G)] #same as circular layout...
    spectral = [nx.spectral_layout(G)]
    tripod = [tripod_layout(G)]

    layouts = [rand,circ,spectral, tripod]
    regimes = ["random","circular","spectral", "tripod"]

    for layout in layouts:
        layout.append(nx.spring_layout(G,2,layout[0]))
        layout.append(iterate_swaps(G,layout[0]))
        layout.append(nx.spring_layout(G,2,layout[2]))
        layout.append(greedy_swapper(G,layout[0]))

    # Now have list of lists... Find lengths of edgecrossings...

    num_crossings = []
    for layout in layouts:
        for sublayout in layout:
            num_crossings.append(count_crosses(G,sublayout))

    names = []
    for regime in regimes:
        names.append(regime)
        names.append(regime + "-spring")
        names.append(regime + "-swap")
        names.append(regime + "-swap-spr")
        names.append(regime + "-greedy")

    return G, layouts, names, num_crossings

 def generate_random_graph(self):
     print 'performer.generate_random_graph:', self.NODE_COUNT, self.EDGE_COUNT
     while True:
         graph = gnm_random_graph(self.NODE_COUNT, self.EDGE_COUNT)
         if self.constraints_satisfied(graph):
             self.process_graph(graph)
             return graph

def MinDistanceGraphFinder(number_of_vertices,number_of_edges):
		
	if number_of_edges<number_of_vertices-1:
		print 'Too few edges. The graph will be disconnected. Exiting...'
		return -1
	if number_of_edges>(number_of_vertices-1)*number_of_vertices/2.0:
		print 'Too many edges. Such a graph cannot exist. Exiting...'
		return -1
		
	if number_of_edges>(number_of_vertices-2)*(number_of_vertices-1)/2.0:
		OutputGraph=nx.gnm_random_graph(number_of_vertices,number_of_edges)
		return OutputGraph
	
	
	G=nx.star_graph(number_of_vertices-1)
	VertexList=G.nodes()
	remaining_edges=number_of_edges-number_of_vertices+1
	
	while remaining_edges>0:
		first_vertex=random.choice(VertexList)
		second_vertex=random.choice(VertexList)
		if first_vertex==second_vertex:continue
		if (first_vertex,second_vertex) in G.edges():continue
		if (second_vertex,first_vertex) in G.edges():continue
		
		G.add_edge(first_vertex,second_vertex)
		remaining_edges-=1
		
	OutputGraph=G.copy()
		
	return OutputGraph

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 losowy_graf(self, n, m, maks_cap, orient):
     g = nx.gnm_random_graph(n, m)
     graf = [ [] for x in range(0, n)]
 #    print str(graf)
     c = zeros((n, n))
     for i in range(0, n):
         for j in range(0,n):
             if i < j: # gererujemy graf nieskierowany
                 c[i,j] = random.randint(0, maks_cap)
                 if orient:
                     c[j,i] = c[i,j]
                 else:
                     c[j,i] = random.randint(0, maks_cap)
     if orient:
         self.zorientowany = True
     #print str(g.edges())
     for (u,v) in g.edges():
 #        print 'Dodajemy wierzcholek'
         (graf[u]).append(v)
         graf[v].append(u)
     #print str(graf)
 #    for u in range(0,n):
 #        for v in graf[u]:
 #            print str(u) + ' -> '+ str(v)
     return (graf, c)

 def generate_graph(self):
     n = self._num_of_nodes
     m = self._num_of_edges
     G = networkx.gnm_random_graph(n, m)
     for u, v in G.edges():
         G[u][v]["weight"] = 1
     return G

def measure_single(graph_size):
	global args
	time_results = []
	memory_results = []

	print('graph size={}:'.format(graph_size), end=' ')
	for density in args.densities:
		vertices = compute_vertices_count(graph_size, density)
		edges = graph_size - vertices

		nx_graph = nx.gnm_random_graph(vertices, edges, directed=True)
		if nx_graph.number_of_nodes() + nx_graph.number_of_edges() != graph_size:
			time_results.append(float('nan'))
			memory_results.append(float('nan'))
			continue
		print('[D={} |V|={} |E|={}]'.format(density, nx_graph.number_of_nodes(), nx_graph.number_of_edges()), end=' ')

		stats = get_stats(args.repetitions, args.multiplication, [args.algorithm], nx_graph, args.garbage_collection)
		time_results.append(round(min(stats[args.algorithm]['time']), 5))
		memory_results.append(stats[args.algorithm]['memory'] / float(2**20))

	print()
	for res in [(time_results, '_time.csv'), (memory_results, '_memory.csv')]:
		with open(args.output + res[1], 'a') as csvfile:
			writer = csv.writer(csvfile)
			row = [graph_size] + res[0]
			writer.writerow(row)

def measure_multi(graph_size):
	global args

	vertices = compute_vertices_count(graph_size, args.density)
	edges = graph_size - vertices

	nx_graph = nx.gnm_random_graph(vertices, edges, directed=True)
	if nx_graph.number_of_nodes() + nx_graph.number_of_edges() != graph_size:
		return

	print('graph size={}: [D={} |V|={} |E|={}]'.format(graph_size, args.density,
		nx_graph.number_of_nodes(), nx_graph.number_of_edges()))

	stats = get_stats(args.repetitions, args.multiplication, args.algorithms, nx_graph, args.garbage_collection)

	#extract minimal time from all measured times
	for key in stats:
		stats[key]['time'] = round(min(stats[key]['time']), 5)

	#write time and memory values into files as CSV
	for res_type in ['time', 'memory']:
		with open(args.output + '_' + res_type + '.csv', 'a') as csvfile:
			writer = csv.writer(csvfile)
			row = [graph_size] + [stats[key][res_type] for key in sorted(stats)]
			writer.writerow(row)

	def random_graph(self):
		
		#Compute graph and caculate average path length, clustering coeff 
		logging.info('Inside random graph')
		RG = nx.gnm_random_graph(self.node_count, self.edge_count)
		RG = nx.connected_component_subgraphs(RG.to_undirected())[0]
		self.average_shortest_path_length('Random graph', RG)
		self.global_clustering_coefficient('Random graph', RG)

 def connect_fixed_edges(self,N,p):
     """
     A fixed fraction of the total possible N*(N-1)/2 connections are made. (Not a binomial
     graph!  The number of edges is always p*N(N-1)/2, not just in the N->infinity limit.)
     """
     self.connect_empty(N)
     dN = int(p*N*(N-1)/2)
     self.add_edges_from(nx.gnm_random_graph(N,dN).edges())

def random_graph_heterogeneous_synapses(cell_positions):
    h = spatial_graph_2010(cell_positions)
    weights = [e[2]['weight'] for e in h.edges(data=True)]
    random.shuffle(weights)
    g = nx.gnm_random_graph(h.order(), h.size())
    for k, e in enumerate(g.edges()):
        g[e[0]][e[1]]['weight'] = weights[k]
    return g

    def obtain_graph(args):
        """Build a Graph according to command line arguments

        Arguments:
        - `args`: command line options
        """
        if hasattr(args,'gnd') and args.gnd:

            n,d = args.gnd
            if (n*d)%2 == 1:
                raise ValueError("n * d must be even")
            G=networkx.random_regular_graph(d,n)
            return G

        elif hasattr(args,'gnp') and args.gnp:

            n,p = args.gnp
            G=networkx.gnp_random_graph(n,p)

        elif hasattr(args,'gnm') and args.gnm:

            n,m = args.gnm
            G=networkx.gnm_random_graph(n,m)

        elif hasattr(args,'grid') and args.grid:

            G=networkx.grid_graph(args.grid)

        elif hasattr(args,'torus') and args.torus:
            
            G=networkx.grid_graph(args.torus,periodic=True)

        elif hasattr(args,'complete') and args.complete>0:

            G=networkx.complete_graph(args.complete)

        elif args.graphformat:

            G=readGraph(args.input,args.graphformat)
        else:
            raise RuntimeError("Invalid graph specification on command line")

        # Graph modifications
        if hasattr(args,'plantclique') and args.plantclique>1:

            clique=random.sample(G.nodes(),args.plantclique)

            for v,w in combinations(clique,2):
                G.add_edge(v,w)

        # Output the graph is requested
        if hasattr(args,'savegraph') and args.savegraph:
            writeGraph(G,
                       args.savegraph,
                       args.graphformat,
                       graph_type='simple')

        return G

def graphFactoryPlanar(nb_graph, size_graph, graphtype, section='all'):
    cpt = 0
    while cpt <= nb_graph:
        m = np.random.random_sample(1)
        G = nx.gnm_random_graph(size_graph,edgeForDensity(size_graph,m))
        if graphToCSV(G,graphtype,section,pl.is_planar(G)):
            cpt+=1
            if cpt%10 == 0:
                print(str(cpt)+'/'+str(nb_graph)+' '+str(100*cpt/nb_graph)+'%')

def demo():
    '''
    Run a demo showing how a random, ugly network graph evolves into
    a much nicer-looking graph.
    '''
    size = 8
    G = nx.gnm_random_graph(size,11)
    seed = nx.spring_layout(G)
    evol = run_simulation(G,seed)

def graphFactoryPlanarNormalDistribution(nb_graph,size_graph,graphtype,location,spread,section='all'):
    cpt=0
    while cpt <= nb_graph:
        rdm_density = np.random.normal(location,spread)
        G = nx.gnm_random_graph(size_graph,edgeForDensity(size_graph,rdm_density))
        if graphToCSV(G,graphtype,section,pl.is_planar(G)):
            cpt+=1
            if cpt%10 == 0:
                print(str(cpt)+'/'+str(nb_graph)+' '+str(100*cpt/nb_graph)+'%')

def build_random_network(n=100, m=300, directed=False):
    """
    Builds a random network with n nodes (default n=100) and m edges
    (default m=300).
    """

    network = nx.gnm_random_graph(n, m, directed=directed)

    return network

def RandomGNM(n, m, dense=False, seed=None):
    """
    Returns a graph randomly picked out of all graphs on n vertices
    with m edges.

    INPUT:


    -  ``n`` - number of vertices.

    -  ``m`` - number of edges.

    -  ``dense`` - whether to use NetworkX's
       dense_gnm_random_graph or gnm_random_graph


    EXAMPLES: We show the edge list of a random graph on 5 nodes with
    10 edges.

    ::

        sage: graphs.RandomGNM(5, 10).edges(labels=False)
        [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

    We plot a random graph on 12 nodes with m = 12.

    ::

        sage: gnm = graphs.RandomGNM(12, 12)
        sage: gnm.show()  # long time

    We view many random graphs using a graphics array::

        sage: g = []
        sage: j = []
        sage: for i in range(9):
        ...    k = graphs.RandomGNM(i+3, i^2-i)
        ...    g.append(k)
        ...
        sage: for i in range(3):
        ...    n = []
        ...    for m in range(3):
        ...        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
        ...    j.append(n)
        ...
        sage: G = sage.plot.graphics.GraphicsArray(j)
        sage: G.show()  # long time
    """
    if seed is None:
        seed = current_randstate().long_seed()
    import networkx

    if dense:
        return graph.Graph(networkx.dense_gnm_random_graph(n, m, seed=seed))
    else:
        return graph.Graph(networkx.gnm_random_graph(n, m, seed=seed))

def demo_evolution():
    '''
    Run a demo showing how a random, ugly network graph evolves into
    a much nicer-looking graph, using an asexually-reproducing
    evolutionary algorithm.
    '''
    size = 8
    G = nx.gnm_random_graph(size,11)
    seed = nx.spring_layout(G)
    evol = evolve_asexually(G,seed)