2
$\begingroup$

I am using the code provided in the answer for this other question. It is shown below:

allEdges[n_]:=Flatten[Table[UndirectedEdge[i,j],{i,1,n},{j,i+1,n}]]; allConnected[n_]:=Select[Map[Graph[Range[n],#,VertexLabels->Automatic]&, Subsets[allEdges[n]]],ConnectedGraphQ]; allConnectedUpToIso[n_]:=DeleteDuplicates[allConnected[n],IsomorphicGraphQ];

However, I am trying to do n = 9 for 9 nodes, and Mathematica is telling me I don't have enough RAM to compute it (closing all applications and restarting my computer didn't help). I was able to complete 6 notes/n = 6. Is there a way to have it generate only a limited number of graphs for n = 9 rather than all of them, so I can actually run the program? Thank you.

Edit: Or, if there's a fix to make it not use so much memory, that would be greatly appreciated.

Improve this question
$\endgroup$
5
  • $\begingroup$ The number of such graphs is given here, for N=9 it's only 261080, this should be manageable. The code in the linked answer is brute force, generating a significantly larger number of graphs and then filtering, which is where the problem lies. Unfortunately I don't know how to generate just the graphs you are looking for, but maybe the link is helpful. $\endgroup$ Commented Jun 6 at 6:02
  • 1
    $\begingroup$ Do you want labelled graphs (as in the question you linked to)? If so, there's probably too many of these. Or do you want unlabelled ones? In that case use nauty, Import["! geng -c 9", "Graph6"], or with IGraph/M (faster and more supported import formats) IGImport["! geng -c 9", "Nauty"]. Search for my answers that utilize nauty / geng on this site. $\endgroup$ Commented Jun 6 at 8:24
  • $\begingroup$ You can get all trees on $n$ unlabeled nodes by Graph[GraphData[#, "Graph"], VertexLabels -> "Name"] & /@ GraphData["Tree", n]. (There are 47 trees on 9 nodes.) Then you can add as many edges as you want. $\endgroup$ Commented Jun 6 at 8:32
  • $\begingroup$ @A.Kato It's not possible to generate all graphs this way. If you want labelled graphs, starting with unlabelled trees is not going to work. If you want unlabelled graphs, adding edges to trees will create isomorphic duplicates. There is no need to try to come up with such hacks when there are excellent tools that get the job done (nauty). $\endgroup$ Commented Jun 6 at 8:52
  • $\begingroup$ @Szabolcs I don't think I necessarily need labelled graphs. I will try looking through your previous answers and working with nauty, and then I will see how that works out for me. Thank you! $\endgroup$ Commented Jun 6 at 20:14

1 Answer 1

Reset to default
3
$\begingroup$

What ended up working for me was using Nauty, generating the graphs, and taking the output that Nauty created and putting it in Mathematica.

I was using Google Colab to run Nauty instead of installing it onto my computer because I didn't want to install files onto my computer. I installed Nauty, ran the "!geng -c 9" code in Colab, then outputted the answer into a txt file. (Unfortunately, Colab was giving me "Streaming output truncated to the last 5000 lines," so I had to use the code below to put the results in a txt file in my Drive.)

from google.colab import drive drive.mount('/content/drive') import os

then

import subprocess # Run the command and capture the output result = subprocess.run(['/content/nauty2_8_9/geng', '-c', '9'], capture_output=True, text=True) print(result.stdout)

then

os.chdir("/content/drive/") with open('/content/drive/MyDrive/output.txt','w') as out: out.write(result.stdout)

with the output file and uploading to Drive from this other post.

I then downloaded output file to my computer and ran it in Mathematica using this code:

Import["/Users/[username]/Downloads/output.txt", "Graph6"]

Just the location of where the output file was. This generated enough graphs for what I need. (Not sure if it's all of them, didn't check.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for putting in the effort to write up the answer after you solved the problem :-) $\endgroup$ Commented Jun 10 at 0:33
  • $\begingroup$ @Szabolcs No problem! :) $\endgroup$ Commented Jun 11 at 19:45

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.