def dense_gnm_random_graph(n, m, seed=None):
    """Returns a `G_{n,m}` random graph.

    In the `G_{n,m}` model, a graph is chosen uniformly at random from the set
    of all graphs with `n` nodes and `m` edges.

    This algorithm should be faster than :func:`gnm_random_graph` for dense
    graphs.

    Parameters
    ----------
    n : int
        The number of nodes.
    m : int
        The number of edges.
    seed : int, optional
        Seed for random number generator (default=None).

    See Also
    --------
    gnm_random_graph()

    Notes
    -----
    Algorithm by Keith M. Briggs Mar 31, 2006.
    Inspired by Knuth's Algorithm S (Selection sampling technique),
    in section 3.4.2 of [1]_.

    References
    ----------
    .. [1] Donald E. Knuth, The Art of Computer Programming,
        Volume 2/Seminumerical algorithms, Third Edition, Addison-Wesley, 1997.
    """
    mmax=n*(n-1)/2
    if m>=mmax:
        G=complete_graph(n)
    else:
        G=empty_graph(n)
    G.name="dense_gnm_random_graph(%s,%s)"%(n,m)

    if n==1 or m>=mmax:
        return G

    if seed is not None:
        random.seed(seed)

    u=0
    v=1
    t=0
    k=0
    while True:
        if random.randrange(mmax-t)<m-k:
            G.add_edge(u,v)
            k+=1
            if k==m: return G
        t+=1
        v+=1
        if v==n: # go to next row of adjacency matrix
            u+=1
            v=u+1

def gnp_random_graph(n, p, seed=None, directed=False):
    """Returns a `G_{n,p}` random graph, also known as an Erdős-Rényi graph or
    a binomial graph.

    The `G_{n,p}` model chooses each of the possible edges with probability
    ``p``.

    The functions :func:`binomial_graph` and :func:`erdos_renyi_graph` are
    aliases of this function.

    Parameters
    ----------
    n : int
        The number of nodes.
    p : float
        Probability for edge creation.
    seed : int, optional
        Seed for random number generator (default=None).
    directed : bool, optional (default=False)
        If ``True``, this function returns a directed graph.

    See Also
    --------
    fast_gnp_random_graph

    Notes
    -----
    This algorithm runs in `O(n^2)` time.  For sparse graphs (that is, for
    small values of `p`), :func:`fast_gnp_random_graph` is a faster algorithm.

    References
    ----------
    .. [1] P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).
    .. [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
    """
    if directed:
        G=nx.DiGraph()
    else:
        G=nx.Graph()
    G.add_nodes_from(range(n))
    G.name="gnp_random_graph(%s,%s)"%(n,p)
    if p<=0:
        return G
    if p>=1:
        return complete_graph(n,create_using=G)

    if not seed is None:
        random.seed(seed)

    if G.is_directed():
        edges=itertools.permutations(range(n),2)
    else:
        edges=itertools.combinations(range(n),2)

    for e in edges:
        if random.random() < p:
            G.add_edge(*e)
    return G

def anti_barabasi(n,m):
    G = complete_graph(m)
    #target nodes for new nodes
    targets = list(range(m))
    new = m#initialize = m
    while new < n:
        G.add_edges_from(zip([new]*m,targets))#add m edge together
        targets = prob_subset(G,m)
        new += 1
    return G

def gnp_random_graph(n, p, seed=None, directed=False):
    """Return a random graph G_{n,p} (Erdős-Rényi graph, binomial graph).

    Chooses each of the possible edges with probability p.

    This is also called binomial_graph and erdos_renyi_graph. 

    Parameters
    ----------
    n : int
        The number of nodes.
    p : float
        Probability for edge creation.
    seed : int, optional
        Seed for random number generator (default=None). 
    directed : bool, optional (default=False)
        If True return a directed graph 
    
    See Also  
    --------
    fast_gnp_random_graph

    Notes
    -----
    This is an O(n^2) algorithm.  For sparse graphs (small p) see
    fast_gnp_random_graph for a faster algorithm.

    References
    ----------
    .. [1] P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).
    .. [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).
    """
    if directed:
        G = nx.DiGraph()
    else:
        G = nx.Graph()
    G.add_nodes_from(range(n))
    G.name = "gnp_random_graph(%s,%s)" % (n, p)
    if p <= 0:
        return G
    if p >= 1:
        return complete_graph(n, create_using=G)

    if not seed is None:
        random.seed(seed)

    if G.is_directed():
        edges = itertools.permutations(range(n), 2)
    else:
        edges = itertools.combinations(range(n), 2)

    for e in edges:
        if random.random() < p:
            G.add_edge(*e)
    return G

