1 """
2 Read graphs in graph6 and sparse6 format.
3 See http://cs.anu.edu.au/~bdm/data/formats.txt
4
5 """
6
7
8 __author__ = """Aric Hagberg (hagberg@lanl.gov)"""
9 __date__ = """"""
10 __credits__ = """"""
11 __revision__ = ""
12
13
14
15
16
17
18
19 import networkx
20 from networkx.exception import NetworkXException, NetworkXError
21 from networkx.utils import _get_fh
22
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
35 """Read simple undirected graphs in graph6 format from path.
36 Returns a single Graph."""
37 return read_graph6_list(path)[0]
38
39
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
52 """Read simple undirected graphs in sparse6 format from path.
53 Returns a single Graph."""
54 return read_sparse6_list(path)[0]
55
56
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
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
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
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
108 dLen = 0
109
110 while 1:
111 if dLen < 1:
112 d = chunks.next()
113 dLen = 6
114 dLen -= 1
115 b = (d>>dLen) & 1
116
117 x = d & ((1<<dLen)-1)
118 xLen = dLen
119 while xLen < k:
120 d = chunks.next()
121 dLen = 6
122 x = (x<<6) + d
123 xLen += 6
124 x = (x >> (xLen - k))
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
136 elif x > v: v = x
137 else:
138 G.add_edge(x,v)
139
140 return G
141
142
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
157 nxbase=sys.path[0]+os.sep+os.pardir
158 sys.path.insert(0,nxbase)
159 unittest.TextTestRunner().run(_test_suite())
160