def gnp_random_graph(n, p, seed=None):
    """
    Return a random graph G_{n,p}.

    Choses each of the possible [n(n-1)]/2 edges with probability p.
    This is the same as binomial_graph and erdos_renyi_graph. 

    Sometimes called Erdős-Rényi graph, or binomial graph.

    :Parameters:
      - `n`: the number of nodes
      - `p`: probability for edge creation
      - `seed`: seed for random number generator (default=None)
      
    This is an O(n^2) algorithm.  For sparse graphs (small p) see
    fast_gnp_random_graph. 

    P. Erdős and A. Rényi, On Random Graphs, Publ. Math. 6, 290 (1959).
    E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).

    """
    G=empty_graph(n)
    G.name="gnp_random_graph(%s,%s)"%(n,p)

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

    for u in xrange(n):
        for v in xrange(u+1,n):
            if random.random() < p:
                G.add_edge(u,v)
    return G

def scalefree_graph(n, m):
   
       
	# Add m initial nodes (m0 in barabasi-speak) 
	G=empty_graph(m)
	#G.name="barabasi_albert_graph(%s,%s)"%(n,m)
	# Target nodes for new edges
	#nx.draw(G)
	#plt.show()
	targets=list(range(m))
	sample=[]
	print "Targets:",targets
	# List of existing nodes, with nodes repeated once for each adjacent edge 
	repeated_nodes=[]     
	# Start adding the other n-m nodes. The first node is m.
	source=m 
	while source<n: 
		# Add edges to m nodes from the source.
		#print zip([source]*m,targets)
		G.add_edges_from(zip([source]*m,targets)) 
		# Add one node to the list for each new edge just created.
		repeated_nodes.extend(targets)
		sample.append(targets)
		# And the new node "source" has m edges to add to the list.
		repeated_nodes.extend([source]*m) 
		sample.append([source]*m)
		# Now choose m unique nodes from the existing nodes 
		# Pick uniformly from repeated_nodes (preferential attachement) 
		targets = _random_subset(repeated_nodes,m)
		source += 1
	#print "T",targets
	#print "S " ,sample
	return G

def gnc_graph(n,seed=None):
    """Return the GNC (growing network with copying) digraph with n nodes.

    The graph is built by adding nodes one at a time with a links
    to one previously added node (chosen uniformly at random)
    and to all of that node's successors.

    Reference::

      @article{krapivsky-2005-network,
      title   = {Network Growth by Copying},
      author  = {P. L. Krapivsky and S. Redner},
      journal = {Phys. Rev. E},
      volume  = {71},
      pages   = {036118},
      year    = {2005},
      }

    """
    G=empty_graph(1,create_using=networkx.DiGraph())
    G.name="gnc_graph(%s)"%(n)

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

    if n==1:
        return G

    for source in range(1,n):
        target=random.randrange(0,source)
        for succ in G.successors(target):
            G.add_edge(source,succ)
        G.add_edge(source,target)

    return G

def random_shell_graph(constructor, create_using=None, seed=None):
    """Return a random shell graph for the constructor given.

    Parameters
    ----------
    constructor: a list of three-tuples 
        (n,m,d) for each shell starting at the center shell.
    n : int
        The number of nodes in the shell
    m : int
        The number or edges in the shell
    d : float
        The ratio of inter-shell (next) edges to intra-shell edges.
        d=0 means no intra shell edges, d=1 for the last shell
    create_using : graph, optional (default Graph)
        The graph instance used to build the graph.
    seed : int, optional
        Seed for random number generator (default=None).   
      
    Examples
    --------
    >>> constructor=[(10,20,0.8),(20,40,0.8)]
    >>> G=nx.random_shell_graph(constructor)        

    """
    if create_using is not None and create_using.is_directed():
        raise nx.NetworkXError("Directed Graph not supported")
    G = empty_graph(0, create_using)
    G.name = "random_shell_graph(constructor)"

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

    glist = []
    intra_edges = []
    nnodes = 0
    # create gnm graphs for each shell
    for (n, m, d) in constructor:
        inter_edges = int(m * d)
        intra_edges.append(m - inter_edges)
        g = nx.convert_node_labels_to_integers(gnm_random_graph(n, inter_edges), first_label=nnodes)
        glist.append(g)
        nnodes += n
        G = nx.operators.union(G, g)

    # connect the shells randomly
    for gi in range(len(glist) - 1):
        nlist1 = glist[gi].nodes()
        nlist2 = glist[gi + 1].nodes()
        total_edges = intra_edges[gi]
        edge_count = 0
        while edge_count < total_edges:
            u = random.choice(nlist1)
            v = random.choice(nlist2)
            if u == v or G.has_edge(u, v):
                continue
            else:
                G.add_edge(u, v)
                edge_count = edge_count + 1
    return G

