def ws_gen(n, k, p):
    """ 
    Given some parameterization n, k, p, generate a random WS network and calucualte C(p) and L(p)
    """
    G=nx.watts_strogatz_graph(n, k, p)
    while nx.number_connected_components(G)>1:
        G=nx.watts_strogatz_graph(n, k, p)
    return({'p':p, 'cc':nx.average_clustering(G), 'avg.pl':nx.average_shortest_path_length(G)})

	def create_network(self):
		if self.network_topology == "small-world":
			G = nx.watts_strogatz_graph(self.number_of_agents, self.mean_degree, self.watts_strogatz_rewiring_probability)
		elif self.network_topology == "scale-free":
			G = nx.barabasi_albert_graph(self.number_of_agents, int(self.mean_degree/2))
		elif self.network_topology == "ring":
			G = nx.watts_strogatz_graph(self.number_of_agents, self.mean_degree, 0)
		elif self.network_topology == "random":
			G = nx.watts_strogatz_graph(self.number_of_agents, self.mean_degree, 1)

		mapping = dict(enumerate(self.agents_list))
		self.agents_network = nx.relabel_nodes(G, mapping)

def generate_graph(n, expected_degree, model="ba"):
    """
    Generates a graph with a given model and expected_mean
    degree

    :param n: int Number of nodes of the graph
    :param expected_degree: int Expected mean degree
    :param model: string Model (ba, er, or ws)
    :return: networkx graph
    """

    global m
    global ws_p

    g = None
    if model == "ba":
        # BA expected avg. degree? m = ba_mean_degrees()
        if m is None:
            m = ba_mean_degrees(n, expected_degree)
        g = nx.barabasi_albert_graph(n, m, seed=None)
    if model == "er":
        # ER expected avg. degree: d = p*(n-1)
        p = float(expected_degree) / float(n - 1)
        g = nx.erdos_renyi_graph(n, p, seed=None, directed=False)
    if model == "ws":
        # WS expected degree == k
        g = nx.watts_strogatz_graph(n, expected_degree, ws_p)

    return g

def edge_attachment_test(seed=None):
    import math
    if seed==None:
        seed = npr.randint(1E6)
    print('rnd seed: %d'%seed)
    npr.seed(seed)
    random.seed(seed)

    nn = 30
    G = nx.watts_strogatz_graph(n=nn, k=4, p=0.0)
    print('All new edges should lie close to the cycle')

    pos = {node:(math.cos(float(node)/nn * math.pi * 2),math.sin(float(node)/nn * math.pi * 2)) for node in G}

    def visualize_rewiring(G, added_edges_set, deled_edges_set, tpl_data):
        old_G = G.copy()
        old_G.remove_edges_from(added_edges_set)
        old_G.add_edges_from(deled_edges_set)
        print('added edges: ')
        print(added_edges_set)
        print('deled edges: ')
        print(deled_edges_set)
        benchmarks.editing_demo_draw(G=old_G, new_G=G, seed=1, pos=pos)
        print(tpl_data)
        pylab.show()

    params = {}
    params['edit_edges_tester'] = visualize_rewiring
    params['edge_edit_rate']    = [0.10]
    params['node_edit_rate']    = [0.]
    params['node_growth_rate']  = [0.]
    params['verbose'] = True

    algorithms.generate_graph(G, params=params)

    def __init__(self, n=1000, k=10, p=0.02947368):
        self.n = n
        self.k = k
        self.p = p
        self.ws = nx.watts_strogatz_graph(self.n, self.k, self.p, seed='nsll')
        nx.set_node_attributes(self.ws, 'SIR', 'S')
        self.clustering = nx.clustering(self.ws)
        self.betweenness = nx.betweenness_centrality(self.ws)
        p_r_0 = 0.001
        r_0 = int(self.n * p_r_0)
        if r_0 < 1:
            r_0 = 1
        random.seed('nsll')
        self.r = random.sample(self.ws.nodes(), r_0)

        i_0 = 4
        if i_0 < r_0:
            i_0 += 1
        random.seed('nsll')
        self.infected = random.sample(self.ws.nodes(), i_0)
        for n in self.infected:
            self.ws.node[n]['SIR'] = 'I'
        for n in self.r:
            self.ws.node[n]['SIR'] = 'R'
        self.s = self.n - len(self.infected) - len(self.r)
        print(self.r)
        print(self.infected)

