Source Code for Module networkx.readwrite.sparsegraph6

  1  """ 
  2  Read graphs in graph6 and sparse6 format. 
  3  See http://cs.anu.edu.au/~bdm/data/formats.txt 
  4   
  5  """ 
  6  # Original author: D. Eppstein, UC Irvine, August 12, 2003. 
  7  # The original code at http://www.ics.uci.edu/~eppstein/PADS/ is public domain. 
  8  __author__ = """Aric Hagberg (hagberg@lanl.gov)""" 
  9  __date__ = """""" 
 10  __credits__ = """""" 
 11  __revision__ = "" 
 12  #    Copyright (C) 2004-2007 by  
 13  #    Aric Hagberg <hagberg@lanl.gov> 
 14  #    Dan Schult <dschult@colgate.edu> 
 15  #    Pieter Swart <swart@lanl.gov> 
 16  #    Distributed under the terms of the GNU Lesser General Public License 
 17  #    http://www.gnu.org/copyleft/lesser.html 
 18   
 19  import networkx 
 20  from networkx.exception import NetworkXException, NetworkXError 
 21  from networkx.utils import _get_fh 
 22           
 23 -def read_graph6_list(path): 
 24      """Read simple undirected graphs in graph6 format from path. 
 25      Returns a list of Graphs, one for each line in file.""" 
 26      fh=_get_fh(path,mode='r')         
 27      glist=[] 
 28      for line in fh: 
 29          line = line.strip() 
 30          if not len(line): continue 
 31          glist.append(parse_graph6(line)) 
 32      return glist 
 33   
 34 -def read_graph6(path): 
 35      """Read simple undirected graphs in graph6 format from path. 
 36      Returns a single Graph.""" 
 37      return read_graph6_list(path)[0] 
 38           
 39           
 40 -def read_sparse6_list(path): 
 41      """Read simple undirected graphs in sparse6 format from path. 
 42      Returns a list of Graphs, one for each line in file.""" 
 43      fh=_get_fh(path,mode='r')         
 44      glist=[] 
 45      for line in fh: 
 46          line = line.strip() 
 47          if not len(line): continue 
 48          glist.append(parse_sparse6(line)) 
 49      return glist 
 50   
 51 -def read_sparse6(path): 
 52      """Read simple undirected graphs in sparse6 format from path. 
 53      Returns a single Graph.""" 
 54      return read_sparse6_list(path)[0] 
 55   
 56   
 57 -def graph6data(str): 
 58      """Convert graph6 character sequence to 6-bit integers.""" 
 59      v = [ord(c)-63 for c in str] 
 60      if min(v) < 0 or max(v) > 63: 
 61          return None 
 62      return v 
 63           
 64 -def graph6n(data): 
 65      """Read initial one or four-unit value from graph6 sequence.  Return value, rest of seq.""" 
 66      if data[0] <= 62: 
 67          return data[0], data[1:] 
 68      return (data[1]<<12) + (data[2]<<6) + data[3], data[4:] 
 69   
 70 -def parse_graph6(str): 
 71      """Read undirected graph in graph6 format.""" 
 72      if str.startswith('>>graph6<<'): 
 73          str = str[10:] 
 74      data = graph6data(str) 
 75      n, data = graph6n(data) 
 76      nd = (n*(n-1)//2 + 5) // 6 
 77      if len(data) != nd: 
 78          raise NetworkXError, 'Expected %d bits but got %d in graph6' % (n*(n-1)//2, len(data)*6) 
 79   
 80      def bits(): 
 81          """Return sequence of individual bits from 6-bit-per-value 
 82          list of data values.""" 
 83          for d in data: 
 84              for i in [5,4,3,2,1,0]: 
 85                  yield (d>>i)&1 
 86                                   
 87      G=networkx.Graph() 
 88      G.add_nodes_from(range(n)) 
 89      for (i,j),b in zip([(i,j) for j in range(1,n) for i in range(j)], bits()): 
 90          if b: G.add_edge(i,j) 
 91      return G 
 92   
 93 -def parse_sparse6(str): 
 94      """Read undirected graph in sparse6 format.""" 
 95      if str.startswith('>>sparse6<<'): 
 96          str = str[10:] 
 97      if not str.startswith(':'): 
 98          raise NetworkXError, 'Expected colon in sparse6' 
 99      n, data = graph6n(graph6data(str[1:])) 
100      k = 1 
101      while 1<<k < n: 
102          k += 1 
103           
104      def parseData(): 
105          """Return stream of pairs b[i], x[i] for sparse6 format.""" 
106          chunks = iter(data) 
107          d = None # partial data word 
108          dLen = 0 # how many unparsed bits are left in d 
109       
110          while 1: 
111              if dLen < 1: 
112                  d = chunks.next() 
113                  dLen = 6 
114              dLen -= 1 
115              b = (d>>dLen) & 1 # grab top remaining bit 
116                           
117              x = d & ((1<<dLen)-1) # partially built up value of x 
118              xLen = dLen         # how many bits included so far in x 
119              while xLen < k:     # now grab full chunks until we have enough 
120                  d = chunks.next() 
121                  dLen = 6 
122                  x = (x<<6) + d 
123                  xLen += 6 
124              x = (x >> (xLen - k)) # shift back the extra bits 
125              dLen = xLen - k 
126              yield b,x 
127           
128      v = 0 
129   
130      G=networkx.Graph() 
131      G.add_nodes_from(range(n)) 
132   
133      for b,x in parseData(): 
134          if b: v += 1 
135          if x >= n: break # padding with ones can cause overlarge number here 
136          elif x > v: v = x 
137          else: 
138              G.add_edge(x,v) 
139   
140      return G 
141   
142   
143 -def _test_suite(): 
144      import doctest 
145      suite = doctest.DocFileSuite('tests/readwrite/sparsegraph6.txt', 
146                                   package='networkx') 
147      return suite 
148   
149  if __name__ == "__main__": 
150      import os  
151      import sys 
152      import unittest 
153      if sys.version_info[:2] < (2, 4): 
154          print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2] 
155          sys.exit(-1) 
156      # directory of networkx package (relative to this) 
157      nxbase=sys.path[0]+os.sep+os.pardir 
158      sys.path.insert(0,nxbase) # prepend to search path 
159      unittest.TextTestRunner().run(_test_suite()) 
160