Source Code for Module networkx.generators.geometric

 1  """ 
 2  Generators for geometric graphs. 
 3   
 4  """ 
 5  #    Copyright (C) 2004,2005 by  
 6  #    Aric Hagberg <hagberg@lanl.gov> 
 7  #    Dan Schult <dschult@colgate.edu> 
 8  #    Pieter Swart <swart@lanl.gov> 
 9  #    Distributed under the terms of the GNU Lesser General Public License 
10  #    http://www.gnu.org/copyleft/lesser.html 
11  __author__ ="""Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)""" 
12  __date__ = "$Date: 2005-06-15 12:44:45 -0600 (Wed, 15 Jun 2005) $" 
13  __credits__ = """""" 
14  __revision__ = "$Revision: 1038 $" 
15   
16  import networkx 
17  import random,sys 
18   
19   
20  #--------------------------------------------------------------------------- 
21  #  Random Geometric Graphs 
22  #--------------------------------------------------------------------------- 
23           
24 -def random_geometric_graph(n, radius, create_using=None, repel=0.0, verbose=False, dim=2): 
25      """Random geometric graph in the unit cube 
26   
27      Returned Graph has added attribute G.pos which is a  
28      dict keyed by node to the position tuple for the node. 
29      """ 
30      if create_using is None:     
31          G=networkx.Graph() 
32      else: 
33          G=create_using 
34          G.clear() 
35      G.name="Random Geometric Graph" 
36      G.add_nodes_from([v for v in range(n)])  # add n nodes 
37      # position them randomly in the unit cube in n dimensions 
38      # but not any two within "repel" distance of each other 
39      # pick n random positions 
40      positions=[] 
41      while(len(positions)< n): 
42          pnew=[] 
43          [pnew.append(random.random()) for i in xrange(0,dim)] 
44          reject=False 
45          # avoid existing nodes 
46          if repel > 0.0 : 
47              for pold in positions: 
48                  m2=map(lambda x,y: (x-y)**2, pold,pnew) 
49                  r2=reduce(lambda x, y: x+y, m2, 0.) 
50                  if r2 < repel**2 : 
51                      reject=True 
52                      print >>sys.stderr,"rejecting", len(positions),pnew 
53                      break 
54              if(reject): 
55                  reject=False 
56                  continue 
57          if(verbose): 
58              print >>sys.stderr,"accepting", len(positions),pnew 
59          positions.append(pnew)     
60   
61      # add positions to nodes         
62      G.pos={} 
63      for v in G.nodes(): 
64          G.pos[v]=positions.pop() 
65   
66      # connect nodes within "radius" of each other 
67      # n^2 algorithm, oh well, should work in n dimensions anyway... 
68      for u in G.nodes(): 
69          p1=G.pos[u] 
70          for v in G.nodes(): 
71              if u==v:  # no self loops 
72                  continue 
73              p2=G.pos[v] 
74              m2=map(lambda x,y: (x-y)**2, p1,p2) 
75              r2=reduce(lambda x, y: x+y, m2, 0.) 
76              if r2 < radius**2 : 
77                  G.add_edge(u,v) 
78      return G 
79   
80   
81 -def _test_suite(): 
82      import doctest 
83      suite = doctest.DocFileSuite('tests/generators/geometric.txt', 
84                                   package='networkx') 
85      return suite 
86   
87  if __name__ == "__main__": 
88      import os 
89      import sys 
90      import unittest 
91      if sys.version_info[:2] < (2, 4): 
92          print "Python version 2.4 or later required (%d.%d detected)." %  sys.version_info[:2] 
93          sys.exit(-1) 
94      # directory of networkx package (relative to this) 
95      nxbase=sys.path[0]+os.sep+os.pardir 
96      sys.path.insert(0,nxbase) # prepend to search path 
97      unittest.TextTestRunner().run(_test_suite()) 
98