| """ |
| ************** |
| SparseGraph 6 |
| ************** |
| Read graphs in graph6 and sparse6 format. |
| |
| Format |
| ------ |
| |
| "graph6 and sparse6 are formats for storing undirected graphs in a |
| compact manner, using only printable ASCII characters. Files in these |
| formats have text type and contain one line per graph." |
| http://cs.anu.edu.au/~bdm/data/formats.html |
| |
| See http://cs.anu.edu.au/~bdm/data/formats.txt for details. |
| """ |
| # 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-2010 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 as nx |
| from networkx.exception import NetworkXError |
| from networkx.utils import open_file |
| |
| # graph6 |
| |
| def read_graph6(path): |
| """Read simple undirected graphs in graph6 format from path. |
| |
| Returns a single Graph. |
| """ |
| return read_graph6_list(path)[0] |
| |
| def parse_graph6(str): |
| """Read a simple undirected graph in graph6 format from string. |
| |
| Returns a single Graph. |
| """ |
| 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 |
| |
| 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)) |
| |
| G=nx.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 |
| |
| @open_file(0,mode='rt') |
| 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. |
| """ |
| glist=[] |
| for line in path: |
| line = line.strip() |
| if not len(line): continue |
| glist.append(parse_graph6(line)) |
| return glist |
| |
| # sparse6 |
| |
| def read_sparse6(path): |
| """Read simple undirected graphs in sparse6 format from path. |
| |
| Returns a single MultiGraph.""" |
| return read_sparse6_list(path)[0] |
| |
| @open_file(0,mode='rt') |
| def read_sparse6_list(path): |
| """Read undirected graphs in sparse6 format from path. |
| |
| Returns a list of MultiGraphs, one for each line in file.""" |
| glist=[] |
| for line in path: |
| line = line.strip() |
| if not len(line): continue |
| glist.append(parse_sparse6(line)) |
| return glist |
| |
| def parse_sparse6(string): |
| """Read undirected graph in sparse6 format from string. |
| |
| Returns a MultiGraph. |
| """ |
| if string.startswith('>>sparse6<<'): |
| string = str[10:] |
| if not string.startswith(':'): |
| raise NetworkXError('Expected colon in sparse6') |
| n, data = graph6n(graph6data(string[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 = next(chunks) |
| 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 = next(chunks) |
| 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=nx.MultiGraph() |
| 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 |
| |
| # helper functions |
| |
| 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:] |