Group Abstract Group Abstract

Message Boards Message Boards

1
|
8.2K Views
|
10 Replies
|
10 Total Likes
View groups...
Share
Share this post:

Handle issues in connection with GraphData for Cubic graphs?

Zs Sz
Posted 5 years ago

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.
POSTED BY: Zs Sz
10 Replies
Sort By:
Zs Sz
Zs Sz
Posted 5 years ago

Alright, thank You very much! :)
POSTED BY: Zs Sz

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.
POSTED BY: Szabolcs Horvát
Zs Sz
Zs Sz
Posted 5 years ago

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.
POSTED BY: Zs Sz

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.
POSTED BY: Szabolcs Horvát

Great, I'm glad it worked :-)
POSTED BY: Szabolcs Horvát
Zs Sz
Zs Sz
Posted 5 years ago

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.
POSTED BY: Zs Sz

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.
POSTED BY: Szabolcs Horvát
POSTED BY: Szabolcs Horvát
Zs Sz
Zs Sz
Posted 5 years ago

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... :)

Thank you for everything!
POSTED BY: Zs Sz

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: http://szhorvat.net/mathematica/IGraphM

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]

enter image description here
POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard