[Nauty] generate all S-free graphs

Brendan McKay bdm at cs.anu.edu.au
Sat Nov 23 20:39:01 EST 2002


* Sterten at aol.com <Sterten at aol.com> [021123 03:50]:
> squarefree:  1,2,4,10,28,100, 441, 2574, 19849,  201682   (12s)

"squarefree" usually means "without 4-cycles" which is implemented
by the "-f" switch on geng, but I see from your code that you mean
"without induced 4-cycles".
 
> int square(graph *g,int n,int maxn) {
> int a[n+1][n+1],e[n+1][n+1],d[n+1];
> long int m=1;int i,j,k,u,v,w,x,y,z;set *gi;
> 
> for(i=0,gi=(set*)g;i<n;++i,gi+=m)for(j=0;j<n;++j)a[n-i][n-j]=ISELEMENT(gi,j);
> 
> for(i=1;i<=n;i++)d[i]=0;
> for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i][j]>0){d[i]++;e[i][d[i]]=j;}
> 
>    for(x=1;x<=d[1];x++) {v=e[1][x];
>      for(y=x+1;y<=d[1];y++) {w=e[1][y];
>        if(a[v][w]<1)
>          for(z=1;z<=d[v];z++) {u=e[v][z];
>            if(a[w][u]>0 && a[1][u]<1 && u>1)return(1);}
>    } } 
> return(0);}

It's a good idea to get used to using the native format rather than
converting to a different format before testing.  Here is the same
effect using the nauty format directly.  It looks for an induced
4-cycle (n-1)-w-v-*-(n-1), where all values for "*" are examined
at once.

/* File to remove graphs for which there is an induced 4-cycle.
Compile as 
    cc -o isqfree -O4 -DPRUNE=isqfree -DMAXN=16 geng.c isqfree.c \
        gtools.o nauty1.o nautil1.o naugraph1.o
*/

#include "nauty.h"

int
isqfree(graph *g, int n, int maxn)
/* Return 0 if there is no induced 4-cycle involving vertex n-1,
   1 if there is. */
{
    setword common;
    int v,w;

    for (v = n-1; --v >= 0;)         /* for v not */
    if ((g[n-1] & bit[v]) == 0)    /* adjacent to n-1 */
    {
        common = g[n-1] & g[v];   /* common neighbours */

        while (common)
        {
            TAKEBIT(w,common);     /* for each w in common */
            if (common & ~g[w]) return 1;  /* if "*" exists */
        }
    }
    return 0;
}

This code assumes MAXN<=WORDSIZE, but that is always true for geng.c.

Note that instead of PRUNE you can use PREPRUNE.  This puts the filter
into a place in the generator before isomorphism pruning has been done.
This is good for very fast tests that eliminate many graphs, as then
the reduced amount of isomorphism pruning more than pays for the
additional calls to the filter.  In this example, using PREPRUNE
gains a factor of 2 in the running time.

Brendan.




More information about the Nauty mailing list