Page MenuHomePhorge
Files F27036885

delptg.c
No OneTemporary
Actions

Authored By
Unknown
Size
6 KB
Referenced Files
None
Subscribers
None

delptg.c
View Options

/* delptg.c version 2.0; B D McKay, Jul 2015. */
#define USAGE "delptg [-lq] [-d#|d#:#] [-n#] [infile [outfile]]"
#define HELPTEXT \
" Delete some vertices from a file of graphs.\n\
\n\
The output file has a header if and only if the input file does.\n\
No isomorph reduction is done.\n\
\n\
-l Canonically label outputs\n\
-d# -d#:# Only remove vertices with original degree in the given range\n\
For digraphs, the out-degree is used.\n\
-n# The number of vertices to delete (default 1).\n\
Inputs that are too small are ignored; no empty graphs are output.\n\
-q Suppress auxiliary information\n"
/*************************************************************************/
#include "gtools.h"
static FILE *outfile;
static nauty_counter nout;
static int outcode;
static boolean digraph,dolabel;
/**************************************************************************/
static void
writeone(graph *g, int m, int n, int *del, int ndel)
/* Delete the stated vertices and write */
{
int i,j,k,nx,mx;
graph *gi,*gxi,*gq;
#if MAXN
graph gx[MAXN*MAXM];
graph hx[MAXN*MAXM];
int lab[MAXN];
#else
DYNALLSTAT(graph,gx,gx_sz);
DYNALLSTAT(graph,hx,hx_sz);
DYNALLSTAT(int,lab,lab_sz);
#endif
nx = n - ndel; /* Always positive */
mx = SETWORDSNEEDED(nx);
#if !MAXN
DYNALLOC2(graph,gx,gx_sz,mx,nx,"delptg");
if (dolabel) DYNALLOC2(graph,hx,hx_sz,mx,nx,"delptg");
DYNALLOC1(int,lab,lab_sz,nx,"delptg");
#endif
j = 0;
for (i = 0; i < del[0]; ++i) lab[j++] = i;
for (k = 1; k < ndel; ++k)
for (i = del[k-1]+1; i < del[k]; ++i) lab[j++] = i;
for (i = del[ndel-1]+1; i < n; ++i) lab[j++] = i;
EMPTYSET(gx,nx*(size_t)mx);
for (i = 0, gxi = (set*)gx; i < nx; ++i, gxi += mx)
{
gi = GRAPHROW(g,lab[i],m);
for (j = 0; j < nx; ++j)
{
k = lab[j];
if (ISELEMENT(gi,k)) ADDELEMENT(gxi,j);
}
}
if (dolabel)
{
fcanonise(gx,mx,nx,hx,NULL,digraph);
gq = hx;
}
else
gq = gx;
if (outcode == DIGRAPH6 || digraph) writed6(outfile,gq,mx,nx);
else if (outcode == SPARSE6) writes6(outfile,gq,mx,nx);
else writeg6(outfile,gq,mx,nx);
++nout;
}
/**************************************************************************/
static void
search(int level, int ndel, int *del, graph *g, int m, int n, boolean *degok)
{
int i;
if (level == ndel)
{
writeone(g,m,n,del,ndel);
return;
}
for (i = (level == 0 ? 0 : del[level-1]+1); i <= n-ndel+level; ++i)
if (degok[i])
{
del[level] = i;
search(level+1,ndel,del,g,m,n,degok);
}
}
/**************************************************************************/
int
main(int argc, char *argv[])
{
char *infilename,*outfilename;
FILE *infile;
boolean badargs,quiet,dswitch,nswitch;
int i,j,m,n,v,argnum;
int ndel;
int codetype;
graph *g;
nauty_counter nin;
char *arg,sw;
setword *gv;
long mindeg,maxdeg;
int degv;
double t;
#if MAXN
boolean degok[MAXN];
boolean del[MAXN];
#else
DYNALLSTAT(boolean,degok,degok_sz);
DYNALLSTAT(boolean,del,del_sz);
#endif
HELP; PUTVERSION;
infilename = outfilename = NULL;
badargs = FALSE;
dswitch = nswitch = quiet = FALSE;
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++;
SWBOOLEAN('l',dolabel)
else SWBOOLEAN('q',quiet)
else SWINT('n',nswitch,ndel,">E delptg -n")
else SWRANGE('d',":-",dswitch,mindeg,maxdeg,">E delptg -d")
else badargs = TRUE;
}
}
else
{
++argnum;
if (argnum == 1) infilename = arg;
else if (argnum == 2) outfilename = arg;
else badargs = TRUE;
}
}
if (nswitch && ndel < 1) gt_abort(">E delptg: bad argument for -n\n");
if (badargs)
{
fprintf(stderr,">E Usage: %s\n",USAGE);
GETHELP;
exit(1);
}
if (!quiet)
{
fprintf(stderr,">A delptg");
if (dolabel) fprintf(stderr," -l");
if (dswitch) fprintf(stderr," -d%ld:%ld",mindeg,maxdeg);
if (nswitch) fprintf(stderr," -n%d",ndel);
if (argnum > 0) fprintf(stderr," %s",infilename);
if (argnum > 1) fprintf(stderr," %s",outfilename);
fprintf(stderr,"\n");
fflush(stderr);
}
if (!dswitch)
{
mindeg = 0;
maxdeg = NAUTY_INFINITY;
}
if (!nswitch) ndel = 1;
if (dolabel) nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);
nin = nout = 0;
if (infilename && infilename[0] == '-') infilename = NULL;
infile = opengraphfile(infilename,&codetype,FALSE,1);
if (!infile) exit(1);
if (!infilename) infilename = "stdin";
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);
}
if (codetype&SPARSE6) outcode = SPARSE6;
else if (codetype&DIGRAPH6) outcode = DIGRAPH6;
else outcode = GRAPH6;
if (codetype&HAS_HEADER)
{
if (outcode == SPARSE6) writeline(outfile,SPARSE6_HEADER);
else if (outcode == DIGRAPH6) writeline(outfile,DIGRAPH6_HEADER);
else writeline(outfile,GRAPH6_HEADER);
}
t = CPUTIME;
while (TRUE)
{
if ((g = readgg(infile,NULL,0,&m,&n,&digraph)) == NULL) break;
++nin;
if (n <= ndel)
{
FREES(g);
continue;
}
#if !MAXN
DYNALLOC1(boolean,degok,degok_sz,n,"delptg");
DYNALLOC1(int,del,del_sz,n,"delptg");
#endif
for (v = 0, gv = g; v < n; ++v, gv += m)
{
degv = 0;
for (i = 0; i < m; ++i)
degv += POPCOUNT(gv[i]);
degok[v] = (degv >= mindeg) && (degv <= maxdeg);
}
search(0,ndel,del,g,m,n,degok);
FREES(g);
}
t = CPUTIME - t;
if (!quiet)
fprintf(stderr,
">Z " COUNTER_FMT " graphs read from %s, "
COUNTER_FMT " written to %s; %3.2f sec.\n",
nin,infilename,nout,outfilename,t);
exit(0);
}

File Metadata

Mime Type
text/x-c
Expires
Tue, Oct 27, 8:16 PM (1 d, 14 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
406520
Default Alt Text
delptg.c (6 KB)

Event Timeline