def vnet_gen(snet, num_standby, fixed_node):
    """
    Generate virtual topology
    Parameters: 
    snet: the substrate network topology
    num_standby: the number of standby routers requested by a customer
    """
    node_list = snet.nodes()

    
    # minimum number of vnodes in a virtual network has to be three, but do 
    # not need to use all of the virtual nodes excluding the reserved standby 
    # virtual routers.     
    # In order to make sure every VN has a VR from a common substrate node, first remove the fixed node from the list
    rest_list = copy.deepcopy(node_list)
    rest_list.remove(fixed_node)
    vnode_in_topo = random.randint(3, len(rest_list) - num_standby)

    #vnode_in_topo = random.randint(5, len(rest_list) - num_standby)
    #vnode_in_topo = 100
    vnet_nodes = random.sample(set(rest_list), vnode_in_topo)
    vnet_nodes.append(fixed_node)
    rand_vnet = nx.gnp_random_graph(len(vnet_nodes), 0.3)
    # Avoid to create VNs with isolatd VRs
    check = check_degree(rand_vnet)
    while(check != 1):
        rand_vnet = nx.gnp_random_graph(len(vnet_nodes), 0.3)
        check = check_degree(rand_vnet)
    # relabel the nodes in the VN
    vnet = conf_vnet(rand_vnet, vnet_nodes)
    # remove selfloop edges
    vnet.remove_edges_from(vnet.selfloop_edges())
    return vnet

    def generateGraph(self, max_available_capacity):
        """
    	"""
        OSPF_weights = [2, 4]
        
        # Generate random nodes and edges
    	graph_tmp = nx.gnp_random_graph(self.n, self.p)
        while not nx.is_connected(graph_tmp):
            graph_tmp = nx.gnp_random_graph(self.n, self.p)

        # Turn it into directed graph
        graph = graph_tmp.to_directed()

        # Generate random OSPF weights and capacities
    	taken = []
        for (x,y) in graph.edges_iter():
            # Generate capacities first
            capacity = random.randint(5, max_available_capacity)
            graph[x][y]['capacity'] = capacity
            
            # Generate OSPF weights
            if (x,y) not in taken:
                # Generate random weight
                index1 = random.randint(0, 1)
                index2 = random.randint(0, 1)
                graph[x][y]['weight'] = OSPF_weights[index1]
                graph[y][x]['weight'] = OSPF_weights[index2] 
                taken.append((x,y))
                taken.append((y,x))

        return graph

def pytest_generate_tests(metafunc):
    """
    Generate the arguments for test functions.
    """

    if "graph" in metafunc.funcargnames:
        wgraphs = []

        # 100 vertex random graph
        a = nx.gnp_random_graph(100, 0.1)
        for e in a.edges_iter(data = True):
            e[2]['weight'] = triangular(-2, 2, 0)
        deg = sg.wgraph.make_deg(a.order(), create_iter(a.edges_iter(data = True)))
        b = sg.wgraph.make(a.order(), a.size(), create_iter(a.edges_iter(data = True)), deg)
        wgraphs.append((a, b))
        
        # 100 vertex random graph with parallel edges
        a = nx.gnp_random_graph(100, 0.1)
        for e in a.edges_iter(data = True):
            e[2]['weight'] = triangular(-2, 2, 0)
        deg = sg.wgraph.make_deg(a.order(), chain(create_iter(a.edges_iter(data = True)), create_iter(a.edges_iter(data = True))))
        b = sg.wgraph.make(a.order(), 2 * a.size(), chain(create_iter(a.edges_iter(data = True)), create_iter(a.edges_iter(data = True))), deg)
        wgraphs.append((a, b))
        
        # 100 vertex random graph with overestimated edge count
        a = nx.gnp_random_graph(100, 0.1)
        for e in a.edges_iter(data = True):
            e[2]['weight'] = triangular(-2, 2, 0)
        deg = sg.wgraph.make_deg(a.order(), create_iter(a.edges_iter(data = True)))
        b = sg.wgraph.make(a.order(), 2 * a.size(), create_iter(a.edges_iter(data = True)), deg)
        wgraphs.append((a, b))
        
        metafunc.parametrize("graph", wgraphs)

