def RBR(Na, Nb, za, zb, p):
	'''
	Return a NetworkX graph composed of two random za-, zb-regular graphs of sizes Na, Nb,
	with Bernoulli(p) distributed coupling.
	'''
	network_build_time = time.time()
	
	a_internal_graph = nx.random_regular_graph(za, Na)
	b_internal_graph = nx.random_regular_graph(zb, Nb)

	a_inter_stubs = [bern(p) for i in xrange(Na)]
	b_inter_stubs = [bern(p*float(Na)/float(Nb)) for i in xrange(Nb)]
	while sum(a_inter_stubs) != sum(b_inter_stubs) or abs(sum(a_inter_stubs)-(p*Na)) > 0:
		a_inter_stubs = [bern(p) for i in xrange(Na)]
		b_inter_stubs = [bern(p*float(Na)/float(Nb)) for i in xrange(Nb)]
	
	G = nx.bipartite_configuration_model(a_inter_stubs, b_inter_stubs)
	
	for u, v in a_internal_graph.edges():
		G.add_edge(u, v)
	for u, v in b_internal_graph.edges():
		G.add_edge(Na+u, Na+v)
	
	network_build_time = time.time() - network_build_time
	print('Generating the network took {0:.3f} seconds, {1:.3f} minutes, {2:.3f} hours.'.format(network_build_time, network_build_time/60.0, network_build_time/3600.0))
	return G

def generate_random_regular():
    d = randint(2,number_of_vertices-1)
    G = NX.random_regular_graph(d, number_of_vertices)
    while not (G and NX.is_connected(G)):
        d = randint(2, number_of_vertices-1)
        G = NX.random_regular_graph(d, number_of_vertices)

    return G

def regular(size, degree, seed=None):
    assert size > 0
    assert degree >= 0

    if seed:
        g = nx.random_regular_graph(d=degree, n=size, seed=seed)
    else:
        g = nx.random_regular_graph(d=degree, n=size)

    g.name = 'Random Regular Graph: {n} nodes, {d} degree'.format(n=size,
                                                                  d=degree)
    return g

def main():

    msg = "usage: ./p2p2012.py type r|g|g2 ttl par tries churn_rate"

    if len(sys.argv) < 7:
        print msg
        sys.exit(1)

    global out_file, churn_rate
    out_file = sys.stdout

    gtype = sys.argv[1]
    walk = sys.argv[2]
    ttl = int(sys.argv[3])
    par = int(sys.argv[4])
    tries = int(sys.argv[5])
    churn_rate = float(sys.argv[6])

    if gtype == "a":
        g = nx.barabasi_albert_graph(97134, 3)
    elif gtype == "b":
        g = nx.barabasi_albert_graph(905668, 12)
    elif gtype == "c":
        g = sm.randomWalk_mod(97134, 0.90, 0.23)
    elif gtype == "d":
        g = sm.randomWalk_mod(905668, 0.93, 0.98)
    elif gtype == "e":
        g = sm.nearestNeighbor_mod(97134, 0.53, 1)
    elif gtype == "f":
        g = sm.nearestNeighbor_mod(905668, 0.90, 5)
    elif gtype == "g":
        g = nx.random_regular_graph(6, 97134)
    elif gtype == "h":
        g = nx.random_regular_graph(20, 905668)
    elif gtype == "i":
        g = nx.read_edgelist(sys.argv[7])

    if walk == "r":
        lookup(g, ttl, tries, par, get_random_node)
    elif walk == "g":
        lookup(g, ttl, tries, par, get_greedy_node)
    elif walk == "g2":
        lookup(g, ttl, tries, par, get_greedy2_node)
    elif walk == "sum":
        sum_edges(g, int(sys.argv[3]))

    nodes = g.number_of_nodes()
    edges = g.size()
    avg_cc = nx.average_clustering(g)

    print >> sys.stderr, nodes, edges, avg_cc

