Message Boards

WOLFRAM COMMUNITY

8934 Views

12 Replies

5 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Import a downloaded Cactus Graph program from a web?

Licheng Zhang

Posted 5 years ago

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: CactusGraph (1).nb

POSTED BY: Licheng Zhang

12 Replies

Sort By:

Szabolcs Horvát

Posted 4 years ago

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

POSTED BY: Szabolcs Horvát

Szabolcs Horvát

Posted 5 years 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 BY: Szabolcs Horvát

Szabolcs Horvát

Posted 5 years 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.

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

Szabolcs Horvát

Posted 5 years 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 BY: Szabolcs Horvát

Moderation Team

Moderation Team, WOLFRAM

Posted 5 years ago

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]

POSTED BY: Moderation Team

Licheng Zhang

Posted 5 years ago

Thanks Mr, sorry, I just see it.

POSTED BY: Licheng Zhang

Licheng Zhang

Posted 5 years 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 BY: Licheng Zhang

Szabolcs Horvát

Posted 5 years 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 BY: Szabolcs Horvát

Licheng Zhang

Posted 5 years 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 BY: Licheng Zhang

Szabolcs Horvát

Posted 5 years 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.

POSTED BY: Szabolcs Horvát

Licheng Zhang

Posted 4 years ago

I am very excited about the update of IGraph you told me. It is very well!

POSTED BY: Licheng Zhang

Licheng Zhang

Posted 2 years ago

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.

POSTED BY: Licheng Zhang

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Group Abstract

Feedback