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

[Brendan McKay]

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