Skip to main content
`Ctrl`+`K`

# Source code for networkx.generators.directed

    """
    Generators for some directed graphs, including growing network (GN) graphs and
    scale-free graphs.

    """

    import numbers
    from collections import Counter

    import networkx as nx
    from networkx.generators.classic import empty_graph
    from networkx.utils import discrete_sequence, py_random_state, weighted_choice

    __all__ = [
        "gn_graph",
        "gnc_graph",
        "gnr_graph",
        "random_k_out_graph",
        "scale_free_graph",
    ]

    @py_random_state(3)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def gn_graph(n, kernel=None, create_using=None, seed=None):
        """Returns the growing network (GN) digraph with `n` nodes.

        The GN 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 the degree of a node.

        The graph is always a (directed) tree.

        Parameters
        ----------
        n : int
            The number of nodes for the generated graph.
        kernel : function
            The attachment kernel.
        create_using : NetworkX graph constructor, optional (default DiGraph)
            Graph type to create. If graph instance, then cleared before populated.
        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.

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

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

        To specify an attachment kernel, use the `kernel` keyword argument::

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

        References
        ----------
        .. [1] P. L. Krapivsky and S. Redner,
               Organization of Growing Random Networks,
               Phys. Rev. E, 63, 066123, 2001.
        """
        G = empty_graph(1, create_using, default=nx.DiGraph)
        if not G.is_directed():
            raise nx.NetworkXError("create_using must indicate a Directed Graph")

        if kernel is None:

            def kernel(x):
                return x

        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, seed=seed)[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

    @py_random_state(3)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def gnr_graph(n, p, create_using=None, seed=None):
        """Returns 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 probability `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 : NetworkX graph constructor, optional (default DiGraph)
            Graph type to create. If graph instance, then cleared before populated.
        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.

        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.
        """
        G = empty_graph(1, create_using, default=nx.DiGraph)
        if not G.is_directed():
            raise nx.NetworkXError("create_using must indicate a Directed Graph")

        if n == 1:
            return G

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

    @py_random_state(2)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def gnc_graph(n, create_using=None, seed=None):
        """Returns the growing network with copying (GNC) digraph with `n` nodes.

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

        Parameters
        ----------
        n : int
            The number of nodes for the generated graph.
        create_using : NetworkX graph constructor, optional (default DiGraph)
            Graph type to create. If graph instance, then cleared before populated.
        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.

        References
        ----------
        .. [1] P. L. Krapivsky and S. Redner,
               Network Growth by Copying,
               Phys. Rev. E, 71, 036118, 2005k.},
        """
        G = empty_graph(1, create_using, default=nx.DiGraph)
        if not G.is_directed():
            raise nx.NetworkXError("create_using must indicate a Directed Graph")

        if n == 1:
            return G

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

    @py_random_state(6)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def scale_free_graph(
        n,
        alpha=0.41,
        beta=0.54,
        gamma=0.05,
        delta_in=0.2,
        delta_out=0,
        seed=None,
        initial_graph=None,
    ):
        """Returns a scale-free directed graph.

        Parameters
        ----------
        n : integer
            Number of nodes in graph
        alpha : float
            Probability for adding a new node connected to an existing node
            chosen randomly according to the in-degree distribution.
        beta : float
            Probability for adding an edge between two existing nodes.
            One existing node is chosen randomly according the in-degree
            distribution and the other chosen randomly according to the out-degree
            distribution.
        gamma : float
            Probability for adding a new node connected to an existing node
            chosen randomly according to the out-degree distribution.
        delta_in : float
            Bias for choosing nodes from in-degree distribution.
        delta_out : float
            Bias for choosing nodes from out-degree distribution.
        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.
        initial_graph : MultiDiGraph instance, optional
            Build the scale-free graph starting from this initial MultiDiGraph,
            if provided.

        Returns
        -------
        MultiDiGraph

        Examples
        --------
        Create a scale-free graph on one hundred nodes::

        >>> G = nx.scale_free_graph(100)

        Notes
        -----
        The sum of `alpha`, `beta`, and `gamma` must be 1.

        References
        ----------
        .. [1] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan,
               Directed scale-free graphs,
               Proceedings of the fourteenth annual ACM-SIAM Symposium on
               Discrete Algorithms, 132--139, 2003.
        """

        def _choose_node(candidates, node_list, delta):
            if delta > 0:
                bias_sum = len(node_list) * delta
                p_delta = bias_sum / (bias_sum + len(candidates))
                if seed.random() < p_delta:
                    return seed.choice(node_list)
            return seed.choice(candidates)

        if initial_graph is not None and hasattr(initial_graph, "_adj"):
            if not isinstance(initial_graph, nx.MultiDiGraph):
                raise nx.NetworkXError("initial_graph must be a MultiDiGraph.")
            G = initial_graph
        else:
            # Start with 3-cycle
            G = nx.MultiDiGraph([(0, 1), (1, 2), (2, 0)])

        if alpha <= 0:
            raise ValueError("alpha must be > 0.")
        if beta <= 0:
            raise ValueError("beta must be > 0.")
        if gamma <= 0:
            raise ValueError("gamma must be > 0.")

        if abs(alpha + beta + gamma - 1.0) >= 1e-9:
            raise ValueError("alpha+beta+gamma must equal 1.")

        if delta_in < 0:
            raise ValueError("delta_in must be >= 0.")

        if delta_out < 0:
            raise ValueError("delta_out must be >= 0.")

        # pre-populate degree states
        vs = sum((count * [idx] for idx, count in G.out_degree()), [])
        ws = sum((count * [idx] for idx, count in G.in_degree()), [])

        # pre-populate node state
        node_list = list(G.nodes())

        # see if there already are number-based nodes
        numeric_nodes = [n for n in node_list if isinstance(n, numbers.Number)]
        if len(numeric_nodes) > 0:
            # set cursor for new nodes appropriately
            cursor = max(int(n.real) for n in numeric_nodes) + 1
        else:
            # or start at zero
            cursor = 0

        while len(G) < n:
            r = seed.random()

            # random choice in alpha,beta,gamma ranges
            if r < alpha:
                # alpha
                # add new node v
                v = cursor
                cursor += 1
                # also add to node state
                node_list.append(v)
                # choose w according to in-degree and delta_in
                w = _choose_node(ws, node_list, delta_in)

            elif r < alpha + beta:
                # beta
                # choose v according to out-degree and delta_out
                v = _choose_node(vs, node_list, delta_out)
                # choose w according to in-degree and delta_in
                w = _choose_node(ws, node_list, delta_in)

            else:
                # gamma
                # choose v according to out-degree and delta_out
                v = _choose_node(vs, node_list, delta_out)
                # add new node w
                w = cursor
                cursor += 1
                # also add to node state
                node_list.append(w)

            # add edge to graph
            G.add_edge(v, w)

            # update degree states
            vs.append(v)
            ws.append(w)

        return G

    @py_random_state(4)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def random_uniform_k_out_graph(n, k, self_loops=True, with_replacement=True, seed=None):
        """Returns a random `k`-out graph with uniform attachment.

        A random `k`-out graph with uniform attachment is a multidigraph
        generated by the following algorithm. For each node *u*, choose
        `k` nodes *v* uniformly at random (with replacement). Add a
        directed edge joining *u* to *v*.

        Parameters
        ----------
        n : int
            The number of nodes in the returned graph.

        k : int
            The out-degree of each node in the returned graph.

        self_loops : bool
            If True, self-loops are allowed when generating the graph.

        with_replacement : bool
            If True, neighbors are chosen with replacement and the
            returned graph will be a directed multigraph. Otherwise,
            neighbors are chosen without replacement and the returned graph
            will be a directed graph.

        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.

        Returns
        -------
        NetworkX graph
            A `k`-out-regular directed graph generated according to the
            above algorithm. It will be a multigraph if and only if
            `with_replacement` is True.

        Raises
        ------
        ValueError
            If `with_replacement` is False and `k` is greater than
            `n`.

        See also
        --------
        random_k_out_graph

        Notes
        -----
        The return digraph or multidigraph may not be strongly connected, or
        even weakly connected.

        If `with_replacement` is True, this function is similar to
        :func:`random_k_out_graph`, if that function had parameter `alpha`
        set to positive infinity.

        """
        if with_replacement:
            create_using = nx.MultiDiGraph()

            def sample(v, nodes):
                if not self_loops:
                    nodes = nodes - {v}
                return (seed.choice(list(nodes)) for i in range(k))

        else:
            create_using = nx.DiGraph()

            def sample(v, nodes):
                if not self_loops:
                    nodes = nodes - {v}
                return seed.sample(list(nodes), k)

        G = nx.empty_graph(n, create_using)
        nodes = set(G)
        for u in G:
            G.add_edges_from((u, v) for v in sample(u, nodes))
        return G

    @py_random_state(4)
    @nx._dispatchable(graphs=None, returns_graph=True)
    def random_k_out_graph(n, k, alpha, self_loops=True, seed=None):
        """Returns a random `k`-out graph with preferential attachment.

        A random `k`-out graph with preferential attachment is a
        multidigraph generated by the following algorithm.

        1. Begin with an empty digraph, and initially set each node to have
           weight `alpha`.
        2. Choose a node `u` with out-degree less than `k` uniformly at
           random.
        3. Choose a node `v` from with probability proportional to its
           weight.
        4. Add a directed edge from `u` to `v`, and increase the weight
           of `v` by one.
        5. If each node has out-degree `k`, halt, otherwise repeat from
           step 2.

        For more information on this model of random graph, see [1].

        Parameters
        ----------
        n : int
            The number of nodes in the returned graph.

        k : int
            The out-degree of each node in the returned graph.

        alpha : float
            A positive :class:`float` representing the initial weight of
            each vertex. A higher number means that in step 3 above, nodes
            will be chosen more like a true uniformly random sample, and a
            lower number means that nodes are more likely to be chosen as
            their in-degree increases. If this parameter is not positive, a
            :exc:`ValueError` is raised.

        self_loops : bool
            If True, self-loops are allowed when generating the graph.

        seed : integer, random_state, or None (default)
            Indicator of random number generation state.
            See :ref:`Randomness<randomness>`.

        Returns
        -------
        :class:`~networkx.classes.MultiDiGraph`
            A `k`-out-regular multidigraph generated according to the above
            algorithm.

        Raises
        ------
        ValueError
            If `alpha` is not positive.

        Notes
        -----
        The returned multidigraph may not be strongly connected, or even
        weakly connected.

        References
        ----------
        [1]: Peterson, Nicholas R., and Boris Pittel.
             "Distance between two random `k`-out digraphs, with and without
             preferential attachment."
             arXiv preprint arXiv:1311.5961 (2013).
             <https://arxiv.org/abs/1311.5961>

        """
        if alpha < 0:
            raise ValueError("alpha must be positive")
        G = nx.empty_graph(n, create_using=nx.MultiDiGraph)
        weights = Counter({v: alpha for v in G})
        for i in range(k * n):
            u = seed.choice([v for v, d in G.out_degree() if d < k])
            # If self-loops are not allowed, make the source node `u` have
            # weight zero.
            if not self_loops:
                adjustment = Counter({u: weights[u]})
            else:
                adjustment = Counter()
            v = weighted_choice(weights - adjustment, seed=seed)
            G.add_edge(u, v)
            weights[v] += 1
        return G