Seeking to support the graph6 format.

[lichengzhang1]

Nauty's geng is a tool for generating graphs, but currently it does not support checking whether there exist (induced) subgraphs, Its encoding is mainly in the graph6 format. Can these two software packages be used together? I feel that the key is to support the graph6 format.

One approach is to use showgfor adjacency lists, but there are still significant differences in the supported formats compared to glasgow-subgraph-solver.

geng 4 3|showg

Graph 1, order 4.
  0 : 3;
  1 : 3;
  2 : 3;
  3 : 0 1 2;

Graph 2, order 4.
  0 : 2 3;
  1 : 3;
  2 : 0;
  3 : 0 1;

Graph 3, order 4.
  0 : 2 3;
  1 : ;
  2 : 0 3;
  3 : 0 2;

For example, I want to select all 8-vertex connected graphs containing at least one induced cycles of length 5.

geng 8 -c can generate connected graphs with 8 vertices, but how to continue? There is a potential of this software, but the current obstacle is in the support of formats.

[ciaranm]

There are a couple of options. The easiest is to add support for the graph6 format: have a look at the gss/formats directory. I'm travelling for the next couple of weeks but I can probably do this quickly when I'm back, if you don't get there first.

A better but harder solution would be to use the solver as a library, and write a small client program. This will save you the overheads of having to write everything to file and parse it. Particularly for small graphs, most of the time will be spent starting up the program and converting all the graph formats, rather than doing subgraph matching.