def gnm_random_graph(n, m, seed=None, directed=False):
    """Returns a `G_{n,m}` random graph.

    In the `G_{n,m}` model, a graph is chosen uniformly at random from the set
    of all graphs with `n` nodes and `m` edges.

    This algorithm should be faster than :func:`dense_gnm_random_graph` for
    sparse graphs.

    Parameters
    ----------
    n : int
        The number of nodes.
    m : int
        The number of edges.
    seed : int, optional
        Seed for random number generator (default=None).
    directed : bool, optional (default=False)
        If True return a directed graph

    See also
    --------
    dense_gnm_random_graph

    """
    if directed:
        G=nx.DiGraph()
    else:
        G=nx.Graph()
    G.add_nodes_from(range(n))
    G.name="gnm_random_graph(%s,%s)"%(n,m)

    if seed is not None:
        random.seed(seed)

    if n==1:
        return G
    max_edges=n*(n-1)
    if not directed:
        max_edges/=2.0
    if m>=max_edges:
        return complete_graph(n,create_using=G)

    nlist=G.nodes()
    edge_count=0
    while edge_count < m:
        # generate random edge,u,v
        u = random.choice(nlist)
        v = random.choice(nlist)
        if u==v or G.has_edge(u,v):
            continue
        else:
            G.add_edge(u,v)
            edge_count=edge_count+1
    return G

def dense_gnm_random_graph(n, m, seed=None):
    """
    Return the random graph G_{n,m}.

    Gives a graph picked randomly out of the set of all graphs
    with n nodes and m edges.
    This algorithm should be faster than gnm_random_graph for dense graphs.

    :Parameters:
      - `n`: the number of nodes
      - `m`: the number of edges
      - `seed`: seed for random number generator (default=None)


    Algorithm by Keith M. Briggs Mar 31, 2006.
    Inspired by Knuth's Algorithm S (Selection sampling technique),
    in section 3.4.2 of

    The Art of Computer Programming by Donald E. Knuth
    Volume 2 / Seminumerical algorithms
    Third Edition, Addison-Wesley, 1997.
 
    """
    mmax=n*(n-1)/2
    if m>=mmax:
        G=complete_graph(n)
    else:
        G=empty_graph(n)

        G.name="dense_gnm_random_graph(%s,%s)"%(n,m)
  
    if n==1 or m>=mmax:
        return G
  
    if seed is not None:
        random.seed(seed)

    u=0
    v=1
    t=0
    k=0
    while True:
        if random.randrange(mmax-t)<m-k:
            G.add_edge(u,v)
            k+=1
            if k==m: return G
        t+=1
        v+=1
        if v==n: # go to next row of adjacency matrix
            u+=1
            v=u+1

def gnm_random_graph(n, m, create_using=None, seed=None):
    """Return the random graph G_{n,m}.

    Gives a graph picked randomly out of the set of all graphs
    with n nodes and m edges.

    Parameters
    ----------
    n : int
        The number of nodes.
    m : int
        The number of edges.
    create_using :  graph, optional (default Graph)
        Use specified graph as a container.
    seed : int, optional
        Seed for random number generator (default=None). 
      
    """
    if create_using is not None and create_using.is_directed():
        raise nx.NetworkXError("Directed Graph not supported")
    G=empty_graph(n,create_using)
    G.name="gnm_random_graph(%s,%s)"%(n,m)

    if seed is not None:
        random.seed(seed)

    if n==1:
        return G

    if m>=n*(n-1)/2:
        return complete_graph(n,create_using)

    nlist=G.nodes()
    edge_count=0
    while edge_count < m:
        # generate random edge,u,v
        u = random.choice(nlist)
        v = random.choice(nlist)
        if u==v or G.has_edge(u,v):
            continue
        # is this faster?
        # (u,v)=random.sample(nlist,2)
        #  if G.has_edge(u,v):
        #      continue
        else:
            G.add_edge(u,v)
            edge_count=edge_count+1
    return G

	def __init__(self, m_0, m , max_num ):
		self._round = 0
		self._network  = complete_graph( m_0 )
		self._max_nid = m_0
		self._nodes_start = dict()
		self._nodes_end = dict()
		self._m = m 
		self._max_num = max_num

		self._choice_list = list() 
		for v in self._network.nodes() :
			self._nodes_start[ v] =  self._round
			for i in range( self._network.degree( v )):
				self._choice_list.append( v ) 

		self._round += 1

def gnm_random_graph(n, m, seed=None, directed=False):
    """Return the random graph G_{n,m}.

    Produces a graph picked randomly out of the set of all graphs
    with n nodes and m edges.

    Parameters
    ----------
    n : int
        The number of nodes.
    m : int
        The number of edges.
    seed : int, optional
        Seed for random number generator (default=None). 
    directed : bool, optional (default=False)
        If True return a directed graph 
    """
    if directed:
        G = nx.DiGraph()
    else:
        G = nx.Graph()
    G.add_nodes_from(range(n))
    G.name = "gnm_random_graph(%s,%s)" % (n, m)

    if seed is not None:
        random.seed(seed)

    if n == 1:
        return G
    max_edges = n * (n - 1)
    if not directed:
        max_edges /= 2.0
    if m >= max_edges:
        return complete_graph(n, create_using=G)

    nlist = G.nodes()
    edge_count = 0
    while edge_count < m:
        # generate random edge,u,v
        u = random.choice(nlist)
        v = random.choice(nlist)
        if u == v or G.has_edge(u, v):
            continue
        else:
            G.add_edge(u, v)
            edge_count = edge_count + 1
    return G

