# Message Boards

Posted 1 year ago
2321 Views
|
11 Replies
|
4 Total Likes
|
11 Replies
Sort By:
Posted 1 year ago
 Welcome to Wolfram Community! Please make sure you know the rules: https://wolfr.am/READ-1STThe 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] 
Posted 1 year ago
 Thanks Mr, sorry, I just see it.
Posted 1 year ago
 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.
Posted 11 months ago
 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.
Posted 11 months ago
 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} 
Posted 11 months ago
 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.
Posted 11 months ago
 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.
Posted 11 months ago
 Thanks for your very detailed solution, When I click on the url http://szhorvat.net/pelican/, 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
Posted 11 months ago
 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.