path: root/networkx/generators/directed.py

# -*- coding: utf-8 -*-
"""
Generators for some directed graphs, including growing network (GN) graphs and
scale-free graphs.

"""
#    Copyright (C) 2006-2009 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
__author__ ="""Aric Hagberg (hagberg@lanl.gov)\nWillem Ligtenberg (W.P.A.Ligtenberg@tue.nl)"""

__all__ = ['gn_graph', 'gnc_graph', 'gnr_graph','scale_free_graph']

import random

import networkx as nx
from networkx.generators.classic import empty_graph
from networkx.utils import discrete_sequence


def gn_graph(n, kernel=None, create_using=None, seed=None):
    """Return 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 : 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 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.
    """
    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 kernel is None:
        kernel = lambda x: x

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

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

    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 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 not seed is 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=G.successors(target)[0]
        G.add_edge(source,target)

    return G


def gnc_graph(n, create_using=None, seed=None):
    """Return 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 : 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.

    References
    ----------
    .. [1] P. L. Krapivsky and S. Redner,
           Network Growth by Copying,
           Phys. Rev. E, 71, 036118, 2005k.},
    """
    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 not seed is None:
        random.seed(seed)

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

    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 scale_free_graph(n, alpha=0.41, beta=0.54, gamma=0.05, delta_in=0.2,
                     delta_out=0, create_using=None, seed=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 conecgted to an existing node
        chosen randomly according to the out-degree distribution.
    delta_in : float
        Bias for choosing ndoes from in-degree distribution.
    delta_out : float
        Bias for choosing ndoes from out-degree distribution.
    create_using : graph, optional (default MultiDiGraph)
        Use this graph instance to start the process (default=3-cycle).
    seed : integer, optional
        Seed for random number generator

    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(G,distribution,delta):
        cumsum=0.0
        # normalization 
        psum=float(sum(distribution.values()))+float(delta)*len(distribution)
        r=random.random()
        for i in range(0,len(distribution)):
            cumsum+=(distribution[i]+delta)/psum
            if r < cumsum:  
                break
        return i

    if create_using is None:
        # start with 3-cycle
        G = nx.MultiDiGraph()
        G.add_edges_from([(0,1),(1,2),(2,0)])
    else:
        # keep existing graph structure?
        G = create_using
        if not (G.is_directed() and G.is_multigraph()):
            raise nx.NetworkXError(\
                  "MultiDiGraph required in create_using")

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

    if alpha+beta+gamma !=1.0:
        raise ValueError('alpha+beta+gamma must equal 1.')
        
    G.name="directed_scale_free_graph(%s,alpha=%s,beta=%s,gamma=%s,delta_in=%s,delta_out=%s)"%(n,alpha,beta,gamma,delta_in,delta_out)

    # seed random number generated (uses None as default)
    random.seed(seed)

    while len(G)<n:
        r = random.random()
        # random choice in alpha,beta,gamma ranges
        if r<alpha:
            # alpha
            # add new node v
            v = len(G) 
            # choose w according to in-degree and delta_in
            w = _choose_node(G, G.in_degree(),delta_in)
        elif r < alpha+beta:
            # beta
            # choose v according to out-degree and delta_out
            v = _choose_node(G, G.out_degree(),delta_out)
            # choose w according to in-degree and delta_in
            w = _choose_node(G, G.in_degree(),delta_in)
        else:
            # gamma
            # choose v according to out-degree and delta_out
            v = _choose_node(G, G.out_degree(),delta_out)
            # add new node w
            w = len(G) 
        G.add_edge(v,w)
        
    return G