diff options
Diffstat (limited to 'lib/python2.7/site-packages/setoolsgui/networkx/generators/directed.py')
| -rw-r--r-- | lib/python2.7/site-packages/setoolsgui/networkx/generators/directed.py | 304 |
1 files changed, 304 insertions, 0 deletions
diff --git a/lib/python2.7/site-packages/setoolsgui/networkx/generators/directed.py b/lib/python2.7/site-packages/setoolsgui/networkx/generators/directed.py new file mode 100644 index 0000000..d1dc712 --- /dev/null +++ b/lib/python2.7/site-packages/setoolsgui/networkx/generators/directed.py @@ -0,0 +1,304 @@ +""" +Generators for some directed graphs. + +gn_graph: growing network +gnc_graph: growing network with copying +gnr_graph: growing network with redirection +scale_free_graph: scale free directed graph + +""" +# 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 GN digraph with n nodes. + + The GN (growing network) 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. + + 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 + -------- + >>> 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 + + 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 GNR digraph with n nodes and redirection probability p. + + The GNR (growing network with redirection) 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 + -------- + >>> 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 GNC digraph with n nodes. + + The GNC (growing network with copying) 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. + + 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): + """Return 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 + -------- + >>> G=nx.scale_free_graph(100) + + Notes + ----- + The sum of alpha, beta, and gamma must be 1. + + References + ---------- + .. [1] B. Bollob{\'a}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 + |