search

bovine3dom / Nauty.jl

A small Julia wrapper for nauty
Other
8 stars 5 forks source link

Memory issue for graphs with more than 64 vertices #9

Open kris-brown opened 2 years ago

kris-brown commented 2 years ago

Hi, I'm trying to work with graphs with larger than 64 vertices, and I'm stuck trying to get it to work. Looking at Section 4 of the nauty manual, it seems like I should set MAXN=0 so that memory is dynamically allocated and the max order is ~10^9. I tried to accomplish this by running build.jl with gcc -DWORDSIZE=64 -DMAXN=0 -O4 ..., but I continue to get the error:

nauty: need n <= min(2000000000,64*m), but n=200 (where n is always 2x the order of the graph I tried to compute)

Is there something about MAXN that is hardcoded into Nauty.jl's implementation or am I just failing to compile nauty the correct way?

Thanks for any help you can offer!

kris-brown commented 2 years ago

Hi - just checking in on this again since I'm still getting great use out of Nauty.jl (though occasionally hitting the 64 vertex limit). I'm happy to try addressing this issue (once I fully understand what the issue is).

cmcaine commented 2 years ago

I think the most likely issue is that the lg_to_nauty function throws away the information on the number of setwords and number of vertices https://github.com/bovine3dom/Nauty.jl/blob/89762d5f2909d6e4c4372b95c9730361fd6c3acf/src/Nauty.jl#L324-L355

We then try to recreate that information in densenauty by asking for the size of the array, but arr.chunks will be a vector, so the size isn't right. This matches your 2x problem if your number of nodes is between 65 and 128 and I would expect 3x for 129-192.

It might be enough to replace the final line of lg_to_nauty with this:

reshape(arr.chunks, num_vertices, num_setwords)

It'll still fail if WORDSIZE if anything other than 64, but it should work for your case.

A perhaps better fix would be to make lg_to_nauty return the three values or a struct and adapt densenauty so that it uses that information.

Anyway, try it out, let us know if it works? If it doesn't, could you fork this repo and push your changes to build.jl etc. and also provide a complete example script that gives the error?

kris-brown commented 2 years ago

Hi, I get a segfault when I try that change to the last line of lg_to_nauty, so I've pushed the change (including setting DMAXN=0 in build.jl) to a fork here

The test file is test/bigtest.jl - really appreciate you taking a look!

Dnl-rs commented 4 months ago

Hey, I followed issue #7 and got nauty to work on my side. But now I have the same problem regarding the number of vertices being larger than 64. Did you figure out a solution to this problem? Changing DMAXN=0 creates the same error for me as the initial one in this issue. The fork does not seem to have solved this problem. For me nauty does not stop and seems to be stuck in a loop. Had the same problem when the labeling was wrong but checked it and the error does seem to be connected to it. It also works with the number of vertices being smaller than 64, so I suspect of having the same issue as depicted here.