def q1():
  # given in question
  infection_rate = 0.25
  recovery_rate = 0.30
  # from NetLogo model file (may be incorrect!)
  num_nodes = 200
  num_neighbors = 4
  xvals = range(0, 20000)
  for p_rewire in [0.0, 1.0]:
    G = nx.watts_strogatz_graph(num_nodes, num_neighbors, p_rewire)
    infected = np.zeros(num_nodes, dtype=int)
    # randomly infect one of the nodes
    random_node = random.uniform(0, num_nodes)
    infected[random_node] = 1
    yvals = []
    for xval in xvals:
      for node in range(0, num_nodes):
        if infected[node] == 1:
          if random.uniform(0, 1) <= recovery_rate:
            infected[node] = 0
            continue
          if random.uniform(0, 1) <= infection_rate:
            neighbors = G[node].keys()
            for neighbor in neighbors:
              infected[neighbor] = 1
      num_infected = len(infected[infected == 1])
      print("For p=%f, timeunit=%d, #-infected=%d" % 
        (p_rewire, xval, num_infected))
      yvals.append(num_infected)
    plt.plot(xvals, yvals, color='b' if p_rewire == 0 else 'r')
  plt.show()

def patch_nx():
    """Temporary fix for NX's watts_strogatz routine, which has a bug in versions 1.1-1.3
    """

    import networkx as nx

    # Quick test to see if we get the broken version
    g = nx.watts_strogatz_graph(2, 0, 0)

    if g.number_of_nodes() != 2:
        # Buggy version detected.  Create a patched version and apply it to nx
        
        nx._watts_strogatz_graph_ori = nx.watts_strogatz_graph        

        def patched_ws(n, k, p, seed=None):
            if k<2:
                g = nx.Graph()
                g.add_nodes_from(range(n))
                return g
            else:
                return nx._watts_strogatz_graph_ori(n, k, p, seed)

        patched_ws.__doc__ = nx._watts_strogatz_graph_ori.__doc__

        # Applying monkeypatch now
        import warnings
        warnings.warn("Monkeypatching NetworkX's Watts-Strogatz routine")

        nx.watts_strogatz_graph = patched_ws

 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 compare_graphs(graph):
    n = nx.number_of_nodes(graph)
    m = nx.number_of_edges(graph)
    k = np.mean(list(nx.degree(graph).values()))
    erdos = nx.erdos_renyi_graph(n, p=m/float(n*(n-1)/2))
    barabasi = nx.barabasi_albert_graph(n, m=int(k)-7)
    small_world = nx.watts_strogatz_graph(n, int(k), p=0.04)
    print(' ')
    print('Compare the number of edges')
    print(' ')
    print('My network: ' + str(nx.number_of_edges(graph)))
    print('Erdos: ' + str(nx.number_of_edges(erdos)))
    print('Barabasi: ' + str(nx.number_of_edges(barabasi)))
    print('SW: ' + str(nx.number_of_edges(small_world)))
    print(' ')
    print('Compare average clustering coefficients')
    print(' ')
    print('My network: ' + str(nx.average_clustering(graph)))
    print('Erdos: ' + str(nx.average_clustering(erdos)))
    print('Barabasi: ' + str(nx.average_clustering(barabasi)))
    print('SW: ' + str(nx.average_clustering(small_world)))
    print(' ')
    print('Compare average path length')
    print(' ')
    print('My network: ' + str(nx.average_shortest_path_length(graph)))
    print('Erdos: ' + str(nx.average_shortest_path_length(erdos)))
    print('Barabasi: ' + str(nx.average_shortest_path_length(barabasi)))
    print('SW: ' + str(nx.average_shortest_path_length(small_world)))
    print(' ')
    print('Compare graph diameter')
    print(' ')
    print('My network: ' + str(nx.diameter(graph)))
    print('Erdos: ' + str(nx.diameter(erdos)))
    print('Barabasi: ' + str(nx.diameter(barabasi)))
    print('SW: ' + str(nx.diameter(small_world)))

