Tengo una lista de bordes de 1.2GB de un gráfico en un archivo de texto. Mi PC ubuntu tiene 8 GB de RAM. Cada línea en la entrada se ve como

287111206 357850135

Me gustaría convertirlo en una matriz de adyacencia escasa y enviarlo a un archivo.

Algunas estadísticas para mis datos:

Number of edges: around 62500000
Number of vertices: around 31250000

Hice la misma pregunta antes enhttps://stackoverflow.com/a/38667644/2179021 y obtuve una gran respuesta. El problema es que no puedo hacer que funcione.

Primero probé np.loadtxt para cargar el archivo, pero era muy lento y usaba una gran cantidad de memoria. Entonces, en su lugar, me mudé a pandas.read_csv, que es muy rápido, pero esto causó problemas propios. Este es mi código actual:

import pandas
import numpy as np
from scipy import sparse

data = pandas.read_csv("edges.txt", sep=" ", header= None, dtype=np.uint32)
A = data.as_matrix()
print type(A)
k1,k2,k3=np.unique(A,return_inverse=True,return_index=True)
rows,cols=k3.reshape(A.shape).T
M=sparse.coo_matrix((np.ones(rows.shape,int),(rows,cols)))
print type(M)

El problema es que el marco de datos de pandasdata es enorme y efectivamente estoy haciendo una copia en A que es ineficiente. Sin embargo, las cosas son aún peores ya que el código falla

<type 'instancemethod'>
Traceback (most recent call last):
  File "make-sparse-matrix.py", line 13, in <module>
    rows,cols=k3.reshape(A.shape).T
AttributeError: 'function' object has no attribute 'shape'
raph@raph-desktop:~/python$ python make-sparse-matrix.py 
<type 'numpy.ndarray'>
Traceback (most recent call last):
  File "make-sparse-matrix.py", line 12, in <module>
    k1,k2,k3=np.unique(A,return_inverse=True,return_index=True)
  File "/usr/local/lib/python2.7/dist-packages/numpy/lib/arraysetops.py", line 209, in unique
    iflag = np.cumsum(flag) - 1
  File "/usr/local/lib/python2.7/dist-packages/numpy/core/fromnumeric.py", line 2115, in cumsum
    return cumsum(axis, dtype, out)
MemoryError

Entonces mis preguntas son:

¿Puedo evitar tener tanto la trama de datos pandas de 1.2GB como la copia de matriz numpy de 1.2GB en la memoria?¿Hay alguna forma de completar el código en 8 GB de RAM?

Puede reproducir una entrada de prueba del tamaño con el que estoy tratando de procesar:

import random
#Number of edges, vertices
m = 62500000
n = m/2
for i in xrange(m):
    fromnode = str(random.randint(0, n-1)).zfill(9)
    tonode = str(random.randint(0, n-1)).zfill(9)
    print fromnode, tonode

Actualizar

Ahora he probado varios enfoques diferentes, todos los cuales han fallado. Aquí hay un resumen.

Utilizandoigraph cong = Graph.Read_Ncol('edges.txt'). Esto usa una gran cantidad de RAM que bloquea mi computadora.Utilizandonetworkit conG= networkit.graphio.readGraph("edges.txt", networkit.Format.EdgeList, separator=" ", continuous=False). Esto usa una gran cantidad de RAM que bloquea mi computadora.El código anterior en esta pregunta pero usando np.loadtxt ("edge.txt") en lugar de pandas. Esto usa una gran cantidad de RAM que bloquea mi computadora.

Luego escribí un código separado que reasignó todos los nombres de vértices al número del 1 .. | V | donde | V | es el número total de vértices. Esto debería salvar el código que importa la lista de bordes de tener que construir una tabla que mapee los nombres de vértices. Usando esto probé:

Usando este nuevo archivo de lista de bordes reasignado, utilicé igraph nuevamente cong = Graph.Read_Edgelist("edges-contig.txt"). Esto ahora funciona aunque requiere 4 GB de RAM (que es mucho más que la cantidad teórica que debería). Sin embargo, no existe una función igraph para escribir una matriz de adyacencia dispersa a partir de un gráfico. La solución recomendada esconvertir el gráfico a una matriz_co. Desafortunadamente, esto usa una gran cantidad de RAM que bloquea mi computadora.Usando el archivo de lista de borde reasignado utilicé networkit conG = networkit.readGraph("edges-contig.txt", networkit.Format.EdgeListSpaceOne). Esto también funciona con menos de los 4 GB que necesita igraph. networkit también viene con una función para escribir archivos de Matlab (que es una forma de matriz de adyacencia escasa que puede leer scipy). sin embargonetworkit.graphio.writeMat(G,"test.mat") usa una gran cantidad de RAM que bloquea mi computadora.

Finalmente, la respuesta de Sascha a continuación se completa, pero tarda unos 40 minutos.