File: sparsegraph6.py

package info (click to toggle)
python-networkx 1.7~rc1-3
  • links: PTS, VCS
  • area: main
  • in suites: wheezy
  • size: 4,128 kB
  • sloc: python: 44,557; makefile: 135
file content (169 lines) | stat: -rw-r--r-- 4,749 bytes parent folder | download
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:]