Is it possible to generate all non isomorphic graphs of given order (small) and size with Mathematica (and IGraph?)? I don’t immediately see how to do that, and if this is not possible without complicated programming and use of IGIsomorphicQ, this would be a nice to have, especially if additional constraints can be chosen, such as connectivity, min-degree, etc. There are in general too many non isomorphic graphs to list them all, even for small orders, but being able to list them all when additional restrictions are given is very desirable ...
3
1 Answer
$\begingroup$
$\endgroup$
8
The nauty tool includes the program geng which can generate all non-isomorphic graphs with various constraints (including on the number of vertices, edges, connectivity, biconnectivity, triangle-free and others). Its output is in the Graph6 format, which Mathematica can import.
For example, assuming you have geng installed in /opt/local/bin,
Import["!/opt/local/bin/geng 4", "Graph6"]
There are typically a very large number of results, and geng is likely the fastest tool for the exhaustive generation of non-isomorphic graphs. The bottleneck when using it with Mathematica is not geng itself, but Mathematica's importer.
The next (yet unreleased) version of IGraph/M will include a faster Graph6 importer than Mathematica's built-in, as well as a Digraph6 importer for directed graphs (not currently supported by Mathematica).
In[9]:= Import["!/opt/local/bin/geng 8", "Graph6"]; // AbsoluteTiming
Out[9]= {3.17038, Null}
In[10]:= IGImport["!/opt/local/bin/geng 8", "Graph6"]; // AbsoluteTiming
Out[10]= {0.853189, Null}
I considered integrating geng into IGraph/M, but there would be little benefit compared to calling geng as a separate process. Converting to Mathematica's graph format would be just as slow as with IGImport. Thus I decided to focus on a fast and flexible Graph6/Sparse6/Digraph6 importer instead. Many graph theory tools use these formats, so it is very useful to be able to handle them well (better than Mathematica currently can).
answered Dec 11, 2019 at 12:58
-
$\begingroup$ Thanks! Looking forward to these developments. Is there anything in the works to extend matchings to a maximum matching? Getting them one by one starting from an arbitrary one in lex order ... Connectivity? Perhaps the wrong place to ask, but how can I post about what is not there? $\endgroup$– EGMECommented Dec 11, 2019 at 13:15
-
$\begingroup$ @EGME For IGraph/M specifically, there is gitter.im/IGraphM/Lobby For igraph more generally, there's the mailing list: lists.nongnu.org/mailman/listinfo/igraph-help We plan to launch a modern support forum early next year. $\endgroup$– SzabolcsCommented Dec 11, 2019 at 13:17
-
$\begingroup$ Thanks! I have a long wish list ... indeed there is much room for new and improved functionality, wherever it comes from ... $\endgroup$– EGMECommented Dec 11, 2019 at 13:20
-
$\begingroup$ When you get already to order 10, there are millions of non isomorphic graphs. Is it possible to get them with geng one by one, from say, a certain index, in the order they are given, to another one? As in many of my problems, I need to avoid cramming memory ... but I can afford to check things one by one, in phases .... check the post for NextKSizePartition ... $\endgroup$– EGMECommented Dec 11, 2019 at 16:48
-
$\begingroup$ @EGME I am not sure.
gengis a command line program that writes to the standard output. Its output can be pipes to another process (common with the nauty tools, actually) and it can also be read incrementally. It is possible to read the graphs one by one with Mathematica. However, I do not think that doing this will stopgengfrom going on with the graph generation in the background. I am also not sure where the OS stores all that intermediate piped data (in memory or on disk). $\endgroup$– SzabolcsCommented Dec 11, 2019 at 18:29
gengfrom the nauty suite can handle this problem very well. The only issue is that Mathematica's Graph6 importer is not as good as it could be (despite years of asking for improvements). The next version of IGraph/M will have a better/faster Graph6 importer, but unfortunately it will still be limited by the construction speed ofGraphexpressions (which is pretty slow...) $\endgroup$