def vehicle_accusation_graph(n, p, seed=None, directed=True):
    """Return a random vehicle accusation graph G_{n,p}.
    Chooses each of the possible edges with accusation probability p.
    Parameters
    ----------
    n : int
        The number of vehicles.
    p : float
        Probability for accusation.
    seed : int, optional
        Seed for random number generator (default=None).
    directed : bool, optional (default=True)
        If True return a directed graph
    """

    if directed:
        G=nx.DiGraph()
    else:
        G=nx.Graph()
    G.add_nodes_from(range(n))
    G.name='Vehicle_accusation_graph({}, {})'.format(n, p)
    if p<=0:
        return G
    if p>=1:
        return complete_graph(n,create_using=G)

    if not seed is None:
        random.seed(seed)

    if G.is_directed():
        edges=itertools.permutations(range(n),2)
    else:
        edges=itertools.combinations(range(n),2)

    for e in edges:
        if random.random() < p:
            G.add_edge(*e)

    """
    Remove all isolates in the graph & relabel the nodes of the graph
    """
    if nx.isolates(G):
        G.remove_nodes_from(nx.isolates(G))
        mapping = dict(zip(G.nodes(), range(G.number_of_nodes())))
        G = nx.relabel_nodes(G, mapping)

    return G

def gnm_random_graph(n, m, seed=None):
    """
    Return the random graph G_{n,m}.

    Gives a graph picked randomly out of the set of all graphs
    with n nodes and m edges.

    :Parameters:
        - `n`: the number of nodes
        - `m`: the number of edges
        - `seed`: seed for random number generator (default=None)
    """
    G=empty_graph(n)
    G.name="gnm_random_graph(%s,%s)"%(n,m)

    if seed is not None:
        random.seed(seed)

    if n==1:
        return G

    if m>=n*(n-1)/2:
        return complete_graph(n)

    nlist=G.nodes()
    edge_count=0
    while edge_count < m:
        # generate random edge,u,v
        u = random.choice(nlist)
        v = random.choice(nlist)
        if u==v or G.has_edge(u,v):
            continue
        # is this faster?
        # (u,v)=random.sample(nlist,2)
        #  if G.has_edge(u,v):
        #      continue
        else:
            G.add_edge(u,v)
            edge_count=edge_count+1
    return G

def dense_gnm_random_graph(n, m, create_using=None, seed=None):
    """Return the random graph G_{n,m}.

    Gives a graph picked randomly out of the set of all graphs
    with n nodes and m edges.
    This algorithm should be faster than gnm_random_graph for dense graphs.

    Parameters
    ----------
    n : int
        The number of nodes.
    m : int
        The number of edges.
    create_using :  graph, optional (default Graph)
        Use specified graph as a container.
    seed : int, optional
        Seed for random number generator (default=None). 
      
    See Also
    --------
    gnm_random_graph()

    Notes
    -----
    Algorithm by Keith M. Briggs Mar 31, 2006.
    Inspired by Knuth's Algorithm S (Selection sampling technique),
    in section 3.4.2 of

    References
    ----------
    .. [1] Donald E. Knuth,
        The Art of Computer Programming,
        Volume 2 / Seminumerical algorithms
        Third Edition, Addison-Wesley, 1997.
 
    """
    mmax=n*(n-1)/2
    if m>=mmax:
        G=complete_graph(n,create_using)
    else:
        if create_using is not None and create_using.is_directed():
            raise nx.NetworkXError("Directed Graph not supported")
        G=empty_graph(n,create_using)

        G.name="dense_gnm_random_graph(%s,%s)"%(n,m)
  
    if n==1 or m>=mmax:
        return G
  
    if seed is not None:
        random.seed(seed)

    u=0
    v=1
    t=0
    k=0
    while True:
        if random.randrange(mmax-t)<m-k:
            G.add_edge(u,v)
            k+=1
            if k==m: return G
        t+=1
        v+=1
        if v==n: # go to next row of adjacency matrix
            u+=1
            v=u+1

def tetrahedral_graph(create_using=None):
    """ Return the 3-regular Platonic Tetrahedral graph."""
    G = complete_graph(4, create_using)
    G.name = "Platonic Tetrahedral graph"
    return G

def tetrahedral_graph():
    """ Return the 3-regular Platonic Tetrahedral graph."""
    G=complete_graph(4)
    G.name="Platonic Tetrahedral graph"
    return G