def pytest_generate_tests(metafunc):
    """
    Generate the arguments for test funcs
    """

    if "testgraph" in metafunc.funcargnames:
        testgraphs = []

    # 100 vertex random undirected graph
        a = nx.gnp_random_graph(100, 0.1)
        for u, v in a.edges_iter():    
            a.add_weighted_edges_from([(u, v, uniform(0, 100))])
        edge_list = []
        for u, v, w in a.edges_iter(data = True):
            edge_list.append((u, v, w['weight']))
        e = iter(edge_list)
        deg = sg.wgraph.make_deg(a.order(), e)
        e = iter(edge_list)
        b = sg.wgraph.make(a.order(), a.size(), e, deg)

    # 100 vertex random directed graph
        c = nx.gnp_random_graph(100, 0.1, directed = True)
        for u, v in c.edges_iter():    
            c.add_weighted_edges_from([(u, v, uniform(0, 100))])
        edge_list = []
        for u, v, w in c.edges_iter(data = True):
            edge_list.append((u, v, w['weight']))
        e = iter(edge_list)
        deg = sg.wdigraph.make_deg(c.order(), e)
        e = iter(edge_list)
        d = sg.wdigraph.make(c.order(), c.size(), e, deg)
        testgraphs.append((a, b, c, d))


        metafunc.parametrize("testgraph", testgraphs)

def pytest_generate_tests(metafunc):
    """
    Generate the arguments for test functions.
    """

    if "digraph" in metafunc.funcargnames:
        digraphs = []

        # 100 vertex random graph
        a = nx.gnp_random_graph(100, 0.1, directed=True)
        deg = sg.digraph.make_deg(a.order(), a.edges_iter())
        b = sg.digraph.make(a.order(), a.size(), a.edges_iter(), deg)
        digraphs.append((a, b))
        
        # 100 vertex random graph with parallel edges
        a = nx.gnp_random_graph(100, 0.1, directed=True)
        deg = sg.digraph.make_deg(a.order(), a.edges() + a.edges())
        b = sg.digraph.make(a.order(),  2 * a.size(), a.edges() + a.edges(), deg)
        digraphs.append((a, b))
        
        # 100 vertex random graph with overestimated edge count
        a = nx.gnp_random_graph(100, 0.1, directed=True)
        deg = sg.digraph.make_deg(a.order(), a.edges_iter())
        b = sg.digraph.make(a.order(), 2 * a.size(), a.edges_iter(), deg)
        digraphs.append((a, b))

        metafunc.parametrize("digraph", digraphs)

def pytest_generate_tests(metafunc):
    """
    Generate the arguments for test funcs
    """

    if "testgraph" in metafunc.funcargnames:
        testgraphs = []

        # 100 vertex random graph
        a = nx.gnp_random_graph(100, 0.1, directed=True)
        b = nx.gnp_random_graph(100, 0.1, directed=True)
        deg = sg.digraph.make_deg(a.order(), a.edges_iter())
        c = sg.digraph.make(a.order(), a.size(), a.edges_iter(), deg)
        deg = sg.digraph.make_deg(b.order(), b.edges_iter())
        d = sg.digraph.make(b.order(), b.size(), b.edges_iter(), deg)
        testgraphs.append((a, b, c, d))

        metafunc.parametrize("testgraph", testgraphs)

    if "mismatch_graph" in metafunc.funcargnames:
        mismatch_graphs = []

        a = nx.gnp_random_graph(100, 0.1, directed=True)
        b = nx.gnp_random_graph(150, 0.1, directed=True)
        deg = sg.digraph.make_deg(a.order(), a.edges_iter())
        c = sg.digraph.make(a.order(), a.size(), a.edges_iter(), deg)
        deg = sg.digraph.make_deg(b.order(), b.edges_iter())
        d = sg.digraph.make(b.order(), b.size(), b.edges_iter(), deg)
        mismatch_graphs.append((c, d))

        metafunc.parametrize("mismatch_graph", mismatch_graphs)

