/* newedgeg.c  version 1.1; B D McKay, Dec 2005. */

#define USAGE "newedgeg [-lq] [infile [outfile]]"

#define HELPTEXT \
" For each pair of non-adjacent edges, output the graph obtained\n\
  by subdividing the edges and joining the new vertices.\n\
\n\
    The output file has a header if and only if the input file does.\n\
\n\
    -l  Canonically label outputs\n\
    -q  Suppress auxiliary information\n"

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

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

static FILE *outfile;
static nauty_counter nout;
static int outcode;

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

static void
newedge(graph *g1, int m1, int n1,
        int v1, int v2, int w1, int w2,
        graph *g2, int m2) 
/* Make g2 by subdividing edges v1-v2 and w1-w2 in g1
   and adding an edge between them.  Must have m2 >= m1.  */
{
	int i,j;
	setword *s1,*s2;

	s1 = g1;
	s2 = g2;
	for (i = 0; i < n1; ++i)
	{
	    for (j = 0; j < m1; ++j) *(s2++) = *(s1++);
	    for (; j < m2; ++j) *(s2++) = 0;
	}

	s2 = GRAPHROW(g2,v1,m2);
	DELELEMENT(s2,v2);
	ADDELEMENT(s2,n1);

	s2 = GRAPHROW(g2,v2,m2);
        DELELEMENT(s2,v1);
        ADDELEMENT(s2,n1);

	s2 = GRAPHROW(g2,w1,m2);
        DELELEMENT(s2,w2);
        ADDELEMENT(s2,n1+1);

	s2 = GRAPHROW(g2,w2,m2);
        DELELEMENT(s2,w1);
        ADDELEMENT(s2,n1+1);

	s2 = GRAPHROW(g2,n1,m2);
	EMPTYSET(s2,m2);
	ADDELEMENT(s2,v1);
	ADDELEMENT(s2,v2);
	ADDELEMENT(s2,n1+1);

	s2 = GRAPHROW(g2,n1+1,m2);
	EMPTYSET(s2,m2);
	ADDELEMENT(s2,w1);
	ADDELEMENT(s2,w2);
	ADDELEMENT(s2,n1);
}

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

static void
na_newedge(graph *g1, int m1, int n1, boolean dolabel)
/* Make all graphs by non-adjacent edge addition. */
{
	int n2,m2;
	int v1,v2,w1,w2;
	set *sv1,*sw1;
	graph *gq;
#if MAXN
	graph h[MAXN*MAXM];
	grapg g2[MAXN*MAXM];
#else
	DYNALLSTAT(graph,h,h_sz);
	DYNALLSTAT(graph,g2,g2_sz);
#endif

	n2 = n1 + 2;
	m2 = (n2 + WORDSIZE - 1) / WORDSIZE;
	if (m2 < m1) m2 = m1;

#if !MAXN
	DYNALLOC2(graph,g2,g2_sz,m2,n2,"newedgeg");
	if (dolabel) DYNALLOC2(graph,h,h_sz,m2,n2,"newedgeg");
#endif

	for (v1 = 0, sv1 = g1; v1 < n1-3; ++v1, sv1 += m1)
	for (w1 = v1+1, sw1 = sv1 + m1; w1 < n1-1; ++w1, sw1 += m1)
	{
	    for (v2 = v1; (v2 = nextelement(sv1,m1,v2)) >= 0; )
	    for (w2 = w1; (w2 = nextelement(sw1,m1,w2)) >= 0; )
	    {
		if (v2 == w1 || v2 == w2) continue;

		newedge(g1,m1,n1,v1,v2,w1,w2,g2,m2);

                gq = g2;

                if (dolabel)
                {
                    fcanonise(g2,m2,n2,h,NULL,FALSE);  /* FIXME (loops) */
                    gq = h;
                }
                if (outcode == SPARSE6) writes6(outfile,gq,m2,n2);
                else                    writeg6(outfile,gq,m2,n2);
                ++nout;
	    }
	}
}

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

int
main(int argc, char *argv[])
{
        char *infilename,*outfilename;
        FILE *infile;
        boolean badargs,dolabel,quiet;
	int j,m,n,argnum;
	int codetype;
	graph *g;
	nauty_counter nin;
        char *arg,sw;
	double t;

	HELP; PUTVERSION;

        infilename = outfilename = NULL;
	dolabel = 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 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 newedgeg");
	    if (dolabel) fprintf(stderr," -l");
	    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);
	}

	if (dolabel) nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);

	nin = nout = 0;
	t = CPUTIME;
	while (TRUE)
	{
	    if ((g = readg(infile,NULL,0,&m,&n)) == NULL) break;
#if MAXN
	    if (n > MAXN-2)
	    {
		fprintf(stderr,">E newedgeg: input too large\n");
		exit(1);
	    }
#endif

	    ++nin;

	    na_newedge(g,m,n,dolabel);

	    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);
}