Source Code for Module networkx.generators.directed

  1  """ 
  2  Generators for some directed graphs. 
  3   
  4  gn_graph: growing network  
  5  gnc_graph: growing network with copying 
  6  gnr_graph: growing network with redirection 
  7   
  8  """ 
  9  #    Copyright (C) 2006 by  
 10  #    Aric Hagberg <hagberg@lanl.gov> 
 11  #    Dan Schult <dschult@colgate.edu> 
 12  #    Pieter Swart <swart@lanl.gov> 
 13  #    Distributed under the terms of the GNU Lesser General Public License 
 14  #    http://www.gnu.org/copyleft/lesser.html 
 15  __author__ ="""Aric Hagberg (hagberg@lanl.gov)""" 
 16   
 17  import math 
 18  import random 
 19   
 20  from networkx.digraph import DiGraph 
 21  from networkx.generators.classic import empty_graph 
 22  from networkx.utils import discrete_sequence 
 23   
 24   
 25 -def gn_graph(n,kernel=lambda x:x ,seed=None): 
 26      """Return the GN (growing network) digraph with n nodes. 
 27   
 28      The graph is built by adding nodes one at a time with a link 
 29      to one previously added node.  The target node for the link is chosen 
 30      with probability based on degree.  The default attachment kernel is 
 31      a linear function of degree. 
 32   
 33      The graph is always a (directed) tree. 
 34   
 35      Example: 
 36   
 37      >>> D=gn_graph(10)       # the GN graph 
 38      >>> G=D.to_undirected()  # the undirected version 
 39   
 40      To specify an attachment kernel use the kernel keyword 
 41   
 42      >>> D=gn_graph(10,kernel=lambda x:x**1.5) # A_k=k^1.5 
 43   
 44      Reference:: 
 45   
 46        @article{krapivsky-2001-organization, 
 47        title   = {Organization of Growing Random Networks}, 
 48        author  = {P. L. Krapivsky and S. Redner}, 
 49        journal = {Phys. Rev. E}, 
 50        volume  = {63}, 
 51        pages   = {066123}, 
 52        year    = {2001}, 
 53        } 
 54   
 55   
 56      """ 
 57      G=empty_graph(1,create_using=DiGraph()) 
 58      G.name="gn_graph(%s)"%(n) 
 59   
 60      if seed is not None: 
 61          random.seed(seed) 
 62   
 63      if n==1: 
 64          return G 
 65   
 66      G.add_edge(1,0) # get started 
 67      ds=[1,1] # degree sequence 
 68   
 69      for source in range(2,n): 
 70          # compute distribution from kernel and degree 
 71          dist=[kernel(d) for d in ds]  
 72          # choose target from discrete distribution  
 73          target=discrete_sequence(1,distribution=dist)[0] 
 74          G.add_edge(source,target) 
 75          ds.append(1)  # the source has only one link (degree one) 
 76          ds[target]+=1 # add one to the target link degree 
 77      return G 
 78   
 79   
 80 -def gnr_graph(n,p,seed=None): 
 81      """Return the GNR (growing network with redirection) digraph with n nodes 
 82      and redirection probability p. 
 83   
 84      The graph is built by adding nodes one at a time with a link 
 85      to one previously added node.  The previous target node is chosen 
 86      uniformly at random.  With probabiliy p the link is instead "redirected" 
 87      to the successor node of the target.  The graph is always a (directed) 
 88      tree. 
 89   
 90      Example: 
 91   
 92      >>> D=gnr_graph(10,0.5)  # the GNR graph 
 93      >>> G=D.to_undirected()  # the undirected version 
 94   
 95      Reference:: 
 96   
 97        @article{krapivsky-2001-organization, 
 98        title   = {Organization of Growing Random Networks}, 
 99        author  = {P. L. Krapivsky and S. Redner}, 
100        journal = {Phys. Rev. E}, 
101        volume  = {63}, 
102        pages   = {066123}, 
103        year    = {2001}, 
104        } 
105   
106      """ 
107      G=empty_graph(1,create_using=DiGraph()) 
108      G.name="gnr_graph(%s,%s)"%(n,p) 
109   
110      if not seed is None: 
111          random.seed(seed) 
112   
113      if n==1: 
114          return G 
115   
116      for source in range(1,n): 
117          target=random.randrange(0,source) 
118          if random.random() < p and target !=0: 
119              target=G.successors(target)[0] 
120          G.add_edge(source,target) 
121   
122      return G 
123   
124   
125   
126 -def gnc_graph(n,seed=None): 
127      """Return the GNC (growing network with copying) digraph with n nodes. 
128   
129      The graph is built by adding nodes one at a time with a links 
130      to one previously added node (chosen uniformly at random) 
131      and to all of that node's successors. 
132   
133      Reference:: 
134   
135        @article{krapivsky-2005-network, 
136        title   = {Network Growth by Copying}, 
137        author  = {P. L. Krapivsky and S. Redner}, 
138        journal = {Phys. Rev. E}, 
139        volume  = {71}, 
140        pages   = {036118}, 
141        year    = {2005}, 
142        } 
143   
144      """ 
145      G=empty_graph(1,create_using=DiGraph()) 
146      G.name="gnc_graph(%s)"%(n) 
147   
148      if not seed is None: 
149          random.seed(seed) 
150   
151      if n==1: 
152          return G 
153   
154      for source in range(1,n): 
155          target=random.randrange(0,source) 
156          for succ in G.successors(target): 
157              G.add_edge(source,succ) 
158          G.add_edge(source,target) 
159   
160      return G 
161   
162   
163 -def _test_suite(): 
164      import doctest 
165      suite = doctest.DocFileSuite('tests/generators/directed.txt', 
166                                   package='networkx') 
167      return suite 
168   
169   
170  if __name__ == "__main__": 
171      import os 
172      import sys 
173      import unittest 
174      if sys.version_info[:2] < (2, 4): 
175          print "Python version 2.4 or later required (%d.%d detected)."\ 
176                %  sys.version_info[:2] 
177          sys.exit(-1) 
178      # directory of networkx package (relative to this) 
179      nxbase=sys.path[0]+os.sep+os.pardir 
180      sys.path.insert(0,nxbase) # prepend to search path 
181      unittest.TextTestRunner().run(_test_suite()) 
182