1
$\begingroup$

I badly need data about edges in all graphs (or maybe just connected ones will satisfy me -- it depends on further research) on $n$ vertices for as great $n$ as possible. I have already downloaded it up to $n = 8$ from built-in GraphData and wrote in a file, but need more.

It was already discussed here that GraphData database has complete information for graphs on less or equal than $7$ vertices, which doesn't satisfy me.

I gave a try to old Combinatorica package, but even execution of the `

Needs["Combinatorica`"]
Table[Length@ListGraphs[k], {k, 1, 8}]

took all the CPU resources and about $4$ Gb of RAM, after that I used to abort it, since it was close to the limit of my laptop.

Is there any way how can I get readable for further usage in Wolfram Mathematica data about all graphs (edges in them) with greater than $7$ or $8$ vertices avoiding GraphData and direct calculations with ListGraphs? Maybe it is possible to download it somewhere and convert to appropriate for Wolfram Mathematica format?

$\endgroup$
  • $\begingroup$ All the source code for ListGraphs is down inside the Mathematica tree in Combinatorica.m, which is so much better than when it is compiled into the kernel where nobody can inspect it, and is only a handful of lines. Perhaps you could study that code and see if it would be possible to "turn it inside out" to generate graphs one at a time and do your processing as each one is generated. $\endgroup$ – Bill Oct 28 '17 at 21:00
  • $\begingroup$ What kind of data do you need? In all kind of graphs all kind of edges appear ;-) Why don't you generate all possible graphs from all possible adjacency matrices? $\endgroup$ – M. Stern Oct 28 '17 at 21:09
  • 2
    $\begingroup$ Brendan McKay gives lists up to 10 nodes here $\endgroup$ – Eric Weisstein Oct 30 '17 at 13:25
3
$\begingroup$

Brendan McKay's nauty suite includes graph generation tools. The geng program can generate all non-isomorphic undirected graphs on $n$ nodes. The output is in Graph6 format, which Mathematica supports.

I am currently using OS X and I installed nauty using MacPorts (sudo port install nauty), which placed it in /opt/local/bin. You will need to replace the paths below with wherever you install nauty yourself. Now I can get a list of graphs on 4 nodes like this:

Import["!/opt/local/bin/geng 4", "Graph6"]

enter image description here

If you are patient, you can generate larger sets too:

graphs = Import["!/opt/local/bin/geng 8", "Graph6"]; // AbsoluteTiming
(* {4.15069, Null} *)

Length[graphs]
(* 12346 *)

But be aware that the number of graphs (and the time needed to compute them) will quickly explode.

graphs = Import["!/opt/local/bin/geng 9", "Graph6"]; // AbsoluteTiming
(* {105.883, Null} *)

Length[graphs]
(* 274668 *)

When you generate larger graphs, you probably do not want to import the entire list at once. Instead, you can do the following.

This command starts the geng program:

process = StartProcess[{"/opt/local/bin/geng", "11"}]

You do not need to wait until geng finishes to start reading the graphs. You can use Import[process, {"Graph6", "GraphList", k}] to read the kth graph generated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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