text: /* 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);
  }
  