def barabasi_albert_stepper(n, m, seed=None):
    if m < 1 or m >= n:
        raise nx.NetworkXError(("Barabasi-Albert network must " "have m>=1 and m<n, m=%d,n=%d") % (m, n))
    if seed is not None:
        random.seed(seed)

    # Add m initial nodes (m0 in barabasi-speak)
    G = empty_graph(m)
    G.name = "barabasi_albert_graph(%s,%s)" % (n, m)
    # Target nodes for new edges
    targets = list(range(m))
    # List of existing nodes, with nodes repeated once for each adjacent edge
    repeated_nodes = []
    # Start adding the other n-m nodes. The first node is m.
    source = m
    while source < n:
        # Add edges to m nodes from the source.
        G.add_edges_from(zip([source] * m, targets))
        # Add one node to the list for each new edge just created.
        repeated_nodes.extend(targets)
        # And the new node "source" has m edges to add to the list.
        repeated_nodes.extend([source] * m)
        yield targets
        # Now choose m unique nodes from the existing nodes
        # Pick uniformly from repeated_nodes (preferential attachement)
        targets = _random_subset(repeated_nodes, m)
        source += 1

def degree_sequence_tree(deg_sequence):
    """
    Make a tree for the given degree sequence.

    A tree has #nodes-#edges=1 so
    the degree sequence must have
    len(deg_sequence)-sum(deg_sequence)/2=1
    """

    if not len(deg_sequence)-sum(deg_sequence)/2.0 == 1.0:
        raise networkx.NetworkXError,"Degree sequence invalid"

    G=empty_graph(0)
    # single node tree
    if len(deg_sequence)==1:
        return G
    deg=[s for s in deg_sequence if s>1] # all degrees greater than 1
    deg.sort(reverse=True)

    # make path graph as backbone
    n=len(deg)+2
    G=networkx.path_graph(n)
    last=n

    # add the leaves
    for source in range(1,n-1):
        nedges=deg.pop()-2
        for target in range(last,last+nedges):
            G.add_edge(source, target)
        last+=nedges
        
    # in case we added one too many 
    if len(G.degree())>len(deg_sequence): 
        G.remove_node(0)
    return G

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 newman_watts_strogatz_graph(n, k, p, seed=None):
    """Return a Newman-Watts-Strogatz small world graph.

    Parameters
    ----------
    n : int
        The number of nodes
    k : int
        Each node is connected to k nearest neighbors in ring topology
    p : float 
        The probability of adding a new edge for each edge
    seed : int, optional        
       seed for random number generator (default=None)

    Notes
    -----
    First create a ring over n nodes.  Then each node in the ring is
    connected with its k nearest neighbors (k-1 neighbors if k is odd).  
    Then shortcuts are created by adding new edges as follows: 
    for each edge u-v in the underlying "n-ring with k nearest neighbors" 
    with probability p add a new edge u-w with randomly-chosen existing 
    node w.  In contrast with watts_strogatz_graph(), no edges are removed.

    See Also
    --------
    watts_strogatz_graph()

    References
    ----------
    .. [1] M. E. J. Newman and D. J. Watts,
       Renormalization group analysis of the small-world network model,
       Physics Letters A, 263, 341, 1999.
       http://dx.doi.org/10.1016/S0375-9601(99)00757-4
    """
    if seed is not None:
        random.seed(seed)
    if k >= n // 2:
        raise nx.NetworkXError("k>=n/2, choose smaller k or larger n")
    G = empty_graph(n)
    G.name = "newman_watts_strogatz_graph(%s,%s,%s)" % (n, k, p)
    nlist = G.nodes()
    fromv = nlist
    # connect the k/2 neighbors
    for n in range(1, k // 2 + 1):
        tov = fromv[n:] + fromv[0:n]  # the first n are now last
        for i in range(len(fromv)):
            G.add_edge(fromv[i], tov[i])
    # for each edge u-v, with probability p, randomly select existing
    # node w and add new edge u-w
    e = G.edges()
    for (u, v) in e:
        if random.random() < p:
            w = random.choice(nlist)
            # no self-loops and reject if edge u-w exists
            # is that the correct NWS model?
            while w == u or G.has_edge(u, w):
                w = random.choice(nlist)
            G.add_edge(u, w)
    return G

def LCF_graph(n, shift_list, repeats, create_using=None):
    """
    Return the cubic graph specified in LCF notation.

    LCF notation (LCF=Lederberg-Coxeter-Fruchte) is a compressed
    notation used in the generation of various cubic Hamiltonian
    graphs of high symmetry. See, for example, dodecahedral_graph,
    desargues_graph, heawood_graph and pappus_graph below.
    
    n (number of nodes)
      The starting graph is the n-cycle with nodes 0,...,n-1.
      (The null graph is returned if n < 0.)

    shift_list = [s1,s2,..,sk], a list of integer shifts mod n,

    repeats
      integer specifying the number of times that shifts in shift_list
      are successively applied to each v_current in the n-cycle
      to generate an edge between v_current and v_current+shift mod n.

    For v1 cycling through the n-cycle a total of k*repeats
    with shift cycling through shiftlist repeats times connect
    v1 with v1+shift mod n
          
    The utility graph K_{3,3}

    >>> G=nx.LCF_graph(6,[3,-3],3)
    
    The Heawood graph

    >>> G=nx.LCF_graph(14,[5,-5],7)

    See http://mathworld.wolfram.com/LCFNotation.html for a description
    and references.
    
    """
    if create_using is not None and create_using.is_directed():
        raise NetworkXError("Directed Graph not supported")

    if n <= 0:
        return empty_graph(0, create_using)

    # start with the n-cycle
    G = cycle_graph(n, create_using)
    G.name = "LCF_graph"
    nodes = G.nodes()

    n_extra_edges = repeats * len(shift_list)
    # edges are added n_extra_edges times
    # (not all of these need be new)
    if n_extra_edges < 1:
        return G

    for i in range(n_extra_edges):
        shift = shift_list[i % len(shift_list)]  # cycle through shift_list
        v1 = nodes[i % n]  # cycle repeatedly through nodes
        v2 = nodes[(i + shift) % n]
        G.add_edge(v1, v2)
    return G

def barabasi_albert_graph(n, m, seed=None):
    """Returns a random graph according to the Barabási–Albert preferential
    attachment model.

    A graph of ``n`` nodes is grown by attaching new nodes each with ``m``
    edges that are preferentially attached to existing nodes with high degree.

    Parameters
    ----------
    n : int
        Number of nodes
    m : int
        Number of edges to attach from a new node to existing nodes
    seed : int, optional
        Seed for random number generator (default=None).

    Returns
    -------
    G : Graph

    Raises
    ------
    NetworkXError
        If ``m`` does not satisfy ``1 <= m < n``.

    References
    ----------
    .. [1] A. L. Barabási and R. Albert "Emergence of scaling in
       random networks", Science 286, pp 509-512, 1999.
    """

    if m < 1 or  m >=n:
        raise nx.NetworkXError("Barabási–Albert network must have m >= 1"
                               " and m < n, m = %d, n = %d" % (m, n))
    if seed is not None:
        random.seed(seed)

    # Add m initial nodes (m0 in barabasi-speak)
    G=empty_graph(m)
    G.name="barabasi_albert_graph(%s,%s)"%(n,m)
    # Target nodes for new edges
    targets=list(range(m))
    # List of existing nodes, with nodes repeated once for each adjacent edge
    repeated_nodes=[]
    # Start adding the other n-m nodes. The first node is m.
    source=m
    while source<n:
        # Add edges to m nodes from the source.
        G.add_edges_from(zip([source]*m,targets))
        # Add one node to the list for each new edge just created.
        repeated_nodes.extend(targets)
        # And the new node "source" has m edges to add to the list.
        repeated_nodes.extend([source]*m)
        # Now choose m unique nodes from the existing nodes
        # Pick uniformly from repeated_nodes (preferential attachement)
        targets = _random_subset(repeated_nodes,m)
        source += 1
    return G

def gnr_graph(n, p, create_using=None, seed=None):
    """Return the growing network with redirection (GNR) digraph with `n`
    nodes and redirection probability `p`.

    The GNR graph is built by adding nodes one at a time with a link to one
    previously added node.  The previous target node is chosen uniformly at
    random.  With probabiliy `p` the link is instead "redirected" to the
    successor node of the target.

    The graph is always a (directed) tree.

    Parameters
    ----------
    n : int
        The number of nodes for the generated graph.
    p : float
        The redirection probability.
    create_using : graph, optional (default DiGraph)
        Return graph of this type. The instance will be cleared.
    seed : hashable object, optional
        The seed for the random number generator.

    Examples
    --------
    To create the undirected GNR graph, use the :meth:`~DiGraph.to_directed`
    method::

    >>> D = nx.gnr_graph(10, 0.5)  # the GNR graph
    >>> G = D.to_undirected()  # the undirected version

    References
    ----------
    .. [1] P. L. Krapivsky and S. Redner,
           Organization of Growing Random Networks,
           Phys. Rev. E, 63, 066123, 2001.
    """
    if create_using is None:
        create_using = nx.DiGraph()
    elif not create_using.is_directed():
        raise nx.NetworkXError("Directed Graph required in create_using")

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

    G = empty_graph(1, create_using)
    G.name = "gnr_graph(%s,%s)" % (n, p)

    if n == 1:
        return G

    for source in range(1, n):
        target = random.randrange(0, source)
        if random.random() < p and target != 0:
            target = next(G.successors(target))
        G.add_edge(source, target)

    return G

def random_shell_graph(constructor, seed=None):
    """Returns a random shell graph for the constructor given.

    Parameters
    ----------
    constructor : list of three-tuples
        Represents the parameters for a shell, starting at the center
        shell.  Each element of the list must be of the form ``(n, m,
        d)``, where ``n`` is the number of nodes in the shell, ``m`` is
        the number of edges in the shell, and ``d`` is the ratio of
        inter-shell (next) edges to intra-shell edges. If ``d`` is zero,
        there will be no intra-shell edges, and if ``d`` is one there
        will be all possible intra-shell edges.
    seed : int, optional
        Seed for random number generator (default=None).

    Examples
    --------
    >>> constructor = [(10, 20, 0.8), (20, 40, 0.8)]
    >>> G = nx.random_shell_graph(constructor)

    """
    G=empty_graph(0)
    G.name="random_shell_graph(constructor)"

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

    glist=[]
    intra_edges=[]
    nnodes=0
    # create gnm graphs for each shell
    for (n,m,d) in constructor:
        inter_edges=int(m*d)
        intra_edges.append(m-inter_edges)
        g=nx.convert_node_labels_to_integers(
            gnm_random_graph(n,inter_edges),
            first_label=nnodes)
        glist.append(g)
        nnodes+=n
        G=nx.operators.union(G,g)

    # connect the shells randomly
    for gi in range(len(glist)-1):
        nlist1=glist[gi].nodes()
        nlist2=glist[gi+1].nodes()
        total_edges=intra_edges[gi]
        edge_count=0
        while edge_count < total_edges:
            u = random.choice(nlist1)
            v = random.choice(nlist2)
            if u==v or G.has_edge(u,v):
                continue
            else:
                G.add_edge(u,v)
                edge_count=edge_count+1
    return G

def make_small_undirected_graph(graph_description, create_using=None):
    """
    Return a small undirected graph described by graph_description.

    See make_small_graph.
    """
    G = empty_graph(0, create_using)
    if G.is_directed():
        raise NetworkXError("Directed Graph not supported")
    return make_small_graph(graph_description, G)

def fast_gnp_random_graph(n, p, create_using=None, seed=None):
    """Return a random graph G_{n,p}.

    The G_{n,p} graph choses each of the possible [n(n-1)]/2 edges
    with probability p.

    Sometimes called Erdős-Rényi graph, or binomial graph.

    Parameters
    ----------
    n : int
        The number of nodes.
    p : float
        Probability for edge creation.
    create_using :  graph, optional (default Graph)
        Use specified graph as a container.
    seed : int, optional
        Seed for random number generator (default=None). 
      
    Notes
    -----
    This algorithm is O(n+m) where m is the expected number of
    edges m=p*n*(n-1)/2.
    
    It should be faster than gnp_random_graph when p is small, and
    the expected number of edges is small, (sparse graph).

    References
    ----------
    .. [1] Batagelj and Brandes,
       "Efficient generation of large random networks",
       Phys. Rev. E, 71, 036113, 2005.
    """
    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="fast_gnp_random_graph(%s,%s)"%(n,p)

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

    v=1  # Nodes in graph are from 0,n-1 (this is the second node index).
    w=-1
    lp=math.log(1.0-p)  

    while v<n:
        lr=math.log(1.0-random.random())
        w=w+1+int(lr/lp)
        while w>=v and v<n:
            w=w-v
            v=v+1
        if v<n:
            G.add_edge(v,w)
    return G

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

    Parameters
    ----------
    n : int
        The number of nodes.
    p : float
        Probability for edge creation.
    seed : int, optional
        Seed for random number generator (default=None). 
      
    Notes
    -----
    The G_{n,p} graph algorithm chooses each of the [n(n-1)]/2
    (undirected) or n(n-1) (directed) possible edges with probability p.

    This algorithm is O(n+m) where m is the expected number of
    edges m=p*n*(n-1)/2.
    
    It should be faster than gnp_random_graph when p is small and
    the expected number of edges is small (sparse graph).

    See Also
    --------
    gnp_random_graph

    References
    ----------
    .. [1] Batagelj and Brandes, "Efficient generation of large random networks",
       Phys. Rev. E, 71, 036113, 2005.
    """
    G=empty_graph(n)
    G.name="fast_gnp_random_graph(%s,%s)"%(n,p)

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

    if p<=0 or p>=1:
        return nx.gnp_random_graph(n,p)

    v=1  # Nodes in graph are from 0,n-1 (this is the second node index).
    w=-1
    lp=math.log(1.0-p)  

    while v<n:
        lr=math.log(1.0-random.random())
        w=w+1+int(lr/lp)
        while w>=v and v<n:
            w=w-v
            v=v+1
        if v<n:
            G.add_edge(v,w)
    return G

def barabasi_albert_graph(n , m, seed=None):
    """Return random graph using Barabási-Albert preferential attachment model.
    
    A graph of n nodes is grown by attaching new nodes
    each with m edges that are preferentially attached
    to existing nodes with high degree.
    
    :Parameters:
      - `n`: the number of nodes
      - `m`: number of edges to attach from a new node to existing nodes
      - `seed`: seed for random number generator (default=None)

    The initialization is a graph with with m nodes and no edges.

    Reference::

      @article{barabasi-1999-emergence,
      title   = {Emergence of scaling in random networks},
      author  = {A. L. Barabási and R. Albert},
      journal = {Science},
      volume  = {286},
      number  = {5439},
      pages   = {509 -- 512},
      year = {1999},
      }


    """
        
    if m < 1 or  m >=n:
        raise networkx.NetworkXError,\
              "Barabási-Albert network must have m>=1 and m<n, m=%d,n=%d"%(m,n)

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

    G=empty_graph(m)       # add m initial nodes (m0 in barabasi-speak)
    G.name="barabasi_albert_graph(%s,%s)"%(n,m)
    edge_targets=range(m)  # possible targets for new edges
    repeated_nodes=[]      # list of existing nodes,
                           # with nodes repeated once for each adjacent edge 
    source=m               # next node is m
    while source<n:        # Now add the other n-m nodes
        G.add_edges_from(zip([source]*m,edge_targets)) # add links to m nodes
        repeated_nodes.extend(edge_targets) # add one node for each new link
        repeated_nodes.extend([source]*m) # and new node "source" has m links
        # choose m nodes randomly from existing nodes
        # N.B. during each step of adding a new node the probabilities
        # are fixed, is this correct? or should they be updated.
        # Also, random sampling prevents some parallel edges. 
        edge_targets=random.sample(repeated_nodes,m) 
        source += 1
    return G

def make_small_graph(graph_description, create_using=None):
    """
    Return the small graph described by graph_description.

    graph_description is a list of the form [ltype,name,n,xlist]

    Here ltype is one of "adjacencylist" or "edgelist",
    name is the name of the graph and n the number of nodes.
    This constructs a graph of n nodes with integer labels 0,..,n-1.
    
    If ltype="adjacencylist"  then xlist is an adjacency list
    with exactly n entries, in with the j'th entry (which can be empty)
    specifies the nodes connected to vertex j.
    e.g. the "square" graph C_4 can be obtained by

    >>> G=nx.make_small_graph(["adjacencylist","C_4",4,[[2,4],[1,3],[2,4],[1,3]]])

    or, since we do not need to add edges twice,
    
    >>> G=nx.make_small_graph(["adjacencylist","C_4",4,[[2,4],[3],[4],[]]])
    
    If ltype="edgelist" then xlist is an edge list 
    written as [[v1,w2],[v2,w2],...,[vk,wk]],
    where vj and wj integers in the range 1,..,n
    e.g. the "square" graph C_4 can be obtained by
 
    >>> G=nx.make_small_graph(["edgelist","C_4",4,[[1,2],[3,4],[2,3],[4,1]]])

    Use the create_using argument to choose the graph class/type. 
    """
    ltype = graph_description[0]
    name = graph_description[1]
    n = graph_description[2]

    G = empty_graph(n, create_using)
    nodes = G.nodes()

    if ltype == "adjacencylist":
        adjlist = graph_description[3]
        if len(adjlist) != n:
            raise NetworkXError, "invalid graph_description"
        G.add_edges_from([(u - 1, v) for v in nodes for u in adjlist[v]])
    elif ltype == "edgelist":
        edgelist = graph_description[3]
        for e in edgelist:
            v1 = e[0] - 1
            v2 = e[1] - 1
            if v1 < 0 or v1 > n - 1 or v2 < 0 or v2 > n - 1:
                raise NetworkXError, "invalid graph_description"
            else:
                G.add_edge(v1, v2)
    G.name = name
    return G

def gn_graph(n,kernel=lambda x:x ,seed=None):
    """Return the GN (growing network) digraph with n nodes.

    The graph is built by adding nodes one at a time with a link
    to one previously added node.  The target node for the link is chosen
    with probability based on degree.  The default attachment kernel is
    a linear function of degree.

    The graph is always a (directed) tree.

    Example:

    >>> D=nx.gn_graph(10)       # the GN graph
    >>> G=D.to_undirected()  # the undirected version

    To specify an attachment kernel use the kernel keyword

    >>> D=nx.gn_graph(10,kernel=lambda x:x**1.5) # A_k=k^1.5

    Reference::

      @article{krapivsky-2001-organization,
      title   = {Organization of Growing Random Networks},
      author  = {P. L. Krapivsky and S. Redner},
      journal = {Phys. Rev. E},
      volume  = {63},
      pages   = {066123},
      year    = {2001},
      }


    """
    G=empty_graph(1,create_using=networkx.DiGraph())
    G.name="gn_graph(%s)"%(n)

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

    if n==1:
        return G

    G.add_edge(1,0) # get started
    ds=[1,1] # degree sequence

    for source in range(2,n):
        # compute distribution from kernel and degree
        dist=[kernel(d) for d in ds] 
        # choose target from discrete distribution 
        target=discrete_sequence(1,distribution=dist)[0]
        G.add_edge(source,target)
        ds.append(1)  # the source has only one link (degree one)
        ds[target]+=1 # add one to the target link degree
    return G

def grid_graph(dim, periodic=False):
    """Returns the *n*-dimensional grid graph.

    The dimension *n* is the length of the list `dim` and the size in
    each dimension is the value of the corresponding list element.

    Parameters
    ----------
    dim : list or tuple of numbers or iterables of nodes
        'dim' is a tuple or list with, for each dimension, either a number
        that is the size of that dimension or an iterable of nodes for
        that dimension. The dimension of the grid_graph is the length
        of `dim`.

    periodic : bool
        If `periodic is True` the nodes on the grid boundaries are joined
        to the corresponding nodes on the opposite grid boundaries.

    Returns
    -------
    NetworkX graph
        The (possibly periodic) grid graph of the specified dimensions.

    Examples
    --------
    To produce a 2 by 3 by 4 grid graph, a graph on 24 nodes::

        >>> G = grid_graph(dim=[2, 3, 4])
        >>> len(G)
        24
        >>> G = grid_graph(dim=[range(7, 9), range(3, 6)])
        >>> len(G)
        6
    """
    dlabel = "%s" % dim
    if not dim:
        G = empty_graph(0)
        G.name = "grid_graph(%s)" % dlabel
        return G

    func = cycle_graph if periodic else path_graph
    G = func(dim[0])
    for current_dim in dim[1:]:
        # order matters: copy before it is cleared during the creation of Gnew
        Gold = G.copy()
        Gnew = func(current_dim)
        # explicit: create_using = None
        # This is so that we get a new graph of Gnew's class.
        G = cartesian_product(Gnew, Gold)
    # graph G is done but has labels of the form (1, (2, (3, 1))) so relabel
    H = relabel_nodes(G, flatten)
    H.name = "grid_graph(%s)" % dlabel
    return H

def random_shell_graph(constructor, seed=None):
    """
    Return a random shell graph for the constructor given.

      - constructor: a list of three-tuples [(n1,m1,d1),(n2,m2,d2),..]
        one for each shell, starting at the center shell.
      - n : the number of nodes in the shell
      - m : the number or edges in the shell
      - d : the ratio of inter (next) shell edges to intra shell edges.
              d=0 means no intra shell edges.
              d=1 for the last shell
      - `seed`: seed for random number generator (default=None)
      
    >>> constructor=[(10,20,0.8),(20,40,0.8)]
    >>> G=nx.random_shell_graph(constructor)        

    """
    G=empty_graph(0)
    G.name="random_shell_graph(constructor)"

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

    glist=[]        
    intra_edges=[]
    nnodes=0
    # create gnm graphs for each shell
    for (n,m,d) in constructor:
        inter_edges=int(m*d)
        intra_edges.append(m-inter_edges)
        g=networkx.operators.convert_node_labels_to_integers(
                     gnm_random_graph(n,inter_edges),
                     first_label=nnodes)
        glist.append(g)
        nnodes+=n                     
        G=networkx.operators.union(G,g)

    # connect the shells randomly         
    for gi in range(len(glist)-1):
        nlist1=glist[gi].nodes()
        nlist2=glist[gi+1].nodes()
        total_edges=intra_edges[gi]
        edge_count=0
        while edge_count < total_edges:
            u = random.choice(nlist1)
            v = random.choice(nlist2)
            if u==v or G.has_edge(u,v):
                continue
            else:
                G.add_edge(u,v)
                edge_count=edge_count+1
    return G