"""
**************
SparseGraph 6
**************
Read graphs in graph6 and sparse6 format.
See http://cs.anu.edu.au/~bdm/data/formats.txt
"""
# Original author: D. Eppstein, UC Irvine, August 12, 2003.
# The original code at http://www.ics.uci.edu/~eppstein/PADS/ is public domain.
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
# Copyright (C) 2004-2008 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__ = ['read_graph6', 'parse_graph6', 'read_graph6_list',
'read_sparse6', 'parse_sparse6', 'read_sparse6_list']
import networkx
from networkx.exception import NetworkXException,NetworkXError
from networkx.utils import _get_fh
def read_graph6_list(path):
"""Read simple undirected graphs in graph6 format from path.
Returns a list of Graphs, one for each line in file."""
fh=_get_fh(path,mode='r')
glist=[]
for line in fh:
line = line.strip()
if not len(line): continue
glist.append(parse_graph6(line))
return glist
def read_graph6(path):
"""Read simple undirected graphs in graph6 format from path.
Returns a single Graph."""
return read_graph6_list(path)[0]
def read_sparse6_list(path):
"""Read simple undirected graphs in sparse6 format from path.
Returns a list of Graphs, one for each line in file."""
fh=_get_fh(path,mode='r')
glist=[]
for line in fh:
line = line.strip()
if not len(line): continue
glist.append(parse_sparse6(line))
return glist
def read_sparse6(path):
"""Read simple undirected graphs in sparse6 format from path.
Returns a single Graph."""
return read_sparse6_list(path)[0]
def graph6data(str):
"""Convert graph6 character sequence to 6-bit integers."""
v = [ord(c)-63 for c in str]
if min(v) < 0 or max(v) > 63:
return None
return v
def graph6n(data):
"""Read initial one or four-unit value from graph6 sequence. Return value, rest of seq."""
if data[0] <= 62:
return data[0], data[1:]
return (data[1]<<12) + (data[2]<<6) + data[3], data[4:]
def parse_graph6(str):
"""Read undirected graph in graph6 format."""
if str.startswith('>>graph6<<'):
str = str[10:]
data = graph6data(str)
n, data = graph6n(data)
nd = (n*(n-1)//2 + 5) // 6
if len(data) != nd:
raise NetworkXError, 'Expected %d bits but got %d in graph6' % (n*(n-1)//2, len(data)*6)
def bits():
"""Return sequence of individual bits from 6-bit-per-value
list of data values."""
for d in data:
for i in [5,4,3,2,1,0]:
yield (d>>i)&1
G=networkx.Graph()
G.add_nodes_from(range(n))
for (i,j),b in zip([(i,j) for j in range(1,n) for i in range(j)], bits()):
if b: G.add_edge(i,j)
return G
def parse_sparse6(str):
"""Read undirected graph in sparse6 format."""
if str.startswith('>>sparse6<<'):
str = str[10:]
if not str.startswith(':'):
raise NetworkXError, 'Expected colon in sparse6'
n, data = graph6n(graph6data(str[1:]))
k = 1
while 1<<k < n:
k += 1
def parseData():
"""Return stream of pairs b[i], x[i] for sparse6 format."""
chunks = iter(data)
d = None # partial data word
dLen = 0 # how many unparsed bits are left in d
while 1:
if dLen < 1:
d = chunks.next()
dLen = 6
dLen -= 1
b = (d>>dLen) & 1 # grab top remaining bit
x = d & ((1<<dLen)-1) # partially built up value of x
xLen = dLen # how many bits included so far in x
while xLen < k: # now grab full chunks until we have enough
d = chunks.next()
dLen = 6
x = (x<<6) + d
xLen += 6
x = (x >> (xLen - k)) # shift back the extra bits
dLen = xLen - k
yield b,x
v = 0
G=networkx.Graph()
G.add_nodes_from(range(n))
for b,x in parseData():
if b: v += 1
if x >= n: break # padding with ones can cause overlarge number here
elif x > v: v = x
else:
G.add_edge(x,v)
return G
|