1
$\begingroup$

I have a weighted, undirected graph with weighted edges, that could be represented in mathematica by the following code for $N=3$

    Graph[{Labeled[1 \[UndirectedEdge] 2, "0.21+\[ImaginaryI]"], 
  Labeled[2 \[UndirectedEdge] 3, "2"], 
  Labeled[3 \[UndirectedEdge] 1, "1"]}, VertexLabels -> "Name"]

What is the best way to store such graphs when $N\sim 10^6$ with regard to memory usage, retrieval of edge/vertices weights speed, and value replacement speed ?

I know about matrices and sparse matrices, and associations. But these structures generally include redundant information or useless ones (lots of 0 for example...). Is there anything more efficient ? Including in other languages if you happen to know anything abouth other languages !

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ Store vertex and edge data (such as weights) in a packed array. And store the graph combinatorics in the form of the adjacency matrix in a sparse array. The point of sparse arrays is that the zeros are not stored explicitly. $\endgroup$
    – Henrik Schumacher
    Commented Mar 12, 2021 at 20:53
  • 1
    $\begingroup$ It's not really clear to me what the question is. What do you want to achieve? Store it in a compact format in a file? Store it in a compact way in memory? Store it in memory in such a way that it can be manipulated efficiently? If so, how do you plan to manipulate it? $\endgroup$
    – Szabolcs
    Commented Mar 14, 2021 at 11:08
  • $\begingroup$ Basically, I have an algorithm that simulates few atom interactions on a grid, and I am building a Hamiltonian which effectively is nothing but a big matrix or a graph linking states. The number of states in the Hilbert space I am considering is kind of big, and I am working on optimizing my code, the suggestion by Henrik regarding PackedArrays, was nice, and I am now using them. When pushing it to the limits, my programm runs out of memory, I think RAM, (but I am not an expert), and so I was looking for ways to store the same data (the hamiltonian elements), in the most compact way... $\endgroup$
    – DarkBulle
    Commented Mar 14, 2021 at 21:05
  • $\begingroup$ ...while still being able to retrieve elements rapidly because to build adjacent elements to a given element of the graph, I need to know what this element is, so I cannot use things like Compress for example. I was looking for suggestions much like Henrik provided, not like a ready to use code or anything. @Szabolcs $\endgroup$
    – DarkBulle
    Commented Mar 14, 2021 at 21:07
  • 2
    $\begingroup$ @yfs It seems your application relies on linear algebra, so sparse matrices seem like a natural choice. You say, "But these structures generally include redundant information or useless ones (lots of 0 for example...)." This is not true for sparse matrices. $\endgroup$
    – Szabolcs
    Commented Mar 15, 2021 at 11:53

1 Answer 1

Reset to default
1
$\begingroup$

You can use DumpSave:

g = GridGraph[{1000, 1000}];

VertexCount[g]

1000000

ByteCount[g]

95969272

DumpSave["graph.mx", g];

FileByteCount["graph.mx"]

47968625

The caveat is when retrieving the graph, we need to reinitialize it too after importing the mx file. My guess is that mx files store the expression in InputForm and Graph is not a regular expression.

<<"graph.mx";

VertexCount[g]; // RepeatedTiming

{0.791, Null}

g = g;

VertexCount[g]; // RepeatedTiming

{4.3*10^-7, Null}
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.