Message Boards Message Boards

GROUPS:

Import a downloaded Cactus Graph program from a web?

Posted 4 months ago
640 Views
|
9 Replies
|
3 Total Likes
|

Hellow everyone I downloaded a notebook about Cactus Graph downloaded from <a href="http://mathworld.wolfram.com/CactusGraph.html.*">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

Attachments:
9 Replies

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]

enter image description here

Posted 1 month ago

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.

Posted 1 month 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.

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}

enter image description here

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.

Posted 1 month 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

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.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract