@x
@c
#include "gb_graph.h" /* use the Stanford GraphBase conventions */
#include "gb_save.h" /* and its routine for inputting graphs */
@y
Instead of finding all solutions, this variant of the program estimates
the size of the search tree. {\it Warning:} At present, we handle only
graphs that contain at least one vertex of degree two.

@c
#include "gb_graph.h" /* use the Stanford GraphBase conventions */
#include "gb_save.h" /* and its routine for inputting graphs */
#include "gb_flip.h" /* and its random number generator */
@z
@x
  @<Prepare the graph for backtracking@>;
  @<Backtrack through all solutions@>;
@y
  gb_init_rand(seed);
  for (r=1;r<=reps;r++) {
    @<Prepare the graph for backtracking@>;
    @<Do the Monte Carlo Backtrack estimation@>;
 done: while (l<maxl) {
    profile_est[l]-=profile_est[l]/(double)r;
    sols_est[l]-=sols_est[l]/(double)r;
    l++;
    }
  }
@z
@x
@ The given graph should be in Stanford GraphBase format, in a file
like |"foo.gb"| named on the command line. This file name can optionally
be followed by a modulus |m|, which causes every $\vert m\vert$th solution
to be printed.
If a third command line argument appears, the output will be extremely verbose.

The modulus |m| might be negative; this indicates that solutions should be
printed showing edges in the order they were discovered, rather than in the
natural circuit order.

@d max_n 100 /* our arrays will accommodate this many vertices at most */
@d infty 1000000000 /* infinity (approximately) */

@<Process the command line, inputting the graph@>=
if (argc>1) g=restore_graph(argv[1]);@+ else g=NULL;
if (argc<3 || sscanf(argv[2],"%d",&modulus)!=1) modulus=infty;
if (!g || modulus==0) {
  fprintf(stderr,"Usage: %s foo.gb [[-]modulus] [verbose]\n",argv[0]);
  exit(-1);
}
@y
@ The given graph should be in Stanford GraphBase format, in a file
like |"foo.gb"| named on the command line. The next command line
argument should be the desired number of repetitions, and the
third should be a seed value for the random number generator.

@d max_n 1000 /* our arrays will accommodate this many vertices at most */
@d infty 1000000000 /* infinity (approximately) */

@<Process the command line, inputting the graph@>=
if (argc<4 || !(g=restore_graph(argv[1])) ||
  sscanf(argv[2],"%d",&reps)!=1 || sscanf(argv[3],"%d",&seed)!=1) {
  fprintf(stderr,"Usage: %s foo.gb reps seed [verbose]\n",argv[0]);
  exit(-1);
}
@z
@x
if (argc>3) verbose=1;

@ The |verbose| variable is declared in \.{gb\_graph.h}.

@<Glob...@>=
int modulus; /* how often we should show solutions */
@y
if (argc>4) verbose=1;

@ The |verbose| variable is declared in \.{gb\_graph.h}.

@<Glob...@>=
int r,reps,seed;
double profile_est[max_n], sols_est[max_n];
double tot_nodes, tot_sols;
double factor;
@z
@x
if (d<2) {
@y
if (d>2) {
  printf("I'm sorry, but all vertices have degree >= %d;\n", d);
  printf("I need a vertex of degree 2 to get started!\n");
  exit(-2);
}
if (d<2) {
@z
@x
@ @<Print the results@>=
printf("Altogether %d solutions.\n",total);
if (verbose) {
  for (k=1;k<=maxl;k++)
    printf("%3d: %d\n",k,profile[k]);
}
@y
@ @<Print the results@>=
profile_est[0]=1.0;
for (k=0;k<maxl;k++) {
  printf("Level %d: %20.1f nodes, %20.1f solutions\n",
      k+1,profile_est[k],sols_est[k]);
  tot_nodes+=profile_est[k];
  tot_sols+=sols_est[k];
}
printf("Total estimate %20.1f nodes, %20.1f solutions.\n",
      tot_nodes, tot_sols);
@z
@x
@<Backtrack through all solutions@>=
@<Bootstrap the backtrack process@>;
advance: @<Clothe everything on the bare list@>;
     /* here I said |sanity_check(NULL)| when debugging */
l++;
if (verbose) {
  if (l>maxl) maxl=l;
  printf("Entering level %d:",l);
  profile[l]++;
}
if (ocount>=g->n-1) @<Check for solution and |goto backup|@>;
@<Choose an outer vertex |v| of minimum degree |d|@>;
if (verbose) printf(" choosing %s(%d)\n",v->name,d);
if (d==0) goto backup;
curv[l]=v,curi[l]=1,maxi[l]=d,curb[l]=bcount,curo[l]=ocount;
source[ocount]=v;
w=v->mate;
@<Promote |v| from |outer| to |inner|@>;
a=v->arcs;
try_move:@+for (;;a=a->next) {
  u=a->tip;
  if (u->type!=inner && u!=w) break;
}
@y
@<Do the Monte...@>=
@<Bootstrap the backtrack process@>;
factor=1.0;
advance: @<Clothe everything on the bare list@>;
l++;
if (l>maxl) maxl=l;
if (verbose) {
  printf("Entering level %d:",l);
}
if (ocount>=g->n-1) @<Check for solution and |goto done|@>;
@<Choose an outer vertex |v| of minimum degree |d|@>;
if (verbose) printf(" choosing %s(%d)\n",v->name,d);
if (d==0) goto done;
curv[l]=v,maxi[l]=d,curb[l]=bcount,curo[l]=ocount;
curi[l]=gb_unif_rand(d)+1;
factor*=maxi[l];
profile_est[l]+=(factor-profile_est[l])/(double)r;
source[ocount]=v;
w=v->mate;
@<Promote |v| from |outer| to |inner|@>;
a=v->arcs;
try_move:@+for (k=curi[l]-1;;a=a->next) {
  u=a->tip;
  if (u->type!=inner && u!=w) {
    if (k) k--; else break;
    }
}
@z
@x
    if (v->deg!=2) {
      if (verbose) printf("(oops, low degree; backing up)\n");
      goto emergency_backup; /* see below */
    }
    @<Find the two neighbors, |u| and |w|, of vertex |v|@>;
    if (u->mate==w && ocount!=g->n-2) {
      if (verbose) printf("(oops, short cycle; backing up)\n");
      goto emergency_backup;
    }
@y
    if (v->deg!=2) goto done;
    @<Find the two neighbors, |u| and |w|, of vertex |v|@>;
    if (u->mate==w && ocount!=g->n-2) goto done;
@z
@x
  total++;
  if (total%modulus==0 || verbose) {
    curo[l]=ocount;
    source[ocount]=head->rlink, dest[ocount]=head->llink;
    curi[l]=maxi[l]=1;
    if (modulus<0) {
      printf("\n%d:\n",total);@+print_state();
    }@+else @<Unscramble and print the current solution@>;
  }
  goto backup;
@y
  sols_est[l]+=(factor-sols_est[l])/(double)r;
  goto done;
@z
@x
  for (a=u->arcs;a;a=a->next) if (a->tip==v) goto yes;
  goto backup;
@y
  for (a=u->arcs;a;a=a->next) if (a->tip==v) goto yes;
  goto done;
@z