Handle issues in connection with GraphData for Cubic graphs?

Questions
,
1

Dear All,

I am really new in Mathematica, so every advice or answer is appreciated. I would like to examine the connection between the number of the vertices of a cubic graph and the diameter of the cubic graph.

As a first step I thought using GraphData[“Cubic”,n] would be a good idea. But if n=12 I get {Cubic,{12,91}}, {Cubic,{12,93}} and {Cubic, {12,94}} (besides another 91 graphs) which are not recognised as graphs by any other function in Mathematica (I also tried free form input). Did I make a mistake or what could go wrong? It would be important for me to find all cubic graphs for several ns.

And also if I use n=14 then there are 25 similar cases ({Cubic,{14,538}}, etc.). Is there a solution for this?

And last but not least for bigger ns GraphData gives only a few graphs but in theory there are thousands of such graphs. Are there any functions in Mathematica that provide the same results for bigger ns too? Or how are these ~20 graphs are selected by the function from the thousands of them?

Thank you for your answers and help in advance! Have a nice day!

Kind regards,
Zs. Sz.

2

GraphData is just a database a curated collection of graphs. As I remember, it is exhaustive up to 7 vertices, but above that, it only includes examples of special interest.

Do not use GraphData if you want all graphs with a certain property (at least not above n=7).

To generate all cubic graphs, I recommend the geng tool from the nauty suite. You will need to compile and install these tools on your own (unless your operating systems package manager has them; I usually get them with MacPorts).

geng outputs graphs in Graph6 format, which Mathematica’s built-in Import can read, but IGImport in the IGraph/M package can read even faster. (IGraph/M also supports importing directed graphs in this format—Import currently does not.)

Get IGraph/M here: IGraph/M: a Mathematica interface for igraph

Here’s an example that counts how many cubic graphs are there on 12 vertices with different diameters:

IGImport["!geng -d3 -D3 12", "Nauty"] // Map[IGDiameter] // Counts // KeySort

(* <|3 -> 34, 4 -> 43, 5 -> 6, 6 -> 2, \[Infinity] -> 9|> *)

There are 34 with diameter 3, 43 with 4, etc. A diameter of Infinity means that the graph is disconnected.

-d3 -D3 in the geng call sets both the minimum and the maximum degree to 3. If you are not interested in disconnected graphs, we can filter those with -c.

Now we can go to bigger graphs: this only takes 1.5 seconds on my machine.

IGImport["!geng -d3 -D3 -c 16", "Nauty"] // Map[IGDiameter] // Counts // KeySort

(* <|3 -> 14, 4 -> 2167, 5 -> 1499, 6 -> 261, 7 -> 101, 8 -> 14, 9 -> 4|> *)

BarChart[%, ChartLabels -> Automatic]

bc.png
bc.png360×223 2.97 KB

3

Dear Szabolcs Horvát,

First of all, thank you for your reply and help! I really appreciate it. Based on the examples you presented above this tool is just perfect for me, but unfortunately I could not manage to make it work.

I downloaded the recommended Nauty and Traces, but I use Windows 10 instead of Mac, so at first I used Cygwin to compile and install these tools, however it did not work on my computer. Then I tried to use another computer with Linux to compile and install, and then just copied the files back to the original computer, but I am not convinced that this method solved the entire problem. And I also find out in your documentation that in your examples we assume that the gtools programs are in a directory that is on the operating system’s PATH environment variable. Unfortunatelly I could not figure out how exactly these environments work in Mathematica, but maybe this cause the problem. I do not know, but I get the following warning messages after using the first example you wrote:

-Counts: The argument IGImport[IGDiameter[!geng -d3 -D3 -c 12],IGDiameter[Nauty]] is not a list.

-KeySort: The argument Counts[IGImport[IGDiameter[!geng -d3 -D3 -c 12],IGDiameter[Nauty]]] is not a valid Association or a list of rules.

I also tried the following:

Import["!geng -d3 -D3 12", "Graph6"]

But I got another error, which says ‘Import: Cannot import data as Graph6 format.’

Do you have any ideas what could cause the problem? I think I need exactly this tool, so I would be really happy if I could make it work. Thank you for your help!

Also, I do not really know the rules and features of this forum, but I suppose only English is allowed. However if there is a private message option, then maybe it would be easier to discuss the problem there, because based on your name we both speak Hungarian… :slight_smile:

Thank you for everything!

4

Unfortunately, the tool I mentioned doesn’t come with pre-compiled binaries. Indeed you must compile it yourself. Generally, that can be done by running

./configure
make

in the source directory. I would expect this to work with either Cygwin or MSYS2, but I do not use Windows myself, so I couldn’t try.

One compilation finishes, you should see several programs appear in that directory, including geng.exe.

so at first I used Cygwin to compile and install these tools, however it did not work on my computer

What exactly happened?

You may need to copy cygwin.dll next to the executables before they will work outside of the cygwin shell.

And I also find out in your documentation that in your examples we assume that the gtools programs are in a directory that is on the operating system’s PATH environment variable. Unfortunatelly I could not figure out how exactly these environments work in Mathematica, but maybe this cause the problem

It is actually not necessary to put them on the path. It is sufficient to call them with the full path. For example, on my system, these tools are installed in /opt/local/bin, so I call them using

IGImport["!/opt/local/bin/geng 3", "Graph6"]

Don’t forget the ! at the beginning.

Regarding the errors that IGImport showed: this is a small bug in IGImport. It doesn’t handle it well when the path to the file to be imported is incorrect or the file does not exist. I already fixed this and the fix will be released with the next version shortly. The bug only surfaces when the input to IGImport is incorrect, otherwise it imports things fine.

5

P.S. For importing undirected graphs, you can also use the built-in Import["...", "Graph6"]. However, IGImport will be noticeably faster for a large number of graphs.

6

Thank you for your help! Now it is working properly.
At first I got some error when I tried to use ./configure. Later I figured out that there were some ‘hidden’ (not automatically installed) Cygwin packages (like gcc-g++) that were needed. After that I managed to install the geng.exe, but in Mathematica I still got some errors in connection with the absence of cygwin1.dll, but I could find the solution for this relatively easily.

Thank you for your time and help, I really appreciate it.

7

Great, I’m glad it worked :slight_smile:

8

I made a new release of IGraph/M which fixes the error checking in IGImport. Now it should not blow up if it gets unexpected input.

9

Dear Szabolcs,

Thank You for Your previous help. My last question is the following: How should we cite the IGraph/M package in our paper?

Thank You in advance.

10

IGraph/M now has its own DOI, and you can find citation information here: https://doi.org/10.5281/zenodo.1134932 There is a “cite as” box on the right hand side, a bit down on the page.

11

Alright, thank You very much! :slight_smile: