Page MenuHomePhorge
Files F27033137

vcolg.c
No OneTemporary
Actions

Authored By
Unknown
Size
12 KB
Referenced Files
None
Subscribers
None

vcolg.c
View Options

/* vcolg.c version 1.0; B D McKay, Aug 31, 2013 */
#define USAGE \
"vcolg [-q] [-u|-T|-G|-A|-B] [-e#|-e#:#] \n" \
" [-m#] [-f#] [-D#|-r#|-l#] [infile [outfile]]"
#define HELPTEXT \
" Read undirected loop-free graphs and colour their vertices in\n\
in all possible ways with colours 0,1,2,... .\n\
Isomorphic graphs derived from the same input are suppressed.\n\
If the input graphs are non-isomorphic then the output graphs are also.\n\
\n\
-e# | -e#:# specify a value or range of the total value of the colours\n\
-m# number of available colours (default 2)\n\
-f# Use the group that fixes the first # vertices setwise\n\
-T use a simple text output format (nv ne {col} {v1 v2})\n\
-u no output, just count them\n\
-q suppress auxiliary information\n"
/*************************************************************************/
#include "gtools.h"
#include "naugroup.h"
nauty_counter vc_nin,vc_nout;
FILE *outfile;
#define MAXNV 128
#define MAXNE 1024
static int col[MAXNV];
static boolean first;
static int lastreject[MAXNV];
static boolean lastrejok;
static unsigned long groupsize;
static unsigned long newgroupsize;
static boolean Tswitch;
static int fail_level;
#define GROUPTEST_NOT
#ifdef GROUPTEST
static long long totallab;
#endif
/* If OUTPROC is defined at compile time, and -u is not used, the
* procedure OUTPROC is called for each graph. This must be linked
* by the compiler. The arguments are
* f = open output file
* g = the input graph
* col[0..n-1] = the colours
* m,n = usual nauty meanings
*/
/* SUMMARY feature
*
* If SUMMARY is defined, it must expand as the name of a procedure
* with prototype void SUMMARY(void). It is called at the end before
* the normal summary (which can be suppressed with -q). The numbers of
* graphs read and coloured graphs produced are available in the global
* variables vc_nin and vc_nout (type nauty_counter).
*/
#ifdef OUTPROC
extern void OUTPROC(FILE*,graph*,int*,int,int);
#endif
#ifdef SUMMARY
extern void SUMMARY(void);
#endif
/**************************************************************************/
static void
writeautom(int *p, int n)
/* Called by allgroup. */
{
int i;
for (i = 0; i < n; ++i) printf(" %2d",p[i]);
printf("\n");
}
/**************************************************************************/
static int
ismax(int *p, int n)
/* test if col^p <= col */
{
int i,k;
int fail;
fail = 0;
for (i = 0; i < n; ++i)
{
k = p[i];
if (k > fail) fail = k;
if (col[k] > col[i])
{
fail_level = fail;
return FALSE;
}
else if (col[k] < col[i]) return TRUE;
}
++newgroupsize;
return TRUE;
}
/**************************************************************************/
static void
testmax(int *p, int n, int *abort)
/* Called by allgroup2. */
{
int i;
if (first)
{ /* only the identity */
first = FALSE;
return;
}
if (!ismax(p,n))
{
*abort = 1;
for (i = 0; i < n; ++i) lastreject[i] = p[i];
lastrejok = TRUE;
}
}
/**************************************************************************/
static int
trythisone(grouprec *group, graph *g, int m, int n)
/* Try one solution, accept if maximal. */
/* Return value is level to return to. */
{
int i,j;
boolean accept;
graph *gi;
size_t ne;
newgroupsize = 1;
if (!group || groupsize == 1)
accept = TRUE;
else if (lastrejok && !ismax(lastreject,n))
accept = FALSE;
else if (lastrejok && groupsize == 2)
accept = TRUE;
else
{
newgroupsize = 1;
first = TRUE;
if (allgroup2(group,testmax) == 0)
accept = TRUE;
else
accept = FALSE;
}
if (accept)
{
#ifdef GROUPTEST
if (groupsize % newgroupsize != 0)
gt_abort("group size error\n");
totallab += groupsize/newgroupsize;
#endif
++vc_nout;
if (outfile)
{
#ifdef OUTPROC
OUTPROC(outfile,g,col,m,n);
#else
ne = 0;
for (gi = g + m*(size_t)n; --gi >= g; )
ne += POPCOUNT(*gi);
ne /= 2;
fprintf(outfile,"%d %lu",n,(unsigned long)ne);
for (i = 0; i < n; ++i) fprintf(outfile," %d",col[i]);
fprintf(outfile," ");
for (i = 0, gi = g; i < n; ++i, gi += m)
{
for (j = i; (j = nextelement(gi,m,j)) >= 0; )
fprintf(outfile," %d %d",i,j);
}
fprintf(outfile,"\n");
#endif
}
return n-1;
}
else
return fail_level-1;
}
/**************************************************************************/
static int
scan(int level, graph *g, int *prev, long minedges, long maxedges,
long sofar, long numcols, grouprec *group, int m, int n)
/* Recursive scan for default case */
/* Returned value is level to return to. */
{
int left;
long min,max,k,ret;
if (level == n)
return trythisone(group,g,m,n);
left = n - level - 1;
min = minedges - sofar - numcols*left;
if (min < 0) min = 0;
max = maxedges - sofar;
if (max >= numcols) max = numcols - 1;
if (prev[level] >= 0 && col[prev[level]] < max)
max = col[prev[level]];
for (k = min; k <= max; ++k)
{
col[level] = k;
ret = scan(level+1,g,prev,minedges,maxedges,sofar+k,numcols,group,m,n);
if (ret < level) return ret;
}
return level-1;
}
/**************************************************************************/
#define SORT_OF_SORT 3
#define SORT_NAME sortwt
#define SORT_TYPE1 int
#define SORT_TYPE2 int
#include "sorttemplates.c"
static void
setlab(int *weight, int *lab, int *ptn, int n)
/* Define (lab,ptn) according to weights. */
{
int i;
for (i = 0; i < n; ++i) lab[i] = i;
sortwt(lab,weight,n);
for (i = 0; i < n-1; ++i)
{
if (weight[lab[i]] != weight[lab[i+1]])
ptn[i] = 0;
else
ptn[i] = 1;
}
ptn[n-1] = 0;
}
/**************************************************************************/
static void
colourit(graph *g, int nfixed, long minedges, long maxedges,
long numcols, int m, int n)
{
static DEFAULTOPTIONS_GRAPH(options);
statsblk stats;
setword workspace[100];
grouprec *group;
int i,j,k;
set *gi,*gj;
int lab[MAXNV],ptn[MAXNV],orbits[MAXNV],deg[MAXNV];
int prev[MAXNV]; /* If >= 0, earlier point that must have greater colour */
int weight[MAXNV];
int last0,lastn,thisdeg,region,start,stop;
if (n > MAXNV) gt_abort(">E vcolg: MAXNV exceeded\n");
nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
for (region = 0; region < 2; ++region)
{
if (region == 0)
{
if (nfixed == 0) continue;
start = 0;
stop = nfixed;
if (stop > n) stop = n;
}
else
{
if (nfixed >= n) continue;
start = nfixed;
stop = n;
}
for (i = start, gi = g + m*(size_t)start; i < stop; ++i, gi += m)
{
for (j = i-1, gj = gi-m; j >= start; --j, gj -= m)
{
for (k = 0; k < m; ++k) if (gi[k] != gj[k]) break;
if (k < m)
{
FLIPELEMENT(gi,i); FLIPELEMENT(gj,j);
for (k = 0; k < m; ++k) if (gi[k] != gj[k]) break;
FLIPELEMENT(gi,i); FLIPELEMENT(gj,j);
}
if (k == m) break;
}
if (j >= start)
{
prev[i] = j;
weight[i] = weight[j] + 1;
}
else
{
prev[i] = -1;
weight[i] = 0;
}
}
}
for (i = nfixed; i < n; ++i) weight[i] += nfixed;
if (maxedges == NOLIMIT || maxedges > n*numcols) maxedges = n*numcols;
if (n*numcols < minedges) return;
options.userautomproc = groupautomproc;
options.userlevelproc = grouplevelproc;
options.defaultptn = FALSE;
setlab(weight,lab,ptn,n);
nauty(g,lab,ptn,NULL,orbits,&options,&stats,workspace,100,m,n,NULL);
if (stats.grpsize2 == 0)
groupsize = stats.grpsize1 + 0.1;
else
groupsize = 0;
group = groupptr(FALSE);
makecosetreps(group);
if (stats.numorbits < n)
{
j = n;
for (i = 0; i < n; ++i)
if (orbits[i] < i && orbits[i] < j) j = orbits[i];
for (i = j + 1; i < n; ++i)
if (orbits[i] == j) prev[i] = j;
}
lastrejok = FALSE;
for (i = 0; i < n; ++i) col[i] = 0;
scan(0,g,prev,minedges,maxedges,0,numcols,group,m,n);
}
/**************************************************************************/
int
main(int argc, char *argv[])
{
graph *g;
int i,m,n,codetype;
int argnum,j,nfixed;
char *arg,sw;
boolean badargs;
boolean fswitch,uswitch,eswitch,qswitch,mswitch;
long minedges,maxedges,numcols;
double t;
char *infilename,*outfilename;
FILE *infile;
char msg[201];
int msglen;
HELP; PUTVERSION;
nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);
fswitch = Tswitch = FALSE;
uswitch = eswitch = mswitch = qswitch = FALSE;
infilename = outfilename = NULL;
argnum = 0;
badargs = FALSE;
for (j = 1; !badargs && j < argc; ++j)
{
arg = argv[j];
if (arg[0] == '-' && arg[1] != '\0')
{
++arg;
while (*arg != '\0')
{
sw = *arg++;
SWLONG('m',mswitch,numcols,"vcolg -m")
else SWBOOLEAN('q',qswitch)
else SWBOOLEAN('u',uswitch)
else SWBOOLEAN('T',Tswitch)
else SWINT('f',fswitch,nfixed,"vcolg -f")
else SWRANGE('e',":-",eswitch,minedges,maxedges,"vcolg -e")
else badargs = TRUE;
}
}
else
{
++argnum;
if (argnum == 1) infilename = arg;
else if (argnum == 2) outfilename = arg;
else badargs = TRUE;
}
}
if (badargs || argnum > 2)
{
fprintf(stderr,">E Usage: %s\n",USAGE);
GETHELP;
exit(1);
}
if ((Tswitch!=0) + (uswitch!=0) >= 2)
gt_abort(">E vcolg: -T and -u are incompatible\n");
#ifndef OUTPROC
if (!Tswitch && !uswitch)
gt_abort(">E vcolg: must use -T or -u\n");
#endif
if (!mswitch) numcols = 2;
if (!eswitch)
{
minedges = 0;
maxedges = NOLIMIT;
}
if (!fswitch) nfixed = 0;
if (!qswitch)
{
msg[0] = '\0';
CATMSG0(">A vcolg");
if (eswitch || mswitch || uswitch || (fswitch && nfixed > 0)
|| Tswitch)
CATMSG0(" -");
if (mswitch) CATMSG1("m%ld",numcols);
if (uswitch) CATMSG0("u");
if (Tswitch) CATMSG0("T");
if (fswitch) CATMSG1("f%d",nfixed);
if (eswitch) CATMSG2("e%ld:%ld",minedges,maxedges);
msglen = strlen(msg);
if (argnum > 0) msglen += strlen(infilename);
if (argnum > 1) msglen += strlen(outfilename);
if (msglen >= 196)
{
fputs(msg,stderr);
if (argnum > 0) fprintf(stderr," %s",infilename);
if (argnum > 1) fprintf(stderr," %s",outfilename);
fprintf(stderr,"\n");
}
else
{
if (argnum > 0) CATMSG1(" %s",infilename);
if (argnum > 1) CATMSG1(" %s",outfilename);
CATMSG0("\n");
fputs(msg,stderr);
}
fflush(stderr);
}
if (infilename && infilename[0] == '-') infilename = NULL;
infile = opengraphfile(infilename,&codetype,FALSE,1);
if (!infile) exit(1);
if (!infilename) infilename = "stdin";
NODIGRAPHSYET(codetype);
if (uswitch)
outfile = NULL;
else
{
if (!outfilename || outfilename[0] == '-')
{
outfilename = "stdout";
outfile = stdout;
}
else if ((outfile = fopen(outfilename,"w")) == NULL)
{
fprintf(stderr,"Can't open output file %s\n",outfilename);
gt_abort(NULL);
}
}
vc_nin = vc_nout = 0;
t = CPUTIME;
while (TRUE)
{
if ((g = readg(infile,NULL,0,&m,&n)) == NULL) break;
++vc_nin;
colourit(g,nfixed,minedges,maxedges,numcols,m,n);
if (!uswitch && ferror(outfile))
gt_abort(">E vcolg output error\n");
FREES(g);
}
t = CPUTIME - t;
#ifdef SUMMARY
SUMMARY();
#endif
if (!qswitch)
{
fprintf(stderr,">Z ");
PRINT_COUNTER(stderr,vc_nin);
fprintf(stderr," graphs read from %s",infilename);
fprintf(stderr,"; ");
PRINT_COUNTER(stderr,vc_nout);
if (!uswitch)
fprintf(stderr," coloured graphs written to %s",outfilename);
else
fprintf(stderr," coloured graphs generated");
fprintf(stderr,"; %.2f sec\n",t);
}
#ifdef GROUPTEST
fprintf(stderr,"Group test = %lld\n",totallab);
#endif
exit(0);
}

File Metadata

Mime Type
text/x-c
Expires
Tue, Oct 27, 3:46 PM (1 d, 11 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
406885
Default Alt Text
vcolg.c (12 KB)

Event Timeline