def generate_random_graph():
    if probability_of_graph_construction==0:
        k = rand()
    else:
        k = probability_of_graph_construction
    G=NX.gnp_random_graph(number_of_vertices, k) 
    while not(NX.is_connected(G)):
        G=NX.gnp_random_graph(number_of_vertices, k)
        k += 0.1
    return G

 def setUp(self):
     self.path = nx.path_graph(7)
     self.directed_path = nx.path_graph(7, create_using=nx.DiGraph())
     self.cycle = nx.cycle_graph(7)
     self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
     self.gnp = nx.gnp_random_graph(30, 0.1)
     self.directed_gnp = nx.gnp_random_graph(30, 0.1, directed=True)
     self.K20 = nx.complete_graph(20)
     self.K10 = nx.complete_graph(10)
     self.K5 = nx.complete_graph(5)
     self.G_list = [self.path, self.directed_path, self.cycle,
         self.directed_cycle, self.gnp, self.directed_gnp, self.K10, 
         self.K5, self.K20]

def pagerank_vs_hitting_time(num_graphs):
    graphs = []
    prs = []
    hts = []
    corrs = []
    for i in xrange(num_graphs):
        g = nx.gnp_random_graph(NUM_NODES, float(NUM_EDGES) / NUM_NODES,
                                directed=True)
        graphs.append(g)
        for e in g.edges_iter():
            g[e[0]][e[1]]['weight'] = random.random()

        prs.append(tm.pagerank(g))
        hts.append(tm.hitting_pagerank(g, 'all'))
        corrs.append(stats.spearmanr(prs[i], hts[i])[0])

        sys.stdout.write('.')

    # Plot correlations
    plt.hist(corrs)

    plt.suptitle('Correlation of PageRank and Eigen Hitting Time\n'
                 'Trials on Erdos-Renyi graphs with %d nodes and prob %0.2f'
                 % (NUM_NODES, float(NUM_EDGES) / NUM_NODES))
    plt.xlabel('Spearman rank-correlation')
    plt.ylabel('Number of graphs (independent trials)')
    plt.margins(0.07)
    plt.show()

def erdoes_3d_plot(number_of_average):
	N = np.arange(5, 105, 5)
	X = N
	P = arange(0, 0.2, 0.005)
	Y = P
	X, Y = np.meshgrid(X, Y)
	Z = X/2

	for i in range(len(N)):
		n = N[i]
		print n
		p = 0
		for j in range(len(P)):
			if n > 50 and p > 0.1:
				Z[j][i] = 100
				continue
			average = 0
			for av in range(number_of_average):
				G = nx.gnp_random_graph(n, p, None, 1)
				graph = Graph(G)
				graph.stats()
				average = average + graph.bow_tie[1]
			average = average / number_of_average
			Z[j][i] = average
			p = p + 0.01

	plot_3d(X, Y, Z, '3d_erdoes.png', 'nodes', 'probability of edge creation', 'scc [%]')

def random_weighted_graph(num_nodes, edge_prob, weight_dist='uniform'):
    """ Returns a Erdos-Renyi graph with edge weights. """
    g = nx.gnp_random_graph(num_nodes, edge_prob, directed=True)
    weights = agent_type_rv(weight_dist).rvs(size=g.number_of_edges())
    for i, e in enumerate(g.edges_iter()):
        g[e[0]][e[1]]['weight'] = weights[i]
    return g

