Jeff - 9 months ago 65

Python Question

I am working on software that deals with sparse matrices. They're not huge (anywhere from 15x15 to ~300x300). I'd like to be able to store a representation of the matrix in a short string so that I can store it as a value in a CSV file (along with many other things).

What I've tried so far is to treat the matrix as a binary string, and convert to base62:

`import numpy as np`

import networkx as nx

def graphToHash(a,numnodes):

def baseN(num,b,numerals="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"):

return ((num == 0) and numerals[0]) or (baseN(num // b, b, numerals).lstrip(numerals[0]) + numerals[num % b])

return str(numnodes) + '!' + baseN(int(''.join([str(i) for i in flatten_list(a)]),2), 62)

def flatten_list(l):

l1=[item for sublist in l if isinstance(sublist,list) or isinstance(sublist,np.ndarray) for item in sublist]

l=l1+[item for item in l if not isinstance(item,list) and not isinstance(item,np.ndarray)]

return l

# example

import sys

sys.setrecursionlimit(10000)

a=np.array(nx.to_numpy_matrix(nx.connected_watts_strogatz_graph(160,8,.3,1000))).astype(int)

hash=graphToHash(a,160)

len(hash) # ~4300 characters

This works fine for small graphs (30 nodes is ~150 characters). However larger graphs are bit unwieldy (160 nodes is ~4300 and requires me to increase the recursion limit).

Because the graph is binary and sparse, I know I can do better. Ideally I'd like to continue using strings that are {0-9,a-z,A-Z} because I know these will not pose any issues in my CSV file.

What is the most efficient way to compress a binary sparse matrix?

Answer Source

How about using the `sparse6`

format. It uses printable ASCII characters.
http://users.cecs.anu.edu.au/~bdm/data/formats.txt

```
import networkx as nx
G = nx.connected_watts_strogatz_graph(160,4,.3,1000)
s = nx.generate_sparse6(G)
print(len(s))
print(s)
505
>>sparse6<<:~?A__O??K@?SA?[B__D_kE?{F@CH`KI@[J`_L`gM`{NACOaGQ`?QA[R_oIAcTAsUA{VBCWBKXBSHBOZbW[ac\BsSBo^cO_CKacOb_?bCcccgedGfd?hdSiD[jDcldsmdwo_GTE?peGqe[rEcsEktb_^E{vcGwfGyfg{d_{FkAFg}_ObFs~gKgFH@GS\DhAG\BglDGtEG{AG|GhSmHPJhXKhkuHlNiO?CPOIKMILQI\RIdSIlTItUI|VJDMJ@XjHYbwjJPZcxZ_WPc`\Js`FX^_`__`CKL`k\bKc\IXcKldKsbDpfk|WLLhdPeLPjl[nHHllhmf`fLpnl{lMLCMLqM[?Eprm`tmtuM|vNDwNLxNTyN\rN[mKH{i@|n{~LP~OCeDI?oUA_YBOeBOcMOiEosjOyGpAHghZPUIh@sNYKeIKhqMpiNcwzPyO`QOQMS??~QQR`iRql{QsXQqVpqVjhmREXRSyR\NNqZRc?@a[Rk@Jq]
```