/usr/lib/python2.7/dist-packages/networkx/readwrite/sparsegraph6.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 | """
**************
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:]
|