def correlation_betweenness_degree_on_WS():
    n = 1000
    k = 4
    p = 0.01
    G = nx.watts_strogatz_graph(n, k, p)

    print nx.info(G)
    ND, ND_lambda = ECT.get_number_of_driver_nodes(G)
    ND, driverNodes = ECT.get_driver_nodes(G)

    degrees = []
    betweenness = []

    tot_degree = nx.degree_centrality(G)
    tot_betweenness = nx.betweenness_centrality(G,weight=None)

    for node in driverNodes:
        degrees.append(tot_degree[node])
        betweenness.append(tot_betweenness[node])

    with open("results/driver_degree_WS.txt", "w") as f:
        for x in degrees:
            print >> f, x
    with open("results/driver_betweenness_WS.txt", "w") as f:
        for x in betweenness:
            print >> f, x

    with open("results/tot_degree_WS.txt", "w") as f:
        for key, value in tot_degree.iteritems():
            print >> f, value

    with open("results/tot_betweenness_WS.txt", "w") as f:
        for key, value in tot_betweenness.iteritems():
            print >> f, value

def playwithkmeans(n=50,k=3,p=0.6,save=False):
    '''randomly generate a random Watts-Strogatz graph with 
    n - nodes
    k - connected to k neighbors
    p - rewiring from base NN ring with prob b. 
    Labeled graph is plotted according to kmeans clust=3 
    to see by eye how "well" it does 
    WH StatConn HW 1
    '''
    G = nx.watts_strogatz_graph(n,k,p)
    pos = nx.random_layout(G)
    adjmat = nx.to_numpy_matrix(G)
    km = KMeans(n_clusters=3)
    kmfit = km.fit(adjmat)
    l = kmfit.labels_ 
    c1 = []
    c2 = []
    c3 = []
    for i,x in enumerate(l):
        if x == 0:
            c1.append(i)
        if x == 1:
            c2.append(i)
        if x == 2:
            c3.append(i)
    nx.draw_networkx_nodes(G,pos,nodelist=c1,node_color='r',node_size=500,alpha=0.8)
    nx.draw_networkx_nodes(G,pos,nodelist=c2,node_color='g',node_size=500,alpha=0.8)
    nx.draw_networkx_nodes(G,pos,nodelist=c3,node_color='b',node_size=500,alpha=0.8)
    nx.draw_networkx_edges(G,pos)
    plt.title('Random Graph G with color-coded overlay of kmeans clustering k=3')
    if save:
        plt.savefig('C:\\Users\Will\\Pictures\\graph-%s.pdf'%date.today(),format='pdf')
    plt.show()

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 __init__(self, iter_count, step_count, G=None, **kwargs):
        '''
        Set up a new batch runner.

        Args:
            iter_count: Number of model instances to create and run
            step_count: How many steps to run each model for.
            G: If not None, initialize all models on the same graph. 
            **kwargs: Any model parameters to set.
        '''

        self.model_outputs = []
        self.models = []
        self.outputs = []
        self.step_count = step_count

        # Prepare models
        while len(self.models) < iter_count:
            if G is None:
                # Here comes the hard-coded bit
                G = nx.watts_strogatz_graph(10, 3, 0.2)
                if not nx.is_connected(G): continue
            
            m = Model(G)
            # Set the parameters:
            for attr, val in kwargs.items():
                if hasattr(m, attr):
                    setattr(m, attr, val)

            # Coerce minimum and maximum depth
            # TODO: Better solution for this
            for agent in m.agents.values():
                agent.max_depth = random.randint(m.min_depth, m.max_depth)

            self.models.append(m)

