biplabg.c

/* biplabg.c  version 1.1; B D McKay, Nov 10, 2009. */

#define USAGE "biplabg [-q] [infile [outfile]]"

#define HELPTEXT \
" Label bipartite graphs so that the colour classes are contiguous.\n\
  The first vertex of each component is assigned the first colour.\n\
  Vertices in each colour class have the same relative order as before.\n\
  Non-bipartite graphs are rejected.\n\
\n\
    The output file has a header if and only if the input file does.\n\
\n\
    -q  Suppress auxiliary information.\n"

/*************************************************************************/

#include "gtools.h" 
#include "gutils.h"

/**************************************************************************/

static boolean
biplabel(graph *g, int m, int n, graph *h)
/* h := bipartite labelling of g; else return FALSE */
{
	int i,j;
#if MAXN
	int colour[MAXN];
	int lab[MAXN];
#else
	DYNALLSTAT(int,colour,colour_sz);
	DYNALLSTAT(int,lab,lab_sz);

	DYNALLOC1(int,colour,colour_sz,n,"biplabg");
	DYNALLOC1(int,lab,lab_sz,n,"biplabg");
#endif

	if (!twocolouring(g,colour,m,n)) return FALSE;

	j = 0;
	for (i = 0; i < n; ++i) if (colour[i] == 0) lab[j++] = i;
	for (i = 0; i < n; ++i) if (colour[i] == 1) lab[j++] = i;

	updatecan(g,h,lab,0,m,n);

	return TRUE;
}

/**************************************************************************/

int
main(int argc, char *argv[])
{
        char *infilename,*outfilename;
        FILE *infile,*outfile;
        boolean badargs,quiet;
	int j,m,n,argnum;
	int codetype,outcode;
	graph *g;
	nauty_counter nin,nout;
        char *arg,sw;
	double t;
#if MAXN
	graph h[MAXN*MAXM];
#else
	DYNALLSTAT(graph,h,h_sz);
#endif

	HELP; PUTVERSION;

        infilename = outfilename = NULL;
	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('q',quiet)
		    else badargs = TRUE;
		}
	    }
	    else
	    {
		++argnum;
		if      (argnum == 1) infilename = arg;
	        else if (argnum == 2) outfilename = arg;
		else                  badargs = TRUE;
	    }
	}

	if (badargs)
	{
	    fprintf(stderr,">E Usage: %s\n",USAGE);
	    GETHELP;
	    exit(1);
	}

	if (!quiet)
	{
	    fprintf(stderr,">A biplabg");
	    if (argnum > 0) fprintf(stderr," %s",infilename);
	    if (argnum > 1) fprintf(stderr," %s",outfilename);
	    fprintf(stderr,"\n");
	    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 (!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                  outcode = GRAPH6;

	if (codetype&HAS_HEADER)
	{
	    if (outcode == SPARSE6) writeline(outfile,SPARSE6_HEADER);
	    else    		    writeline(outfile,GRAPH6_HEADER);
	}

	nautil_check(WORDSIZE,1,1,NAUTYVERSIONID);

	nin = nout = 0;
	t = CPUTIME;
	while (TRUE)
	{
	    if ((g = readg(infile,NULL,0,&m,&n)) == NULL) break;
	    ++nin;

#if !MAXN
	    DYNALLOC2(graph,h,h_sz,n,m,"biplabg");
#endif
	    if (biplabel(g,m,n,h))
	    {
		++nout;
	        if (outcode == SPARSE6) writes6(outfile,h,m,n);
	        else                    writeg6(outfile,h,m,n);
	    }
	    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);
}