Package networkx :: Package readwrite :: Module sparsegraph6
[hide private]
[frames] | no frames]

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