1 """ 2 ************** 3 SparseGraph 6 4 ************** 5 Read graphs in graph6 and sparse6 format. 6 7 Format 8 ------ 9 10 "graph6 and sparse6 are formats for storing undirected graphs in a 11 compact manner, using only printable ASCII characters. Files in these 12 formats have text type and contain one line per graph." 13 http://cs.anu.edu.au/~bdm/data/formats.html 14 15 See http://cs.anu.edu.au/~bdm/data/formats.txt for details. 16 """ 17 # Original author: D. Eppstein, UC Irvine, August 12, 2003. 18 # The original code at http://www.ics.uci.edu/~eppstein/PADS/ is public domain. 19 __author__ = """Aric Hagberg (hagberg (at] lanl.gov)""" 20 # Copyright (C) 2004-2010 by 21 # Aric Hagberg <hagberg (at] lanl.gov> 22 # Dan Schult <dschult (at] colgate.edu> 23 # Pieter Swart <swart (at] lanl.gov> 24 # All rights reserved. 25 # BSD license. 26 27 __all__ = ['read_graph6', 'parse_graph6', 'read_graph6_list', 28 'read_sparse6', 'parse_sparse6', 'read_sparse6_list'] 29 30 import networkx as nx 31 from networkx.exception import NetworkXError 32 from networkx.utils import open_file 33 34 # graph6 35 36 def read_graph6(path): 37 """Read simple undirected graphs in graph6 format from path. 38 39 Returns a single Graph. 40 """ 41 return read_graph6_list(path)[0] 42 43 def parse_graph6(str): 44 """Read a simple undirected graph in graph6 format from string. 45 46 Returns a single Graph. 47 """ 48 def bits(): 49 """Return sequence of individual bits from 6-bit-per-value 50 list of data values.""" 51 for d in data: 52 for i in [5,4,3,2,1,0]: 53 yield (d>>i)&1 54 55 if str.startswith('>>graph6<<'): 56 str = str[10:] 57 data = graph6data(str) 58 n, data = graph6n(data) 59 nd = (n*(n-1)//2 + 5) // 6 60 if len(data) != nd: 61 raise NetworkXError(\ 62 'Expected %d bits but got %d in graph6' % (n*(n-1)//2, len(data)*6)) 63 64 G=nx.Graph() 65 G.add_nodes_from(range(n)) 66 for (i,j),b in zip([(i,j) for j in range(1,n) for i in range(j)], bits()): 67 if b: G.add_edge(i,j) 68 return G 69 70 @open_file(0,mode='rt') 71 def read_graph6_list(path): 72 """Read simple undirected graphs in graph6 format from path. 73 74 Returns a list of Graphs, one for each line in file. 75 """ 76 glist=[] 77 for line in path: 78 line = line.strip() 79 if not len(line): continue 80 glist.append(parse_graph6(line)) 81 return glist 82 83 # sparse6 84 85 def read_sparse6(path): 86 """Read simple undirected graphs in sparse6 format from path. 87 88 Returns a single MultiGraph.""" 89 return read_sparse6_list(path)[0] 90 91 @open_file(0,mode='rt') 92 def read_sparse6_list(path): 93 """Read undirected graphs in sparse6 format from path. 94 95 Returns a list of MultiGraphs, one for each line in file.""" 96 glist=[] 97 for line in path: 98 line = line.strip() 99 if not len(line): continue 100 glist.append(parse_sparse6(line)) 101 return glist 102 103 def parse_sparse6(string): 104 """Read undirected graph in sparse6 format from string. 105 106 Returns a MultiGraph. 107 """ 108 if string.startswith('>>sparse6<<'): 109 string = str[10:] 110 if not string.startswith(':'): 111 raise NetworkXError('Expected colon in sparse6') 112 n, data = graph6n(graph6data(string[1:])) 113 k = 1 114 while 1<<k < n: 115 k += 1 116 117 def parseData(): 118 """Return stream of pairs b[i], x[i] for sparse6 format.""" 119 chunks = iter(data) 120 d = None # partial data word 121 dLen = 0 # how many unparsed bits are left in d 122 123 while 1: 124 if dLen < 1: 125 d = next(chunks) 126 dLen = 6 127 dLen -= 1 128 b = (d>>dLen) & 1 # grab top remaining bit 129 130 x = d & ((1<<dLen)-1) # partially built up value of x 131 xLen = dLen # how many bits included so far in x 132 while xLen < k: # now grab full chunks until we have enough 133 d = next(chunks) 134 dLen = 6 135 x = (x<<6) + d 136 xLen += 6 137 x = (x >> (xLen - k)) # shift back the extra bits 138 dLen = xLen - k 139 yield b,x 140 141 v = 0 142 143 G=nx.MultiGraph() 144 G.add_nodes_from(range(n)) 145 146 for b,x in parseData(): 147 if b: v += 1 148 if x >= n: break # padding with ones can cause overlarge number here 149 elif x > v: v = x 150 else: 151 G.add_edge(x,v) 152 153 return G 154 155 # helper functions 156 157 def graph6data(str): 158 """Convert graph6 character sequence to 6-bit integers.""" 159 v = [ord(c)-63 for c in str] 160 if min(v) < 0 or max(v) > 63: 161 return None 162 return v 163 164 def graph6n(data): 165 """Read initial one or four-unit value from graph6 sequence. 166 Return value, rest of seq.""" 167 if data[0] <= 62: 168 return data[0], data[1:] 169 return (data[1]<<12) + (data[2]<<6) + data[3], data[4:] 170
