2
$\begingroup$

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 ...

$\endgroup$
3
  • 1
    $\begingroup$ Not sure if it will help but you might want to check this fairly recent article on graph symmetry breaking. $\endgroup$ Nov 24, 2019 at 17:18
  • 2
    $\begingroup$ @DanielLichtblau geng from 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 of Graph expressions (which is pretty slow...) $\endgroup$
    – Szabolcs
    Dec 11, 2019 at 13:05
  • $\begingroup$ @DanielLichtblau By the way Daniel, FindVertexCut is broken, the developers are aware of it. Hopefully this gets fixed fast, it is a fundamental function, and the only way to test connectivity right now in Mathematica. $\endgroup$
    – EGME
    Dec 11, 2019 at 13:09

1 Answer 1

3
$\begingroup$

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"]

enter image description here

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).

$\endgroup$
8
  • $\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$
    – EGME
    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$
    – Szabolcs
    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$
    – EGME
    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$
    – EGME
    Dec 11, 2019 at 16:48
  • $\begingroup$ @EGME I am not sure. geng is 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 stop geng from 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$
    – Szabolcs
    Dec 11, 2019 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.