def regular_D(n,d,D):
  while True:
    G=nx.random_regular_graph(d,n)
    if nx.is_connected(G):
      diameter = nx.diameter(G)
      if diameter == D:
        return G

 def setup_network(self):
     # make an adjacency matrix
     n = self.params.number_agents
     # make a random graph of links, all nodes have
     # a fixed number of neighbors. will want to add more controls
     # here later.
     self.neighbors = nx.random_regular_graph(NUM_NEIGHBORS, n + (n % 2))

def add_edges_to_groups(output_graph, groups_list, edges_to_add, prob, level):
    global template_created
    total_groups = len(groups_list)
    edges_per_node = max((3 - level), 1)
    triangle_prob = 0.1*level
    if False:
        random_graph = nx.random_regular_graph(int(total_groups/3), total_groups)
    else:
        random_graph = nx.powerlaw_cluster_graph(total_groups, edges_per_node, triangle_prob, random.random()*10)

    if template_created:
        template_created = False
        plt.axis('off')
        position = nx.graphviz_layout(random_graph, prog='sfdp')
        nx.draw_networkx_nodes(random_graph, position, node_size=30, node_color='r') #output_graph.degree().values())
        nx.draw_networkx_edges(random_graph, position, alpha=0.3)
        plt.savefig(dataset_name2 +"/"+ "template_" + image_name, bbox_inches='tight', dpi=500)
        print "plot saved as ", image_name
    
    random_edges = random_graph.edges()
    
    for edge in random_edges:
        e0 = edge[0]
        e1 = edge[1]
        if random.random() > 0.3:
            e0, e1 = e1, e0
        print("adding level{} edges between group{} and group{}".format(level, e0, e1))
        add_edges_to_two_groups(output_graph, groups_list[e0], groups_list[e1], edges_to_add, prob)

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 connect_fixed_degree(self,N,p):
     """
     All nodes have identical degree; they are each randomly connected to p*N other nodes.
     If p > 1 - 1/N, this will return the regular, fully connected graph.'
     """
     self.connect_empty(N)
     d = int(p*N)
     self.add_edges_from(nx.random_regular_graph(d,N).edges())

    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 generate_network(mem_pars, net_pars):
    if net_pars['type']==graph_type[1]:
        G = nx.watts_strogatz_graph(net_pars['N'],net_pars['k'],net_pars['p'])
    elif net_pars['type']==graph_type[2]:
        G = nx.random_regular_graph(net_pars['degree'], net_pars['N'])

    cir = Circuit('Memristor network test')

    # assign dictionary with terminals and memristors
    memdict = {}

    w = mem_pars['w']
    D = mem_pars['D']
    Roff = mem_pars['Roff']
    Ron = mem_pars['Ron']
    mu = mem_pars['mu']
    Tao = mem_pars['Tao']

    for e in G.edges_iter():
        rval = round(Roff + 0.01 * Roff * (random.random() - 0.5), 2)
        key = 'R' + str(e[0]) + str(e[1])
        [v1, v2] = [e[0], e[1]]
        memdict[key] = [v1, v2,
                        memristor.memristor(w, D, Roff, Ron, mu, Tao, 0.0)]  # we set v=0.0 value in the beginning
        cir.add_resistor(key, 'n' + str(v1), 'n' + str(v2), rval)
        G[e[0]][e[1]]['weight'] = rval
        # edge_labels[e]=rval;

    for n in G.nodes_iter():
        G.node[n]['number'] = n

    # Add random ground and voltage terminal nodes
    [v1, gnd] = random.sample(xrange(0, len(G.nodes())), 2)
    lastnode = len(G.nodes())
    G.add_edge(v1, lastnode)
    G.node[lastnode]['number'] = 'V1'
    lastnode += 1
    G.add_edge(gnd, lastnode)
    G.node[lastnode]['number'] = 'gnd'

    plot_graph(G)

    export_graph(G,'/Users/nfrik/CloudStation/Research/LaBean/ESN/FalstadSPICE/test.txt')

    cir.add_resistor("RG", 'n' + str(gnd), cir.gnd, 0.001)
    cir.add_vsource("V1", 'n' + str(v1), cir.gnd, 1000)
    opa = new_op()

    # netdict contains setup graph and circuit
    networkdict = {}
    networkdict['Graph'] = G
    networkdict['Circuit'] = cir
    networkdict['Memristors'] = memdict
    networkdict['Opa']=opa

    return networkdict