def generateRandomNetworks(randomSeed=622527):
    seed(randomSeed)
    # Network size will be 10^1, 10 ^2, 10^3, 10^4
    for exponent in range(1, 4): # 1 .. 4
        n = 10 ** exponent

        for p in [0.1, 0.3, 0.5, 0.7, 0.9]:
            m = round(n * p)

            # Generate erdos Renyi networks
            graph = nx.erdos_renyi_graph(n, p, randomNum())
            graphName = "erdos_renyi_n{}_p{}.graph6".format(n, p)
            nx.write_graph6(graph, directory + graphName)

            # Generate Barabasi Albert networks
            graph = nx.barabasi_albert_graph(n, m, randomNum())
            graphName = "barabasi_albert_n{}_m{}.graph6".format(n, m)
            nx.write_graph6(graph, directory + graphName)

            for k in [0.1, 0.3, 0.5, 0.7, 0.9]:
                k = round(n * k)
                # Generate Watts Strogatz networks
                graph = nx.watts_strogatz_graph(n, k, p, randomNum())
                graphName = "watts_strogatz_n{}_k{}_p{}.graph6".format(n, k, p)
                nx.write_graph6(graph, directory + graphName)

 def generate_network(self):
     net_type_dict = dict(
         complete=nx.complete_graph(self.N),
         barabasi_albert=nx.barabasi_albert_graph(self.N,self.k),
         watts_strogatz=nx.watts_strogatz_graph(self.N,self.k,
                                                self.rewiring_prob),
     )
     return net_type_dict[self.net_type]

def create_WS_graphs(N, betas):
    """Creates list of Newman W-S graphs with N nodes and rewiring probabilities corresponding to the values in betas"""
    NUM_NEIGHBORS = 2

    graphs = []
    for beta in betas:
        graphs.append(networkx.watts_strogatz_graph(N, NUM_NEIGHBORS, beta))
    return graphs

def get_ws_graph(n, p):
    """
    Function to get a WS graph with 4 k-nearest-neighbors
    :param n: number of nodes
    :param p: probability of connection between the nodes
    :return: WS graph
    """
    return nx.watts_strogatz_graph(n, 4, p)

 def connect_watts_strogatz(self,N,k,p):
     """
     Watts-Strogatz graph starting with a k-nearest neighbor ring.  Edges are then rewired with
     probability p.  This differs from the NWS graph in that (1) it may not be connected and
     (2) the mean degree will be fixed at k.
     """
     self.connect_empty(N)
     self.add_edges_from(nx.watts_strogatz_graph(N,k,p).edges())

def watts_new(n,nb,pr,double_swap=False):

	Gs=nx.Graph()
	if double_swap==False:
		Gw=nx.watts_strogatz_graph(n, nb, pr)
	else:
		Gw=nx.watts_strogatz_graph(n, nb, 0.0)
		nx.double_edge_swap(Gw, nswap=int(pr*n*nb/2.), max_tries=10000)
		
	Gs.add_nodes_from(Gw.nodes(),state=1.0,parameters={})
	
	Gs.add_edges_from(Gw.edges(),weight=1.0)
	
	##remove self-edges
	Gs.remove_edges_from(Gs.selfloop_edges())
	
	return Gs

def create_small_world_graph(N_nodes,p_edge,n_infected):
    n = N_nodes
    k = int(p_edge*N_nodes)
    p = 0.5
    #Random graph
    #p_coop is the fraction of cooperators
    G = nx.watts_strogatz_graph(n,k,p)
    return set_graph_strategies(G, n_infected)