Hellow everyone
I downloaded a notebook about Cactus Graph downloaded from http://mathworld.wolfram.com/CactusGraph.html. I want to get all cacti Graph of order 8.
But I don’t know how to use the program from it. what should I do ?
thanks
CactusGraph _OP_1_CP_.nb (676 KB)
Welcome to Wolfram Community! Please make sure you know the rules: https://wolfr.am/READ-1ST
The rules explain how to format your code properly. If you do not format code, it may become corrupted and useless to other members. Please EDIT your post and make sure code blocks start on a new paragraph and look framed and colored like this.
int = Integrate[1/(x^3 - 1), x];
Map[Framed, int, Infinity]
Thanks Mr, sorry, I just see it.
You will find all of them up to 7 vertices in GraphData. Note that GraphData is just a database. It contains all undirected simple graphs up to 7 vertices, but only certain specific instances above 7.
Get all cactus graphs from the database:
GraphData["Cactus"]
Get all 8-vertex cactus graphs from the database:
Select[GraphData[8], GraphData[#, "Cactus"] &]
Is that all of them? To check, let’s write a function to test if a graph is a cactus.
ClearAll[cactusGraphQ]
cactusGraphQ[g_?UndirectedGraphQ] :=
ConnectedGraphQ[g] && AllTrue[
KVertexConnectedComponents[g, 2],
With[{sg = Subgraph[g, #]}, EdgeCount[sg] <= VertexCount[sg]] &
]
cactusGraphQ[_] := False;
Now we want to generate all non-isomorphic 8-vertex graphs and filter the list. I like to use the geng tool from the nauty suite for this. I have it installed at /opt/local/bin/geng. Adjust the next command with wherever you installed this tool.
glist8 = Import["!/opt/local/bin/geng -c 8", "Graph6"];
cacti8 = Select[glist8, cactusGraphQ];
Length[cacti8]
(* 188 *)
Check OEIS to confirm we made no mistake: https://oeis.org/A000083 188 is indeed correct.
Thanks, but I am intrested to generate all non-isomorphic 8-vertex graphs and filter the list
how do I use the geng tool from the nauty suite for this, and I will try.
I am not sure that I understand your last comment …
In my previous post, I showed how to generate all non-isomorphic 8-vertex cacti with the help of geng and a custom cactus-testing function.
Since then, the IGraph/M package got a very fast function to test if a graph is a cactus. With that tool, the task can be accomplished even faster.
In[1]:= << IGraphM`
During evaluation of In[1]:= IGraph/M 0.3.112 (May 7, 2019)
During evaluation of In[1]:= Evaluate IGDocumentation[] to get started.
In[2]:= glist8 = Import["!/opt/local/bin/geng -c 8", "Graph6"]; // AbsoluteTiming
Out[2]= {2.72071, Null}
In[3]:= cacti8 = Select[glist8, IGCactusQ]; // AbsoluteTiming
Out[3]= {0.40647, Null}
It is actually fast enough that we can easily go to 10 vertices.
Keep in mind that a cactus has between V-1 and \lfloor3(V-1)/2\rfloor vertices.
In[12]:=
glist9 = Import["!/opt/local/bin/geng -c 9 8:12", "Graph6"]; // AbsoluteTiming
cacti9 = Select[glist9, IGCactusQ]; // AbsoluteTiming
Length[cacti9]
Out[12]= {1.90844, Null}
Out[13]= {0.379368, Null}
Out[14]= 596
In[15]:=
glist10 = Import["!/opt/local/bin/geng -c 10 9:13", "Graph6"]; // AbsoluteTiming
cacti10 = Select[glist10, IGCactusQ]; // AbsoluteTiming
Length[cacti10]
Out[15]= {9.49928, Null}
Out[16]= {1.7138, Null}
Out[17]= 1979
If you have a bit of patience, probably 11 vertices are also feasible.
Run geng -help on the command line to understand the syntax.
It turns out that the bottleneck is not even the generation of non-isomorphic graphs, or filtering for cacti, but simply reading the Graph6 format. Import[..., "Graph6"] is slower than it should be.
I just implemented a 5x faster custom Graph6 reader for IGraph/M. Now we can have all 11-vertex cacti in under a minute. This Graph6 importer will be included in the next version of IGraph/M.
Thanks for your very detailed solution, When I click on the url About – Szabolcs Horvát, and I follow his instructions and install IGraph/M in my mathematica, it is good and easy. and I can use this useful tools.
But I tried several times to install nauty26r11 tool , and I have failed.
My computer system is Windows 10, is it incompatibility ?
How to install the useful graph tool ? I am very eager to use it.
Where are the installation instructions? Thank you again
I’m afraid that nauty needs to be compiled from source, and that, like most scientific tools, it is not very Windows-friendly.
I rarely use Windows, so I cannot give you precise instructions. But it seems to me that the easiest way to compile it would be to use https://www.msys2.org/ which provides a Unix-line command line, and makes it possible to install the typical tools. It may be necessary to install autoconf in addition to the gcc compiler. Then it would be possible to follow the instructions in nauty’s README file.
The latest public version of IGraph/M now supports importing Graph6, Sparse6 and Digraph6 with good performance. Note that Mathematica does not have a built-in support for Digraph6 and is slower when importing the other two formats.
For a showcase, see https://mathematica.stackexchange.com/a/214436/12
In 2022, I compiled the source code of nauty into Windows binaries using Cygwin, and it is now ready to run under Windows. Before that, I had Linux installed on my computer.
glist8 = Import["!D:/nauty27r3/geng -c 8,", "Graph6"]; // AbsoluteTiming
Length[glist8]
I would like to thank you for helping me with programming on this platform or Mathematica Stack for the past three years.