def main():
    graphs = {
        'star_graph': nx.star_graph(1000),
        'ba_graph': nx.barabasi_albert_graph(1000, 2),
        'watts_strogatz': nx.watts_strogatz_graph(1000, 4, p=0.3),
        'random_regular': nx.random_regular_graph(4, 1000),
    }
    folder = 'resources/'
    for name, graph in graphs.iteritems():
        create_graph_file(graph, folder + name)

  def run(self):
    # Run simulation for several type of networks, in this case Erdos-Renyi and Random Network
    self.networks = [
      {
        'network': nx.scale_free_graph(n = self.nodes),
        'name': 'ScaleFree'
      },
      {
        'network': nx.erdos_renyi_graph(n = self.nodes, p = 0.1), # 0.2, 0.5
        'name': 'ErdosRenyi'
      },
      {
        'network': nx.random_regular_graph(n = self.nodes, d = 10),
        'name': 'RandomNetwork'
      }
    ]

    for network in self.networks:
      nxgraph = network['network']
      graph = helper.convert_nxgraph_to_dict(nxgraph)

      # write network in pajek
      filename = 'pajek/'+ network['name'] + '_' + str(self.nodes) + '.net'
      nx.write_pajek(nxgraph, filename)
      
      for mu in self.mu_values:
        print 'Starting...'
        start_time = time.time()

        # B beta (at least 51 values, B=0.02)
        beta = 0.0
        betas = []
        averages = []
        for i in range(0, 51):
          start_time_beta = time.time()
          sis_initial_model = sis.SIS(graph, mu, beta, self.p0)
          simulation = mc.MonteCarlo(sis_initial_model, self.rep, self.t_max, self.t_trans)
          total_average = simulation.run()

          total_time_beta = time.time() - start_time_beta
          betas.append(beta)
          averages.append(total_average)

          print 'B: {}, average: {}, time: {}s'.format(beta, total_average, total_time_beta)
          beta += 0.02

        total_time = time.time() - start_time
        print 'total time: {}'.format(total_time)

        # plot results and save in file
        helper.plot_results(network['name'], self.nodes, mu, betas, averages)
        helper.write_results(network['name'], self.nodes, mu, betas, averages)

      break 

