[Nauty] generate all S-free graphs

[Sterten at aol.com]

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

yes, the 2-regular graph with 4 vertices is called "square" or C4.
And squarefree means, it doesn't contain a C4.
I saw this in some papers, so I assumed it's usual.
Your squarefree then means: squarefree+diamondfree+K4free

There are 8 graphs with n<8 which can be meaningful excluded:
C3,P3,C4,P4,K4,claw("Y"),paw(C3+e),diamond(K4-e).
I'd like to have a commandline switch for each of these in geng
(plus some graphs with n=5 ..) and then combine the switches.

 >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

..if speed is a problem. So far my testroutines consume so much time,that
the conversion-time is probably negligable.(except maybe squarefree,clawfree)
Also, I'm converting existing Basic-routines, which use the adjacency matrix.

For comparability graphs (transitively orientable) I had the
problem that the transitive orientation of the subgraph G-{n-1}
couldn't be reused.
For asteroidal triples I'll probably also have to test all vertices,
not only the last one.


 >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

just learned, that I can use PRUNE at gcc-commandline.
But I prefer a new gengisq.c, also adapting HELPTEXT and some
more output, see below.
-O2 works a little better for me.

 >*/
 >
 >#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.

yes, that was easy. Just add 3 letters to gengisq.c !
2.69s now for isqfree,n=10 (instead of 11s) .

I'll try PREPRUNE for some other examples.

However all these factors are not worth a lot, since
graphnumbers and timings often rise very rapidly with growing n.
So it would be useful to estimate the numbers without counting them all.
I make a vector of probabilities p(1),..,p(n)
and replace "return(0);" by :
"if(rnd<p(n))return(0);cosu[n]++;return(1);"
from the values of cosu[] I can later calculate an estimate
of the numbers of graphs and the running time to
generate/count them. Or I can generate random graphs with certain properties.
Usually p(i)=const. but sometimes I need other values.
I'd like to include this in geng with a new commandline-parameter
and entering p(i)=p=const. or reading the p(i) from a file.


Guenter.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20021124/8b82457b/attachment.html