[Nauty-list] Custom pruning in genbg

[Brendan McKay]

Hi Stephen,

Thanks for reporting this.  You found a bug in the way PRUNE1 and PRUNE2
are called.  To fix it, change the argument deg to degx in all the calls
to PRUNE1 or PRUNE2 in the function accept2().  There are five cases.

To everyone: you didn't encounter this bug unless you used this unusual
feature of the program genbg, which is only possible by programming.
The program genbg as distributed is fine.

Regarding m:  it is always equal to 1 for genbg.c and also for geng.c.
This means that the total size of the graph can't get bigger than
WORDSIZE, which is either 32 or 64 in practice.

Brendan.

* Stephen Hartke <hartke at gmail.com> [110727 11:59]:
> I am resending this since the previous message was not approved to have
> attachments more than 40K.  I have attached a patch giving the custom
> pruning function I added to genbg.c---hopefully this will get through to the
> list.
> 
> Thanks for any help or insights!
> Stephen
> 
> ---------- Forwarded message ----------
> From: Stephen Hartke <hartke at gmail.com>
> Date: 2011/7/20
> Subject: Custom pruning in genbg
> To: nauty-list at cs.anu.edu.au
> 
> 
> genbg is a fantastic tool for investigating properties of hypergraphs!
> Thanks for creating it!
> 
> I have a question about the custom pruning in genbg.c:
> 
> I created a custom pruning function in genbg.c (modified code is attached)
> to print out information.  Unfortunately, it seems that the deg array does
> not contain the degrees of the vertices of the graph passed in in g; see
> attached output.  I tried the pruning function both as PRUNE1 and PRUNE2,
> and the difficulty arises in both cases.  Am I accessing this information
> incorrectly, or is there a bug?
> 
> Also, it was not clear to me how to calculate m for the passed in graph.
> The function writeg6x seems to suggest that m is always 1.  Is this the
> case?
> 
> Thanks for any help or insights!
> Stephen

> ./genbg 1 2 > output.txt
> >A ./genbg n=1+2 e=0:2 d=0:0 D=2:1
> >Z 3 graphs generated in 0.00 sec
> prune: n1=1, n2=1, maxn2=2, m=1
>   deg[0]=0, count=0, popcount=0
>   deg[1]=0, count=0, popcount=0
> prune: n1=1, n2=2, maxn2=2, m=1
>   deg[0]=0, count=0, popcount=0
>   deg[1]=0, count=0, popcount=0
>   deg[2]=3, count=0, popcount=0
> B?
> prune: n1=1, n2=2, maxn2=2, m=1
>   deg[0]=0, count=1, popcount=1
>   deg[1]=0, count=0, popcount=0
>   deg[2]=3, count=1, popcount=1
> BO
> prune: n1=1, n2=1, maxn2=2, m=1
>   deg[0]=1, count=1, popcount=1
>   deg[1]=1, count=1, popcount=1
> prune: n1=1, n2=2, maxn2=2, m=1
>   deg[0]=1, count=2, popcount=2
>   deg[1]=1, count=1, popcount=1
>   deg[2]=3, count=1, popcount=1
> Bo

> --- genbg.c	2009-11-03 20:30:11.000000000 -0600
> +++ ../nauty24r2-modified/genbg.c	2011-07-21 19:54:26.680280377 -0500
> @@ -139,6 +139,37 @@
>  #define ONE_WORD_SETS
>  #include "gtools.h"   /* which includes nauty.h and stdio.h */
>  
> +/*************************************************************************
> +**************************************************************************
> +  Custom pruning function
> +**************************************************************************
> +**************************************************************************/
> +#define PRUNE1 prune
> +int prune(graph *g, int *deg, int n1, int n2, int maxn2)
> +{
> +    int i,j,m,count;
> +    set *gi;
> +    
> +    m=(n1+maxn2+WORDSIZE-1)/WORDSIZE;  /* the number of setwords for each vertex (need to round up) */
> +	printf("prune: n1=%d, n2=%d, maxn2=%d, m=%d\n",n1,n2,maxn2,m);
> +	for (i=0; i<n1+n2; i++)
> +    {
> +        gi=GRAPHROW(g,i,m);
> +		count=0;
> +		for (j=0; j<n1+n2; j++)
> +			if (ISELEMENT(gi,j))
> +				count++;
> +        printf("  deg[%d]=%d, count=%d, popcount=%d\n",i,deg[i],count,POPCOUNT(*gi));
> +    }
> +    return 0;  /* do not prune */
> +}
> +/*************************************************************************
> +**************************************************************************
> +  End of custom pruning function
> +**************************************************************************
> +**************************************************************************/
> +
> +
>  static void (*outproc)(FILE*,graph*,int,int);
>  #ifdef OUTPROC
>  extern void OUTPROC(FILE*,graph*,int,int);

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list