def create_graph(N_nodes,p_edge,n_infected,regular = False):
    if regular:
        k = int(round(p_edge*(N_nodes-1)))
        G = nx.random_regular_graph(k,N_nodes)
    else:
        G = nx.gnp_random_graph(N_nodes,p_edge,directed=False)
    return set_graph_strategies(G, n_infected)

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 test_models_yaml():
    '''Creates a random models, saves them in yaml format, loads them from file,
    and compares the generated and loaded system models.
    '''
    for M, init_factory in ((Model, set), (Ts, set),
                            (Markov, lambda l: dict([(x, 1) for x in l]))):
        # generate random model
        model = M('Random system model', directed=True, multi=False)
        model.g = nx.gnp_random_graph(n=100, p=0.5, seed=1, directed=True)
        model.init = init_factory(random.sample(model.g.nodes(), 5))
        model.final = set(random.sample(model.g.nodes(), 5))

        # save system model to temporary yaml file
        f = tempfile.NamedTemporaryFile(mode='w+t', suffix='.yaml',
                                        delete=False)
        f.close()
        print('Saving', M.__name__, 'system model to', f.name)
        model.save(f.name)

        # load system model from temporary yaml file
        print('Loading', M.__name__, 'system model from', f.name)
        model2 = M.load(f.name)
    
        # test that the two system models are equal
        assert(model == model2), '{} are not equal!'.format(M.__name__)

        # remove temporary file
        os.remove(f.name)

def test_random_gnp():
    # seeds = [1550709854, 1309423156, 4208992358, 2785630813, 1915069929]
    seeds = [12, 13]

    for seed in seeds:
        G = nx.gnp_random_graph(20, 0.2, seed=seed)
        _check_edge_connectivity(G)

 def test_eigenvector_v_katz_random(self):
     G = nx.gnp_random_graph(10,0.5, seed=1234)
     l = float(max(eigvals(nx.adjacency_matrix(G).todense())))
     e = nx.eigenvector_centrality_numpy(G)
     k = nx.katz_centrality_numpy(G, 1.0/l)
     for n in G:
         assert_almost_equal(e[n], k[n])

def generate_systems(prop_step=5, o_size=20):
    """ Generate population of systems
    """
    para_range = np.linspace(0, 1, prop_step)
    o_range = np.random.uniform(0, 3, o_size)

    systs = []
    for p in para_range:
        systs.append([])

        # setup network
        graph = nx.gnp_random_graph(20, p)

        dim = len(graph.nodes())
        Bvec = np.random.uniform(0, 5, size=dim)

        for omega in o_range:
            # setup dynamical system
            system_config = get_base_config(
                nx.to_numpy_matrix(graph), Bvec, omega)

            systs[-1].append(DW({
                'graph': graph,
                'system_config': system_config
            }))

    return systs, para_range

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 connect_gnp(self,N,p):
     """
     Erdos-Renyi (Poisson random) graph G(N,p).
     """
     # this is kind of a dumb way to do this
     self.connect_empty(N)
     self.add_edges_from(nx.gnp_random_graph(N,p).edges())

def barabasi_gen(start_size, total_size, m):
    """
    Generate a graph according to the process outlined in Barabasi
    and Albert, where vertices are added one at a time, and attach to
    existing vertices with probability:
        p(existing) = deg(existing) / sum(deg(all_vertices))
    """
    if m > start_size:
        print("m must be >= than the initial number of vertices")
        return None
    # Start with an Erdos-Renyi random graph?
    g = networkx.gnp_random_graph(start_size, p=(m / start_size))
    # Need to number each node, so start with:
    new_node = start_size + 1
    while len(g) < total_size:
        # Create the list of other nodes before adding the new node,
        # easiest way to do it
        others = g.nodes()
        # Calculate the probabilities every time, or find a cleverer
        # way of updating the values?
        total_degree = sum(deg for node, deg in g.degree_iter())
        g.add_node(new_node)
        while g.degree(new_node) < m:
            node_to_check = random.choice(others)
            prob = g.degree(node_to_check) / total_degree
            dice_roll = random.random()
            if dice_roll < prob:
                g.add_edge(new_node, node_to_check)
        new_node += 1
    return g