[Nauty] Efficient workflow for filtering when using a transformation and pickg

[Stephen Hartke]

Hi Brendan,

Perfect!  This is exactly what I need.  I did not know about the FILTER
functionality in copyg.  I had been trying to modify pickg, which is much
more complicated.  This also is made easier by the fact that the nauty
library already implements most of the functionality I need (chromatic
number, cliquer, planarity) and I write my own code for the (relatively
simple) transformations.  I don't need to call other programs.

Thanks!
Stephen


On Fri, May 16, 2025 at 11:15 PM Brendan McKay via Nauty <nauty at anu.edu.au>
wrote:

> Hi Stephen,
>
> Sometimes the only way to do something efficiently is to write some code.
>
> In this case, I would use the FILTER facility of the copyg program.
> It is described in the section "How to use this as a skeleton to
> construct a filter." in copyg.c.
>
> The filter will construct the square and compute its chromatic number
> by calling the function chromaticnumber(), which is defined at the
> start of the file nauchromatic.c.  Then it will return TRUE or FALSE
> depending on whether you want to keep the graph or not.
>
> Brendan.
>
>
> On 17/5/2025 8:59 am, Stephen Hartke via Nauty wrote:
> > Hello everyone,
> >
> > I have been using the wonderful nauty library and its included generating
> > and filtering programs for many years now.  The recent(-ish) inclusion of
> > the chromatic number in pickg has been especially useful.
> >
> > I have a question about workflow using these tools.  I'm hoping that
> > members of this mailing list might have insights into how to make my
> > workflow more efficient.
> >
> > I have recently been studying variants of graph coloring that can be
> > modeled by standard vertex coloring on a transformed graph.  An example
> is
> > "square coloring", which is just vertex coloring the square of a graph
> > (here, the square of G is a graph H with the same vertex set as G, and
> > vertices of H are adjacent if and only the vertices have distance at
> most 2
> > in G).  When generating data, I usually:
> > 1) Use geng or another tool to generate graphs in an appropriate family,
> > for example, triangle-free graphs of max degree 4.
> > 2) Apply the transformation, for example, the square of the graph.
> > 3) Use pickg to filter out graphs with given values, say chromatic number
> > at least 10.  This corresponds to the original graph having square
> > chromatic number at least 10.
> >
> > The problem with this approach is that I want to have the actual graphs
> > with the high square chromatic number, not their transformation.  In many
> > cases, it is not easy to invert the transformation.
> >
> > I have gotten around this problem by using a bash script to apply the
> > transformation and pickg individually to each graph coming out of the
> > generation step.  The bash script knows the original graph and can output
> > it if pickg (or countg) accepts the transformed graph.
> >
> > The difficulty with this approach is there are separate invocations for
> > each individual graph, and this generates a lot of overhead.  Is there a
> > smarter way to go about this, using the capability to pipe streams of
> > graphs between the tools?  It seems that a custom transformation could be
> > implemented within pickg (I currently have it implemented in a standalone
> > program), but it seems the output would still be the transformation, not
> > the original graph.
> >
> > Thanks for any suggestions!
> > Stephen Hartke
> > University of Colorado Denver, USA
> > _______________________________________________
> > Nauty mailing list
> > Nauty at anu.edu.au
> > https://mailman.anu.edu.au/mailman/listinfo/nauty
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty
>