def generate_noisy_eulerian_circuit_data(options):
    """
    This is a noisy version of the eularian circuit problem.
    """
    while True:
        num_nodes = options["num_entities"]
        g = nx.random_regular_graph(2, num_nodes)

        try:
            path = list(nxalg.eulerian_circuit(g))
        except:
            continue
        break

    edges = g.edges()

    # generate another misleading cycle
    num_confusing = options["num_confusing"]
    if num_confusing > 0:
        g_confusing = nx.random_regular_graph(2, num_confusing)

        for e in g_confusing.edges():
            edges.append((e[0] + num_nodes, e[1] + num_nodes))

    random.shuffle(edges)

    # randomize index
    idx = _generate_random_node_index(num_nodes + num_confusing)
    new_edges = _relabel_nodes_in_edges(edges, idx)
    new_path = _relabel_nodes_in_edges(path, idx)

    for edge in new_edges:
        print "%s connected-to %s" % (edge[0], edge[1])
        print "%s connected-to %s" % (edge[1], edge[0])

    first_edge = new_path[0]

    node_list = [str(edge[0]) for edge in new_path]
    print "eval eulerian-circuit %s %s\t%s" % (first_edge[0], first_edge[1],
                                               ",".join(node_list))

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

        Arguments:
        - `args`: command line options
        """
        if getattr(args,'gnd'+suffix) is not None:

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

        elif getattr(args,'gnp'+suffix) is not None:

            n,p = getattr(args,'gnp'+suffix)
            G=networkx.gnp_random_graph(n,p)

        elif getattr(args,'gnm'+suffix) is not None:

            n,m = getattr(args,'gnm'+suffix)
            G=networkx.gnm_random_graph(n,m)

        elif getattr(args,'grid'+suffix) is not None:

            G=networkx.grid_graph(getattr(args,'grid'+suffix))

        elif getattr(args,'torus'+suffix) is not None:
            
            G=networkx.grid_graph(getattr(args,'torus'+suffix),periodic=True)

        elif getattr(args,'complete'+suffix) is not None:

            G=networkx.complete_graph(getattr(args,'complete'+suffix))

        elif getattr(args,'empty'+suffix) is not None:

            G=networkx.empty_graph(getattr(args,'empty'+suffix))

        elif getattr(args,'graphformat'+suffix) is not None:

            try:
                print("INFO: reading simple graph {} from '{}'".format(suffix,getattr(args,"input"+suffix).name),
                      file=sys.stderr)
                G=readGraph(getattr(args,'input'+suffix),
                            "simple",
                            getattr(args,'graphformat'+suffix))
            except ValueError,e:
                print("ERROR ON '{}'. {}".format(
                    getattr(args,'input'+suffix).name,e),
                      file=sys.stderr)
                exit(-1)

def RandomRegular(d, n, seed=None):
    """
    Returns a random d-regular graph on n vertices, or returns False on
    failure.

    Since every edge is incident to two vertices, n\*d must be even.

    INPUT:


    -  ``n`` - number of vertices

    -  ``d`` - degree

    -  ``seed`` - for the random number generator


    EXAMPLE: We show the edge list of a random graph with 8 nodes each
    of degree 3.

    ::

        sage: graphs.RandomRegular(3, 8).edges(labels=False)
        [(0, 1), (0, 4), (0, 7), (1, 5), (1, 7), (2, 3), (2, 5), (2, 6), (3, 4), (3, 6), (4, 5), (6, 7)]

    ::

        sage: G = graphs.RandomRegular(3, 20)
        sage: if G:
        ...    G.show()  # random output, long time

    REFERENCES:

    - [1] Kim, Jeong Han and Vu, Van H. Generating random regular
      graphs. Proc. 35th ACM Symp. on Thy. of Comp. 2003, pp
      213-222. ACM Press, San Diego, CA, USA.
      http://doi.acm.org/10.1145/780542.780576

    - [2] Steger, A. and Wormald, N. Generating random regular
      graphs quickly. Prob. and Comp. 8 (1999), pp 377-396.
    """
    if seed is None:
        seed = current_randstate().long_seed()
    import networkx

    try:
        N = networkx.random_regular_graph(d, n, seed=seed)
        if N is False:
            return False
        return graph.Graph(N, sparse=True)
    except StandardError:
        return False

def build_topology_regular(config):
    """Build a N-regular graph"""

    size = config['RegularTopology']['size']
    degree = config['RegularTopology']['degree']
    seed = config['Simulation']['seed']

    assert size > 0
    assert degree >= 0

    top = nx.random_regular_graph(d=degree, n=size, seed=seed)
    top.name = 'Random Regular Graph: {n} nodes, {d} degree, {s} seed'.format(n=size, d=degree, s=seed)
    return top

    def __init__(self, vertices, degree, seed = int(time.time())):
        """
        Construct a Random Regular Network. The vertices argument contains 
        objects of type Vertex representing the vertices of the network. The 
        degree argument specifies the degree of each vertex. The seed argument 
        is the seed for the random number generator used to build the network. 
        Note that an random regular network has no self loops or 
        parallel edges.
        """

        self.vertices = vertices
        self.degree = degree
        self.seed = seed
        self.g = networkx.random_regular_graph(degree, len(vertices), seed = seed)
        self.__adj_list_map__ = {}

def random_graph_from_parameters(vertices_per_block, block_neighbors,
                                 seed=None):
    """Returns a random graph that satisfies the given parameters.

    `vertices_per_block` and `block_neighbors` are the matrices returned by
    :func:`~fraciso.partitions.partition_parameters`.

    If `seed` is specified, it must be an integer provided as the seed to the
    pseudorandom number generator used to generate the graph.

    """
    # TODO there is an alternate way to implement this function: create a
    # random regular networkx.Graph object for each block of the partition,
    # create a random biregular Graph object between blocks of the partition,
    # then compute the union of the two graphs.
    #
    # Rename some variables for the sake of brevity.
    n, D = np.asarray(vertices_per_block), np.asarray(block_neighbors)
    # p is the number of blocks
    p = len(n)
    mat = to_numpy_matrix
    rr = lambda d, s: random_regular_graph(d, s, seed=seed)
    rb = lambda L, R, d, e:  _random_biregular_graph(L, R, d, e, True, seed)
    # Create a block diagonal matrix that has the regular graphs corresponding
    # to the blocks of the partition along its diagonal.
    regular_graphs = block_diag(*(mat(rr(d, s))
                                for s, d in zip(n, D.diagonal())))
    # Create a block strict upper triangular matrix containing the upper-right
    # blocks of the bipartite adjacency matrices.
    #
    # First, we create a list containing only the blocks necessary.
    blocks = [[rb(n[i], n[j], D[i, j], D[j, i]) for j in range(i + 1, p)]
              for i in range(p - 1)]
    # Next, we pad the lower triangular entries with blocks of zeros. (We also
    # need to add an extra block row of all zeros.) At this point, `padded` is
    # a square list of lists.
    padded = [[np.zeros((n[i], n[j])) for j in range(p - len(row))] + row
              for i, row in enumerate(blocks)]
    padded.append([np.zeros((n[-1], n[i])) for i in range(p)])
    # To get the block strict upper triangular matrix, we concatenate the block
    # matrices in each row.
    biregular_graphs = np.vstack(np.hstack(row) for row in padded)
    # Finally, we add the regular graphs on the diagonaly, the upper biregular
    # graphs, and the transpose of the upper biregular graphs in order to get a
    # graph that has the specified parameters.
    adjacency_matrix = regular_graphs + biregular_graphs + biregular_graphs.T
    return from_numpy_matrix(adjacency_matrix)

	def init_graph(self,g='reg',k=2):
		"""Creates a graph of type g"""
		self.diseasenetwork.add_nodes_from(self.agents)
		#Rewiring of graphs could count as random_mixing 
		#Types of random graphs
		gtype = { 'er':nx.fast_gnp_random_graph(self.population,0.05),
				'nws':nx.newman_watts_strogatz_graph(self.population,k,0.5),
				'ws':nx.watts_strogatz_graph(self.population,k,0.5),
				'cws':nx.connected_watts_strogatz_graph(self.population,k,0.5,10),
				'ba':nx.barabasi_albert_graph(self.population,k),
				'reg':nx.random_regular_graph(k,self.population),
				'grid':nx.grid_2d_graph(self.population/2,self.population/2) }
		#This is causing the trouble need to map each edge to nodes :) 
		if g == 'grid':
			self.diseasenetwork.add_edges_from([ (self.agents[x[0]],self.agents[y[0]]) for x,y in gtype[g].edges() ])
		else:
			self.diseasenetwork.add_edges_from([ (self.agents[x],self.agents[y]) for x,y in gtype[g].edges() ])