% This file is part of the Stanford GraphBase (c) Stanford University 1993@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!@i gb_types.w\def\title{LADDERS}\prerequisites{GB\_WORDS}{GB\_\,DIJK}@* Introduction. This demonstration program uses graphsconstructed by the {\sc GB\_WORDS} module to producean interactive program called \.{ladders}, which finds shortest pathsbetween two given five-letter words of English.The program assumes that \UNIX/ conventions are being used. Some code insections listed under `\UNIX/ dependencies' in the index might need to changeif this program is ported to other operating systems.\def\<#1>{$\langle${\rm#1}$\rangle$}To run the program under \UNIX/, say `\.{ladders} \<options>', where \<options>consists of zero or more of the following specifications in any order:{\narrower\def\\#1 {\smallskip\noindent  \hbox to 6em{\tt#1\hfill}\hangindent 8em\hangafter1 }\\-v Verbosely print all words encountered during the shortest-path     computation, showing also their distances from the goal word.\\-a Use alphabetic distance instead of considering adjacent words to be one     unit apart; for example, the alphabetic distance from `\.{words}' to     `\.{woods}' is~3, because `\.r' is three places from `\.o' in the     alphabet.\\-f Use distance based on frequency (see below), instead of considering     adjacent words to be one unit apart. This option is ignored if either     \.{-a} or \.{-r} has been specified.\\-h Use a lower-bound heuristic to shorten the search (see below). This option     is ignored if option \.{-f} has been selected.\\-e Echo the input to the output (useful if input comes from a file instead     of from the terminal).\\-n\<number> Limit the graph to the |n| most common English words, where |n|     is the given \<number>.\\-r\<number> Limit the graph to \<number> randomly selected words. This option     is incompatible with~\.{-n}.\\-s\<number> Use \<number> instead of 0 as the seed for random numbers, to get     different random samples or to explore words of equal frequency in     a different order.\smallskip}\noindent Option \.{-f} assigns a cost of 0 to the most common words and acost of 16 to the least common words; a cost between 0 and~16 is assigned towords of intermediate frequency. The word ladders that are found will then haveminimum total cost by this criterion. Experience shows that the \.{-f} optiontends to give the ``friendliest,'' most intuitively appealing ladders.\smallskipOption \.{-h} attempts to focus the search by giving priority to words thatare near the goal. (More precisely, it modifies distances between adjacentwords by using a heuristic function $\\{hh}(v)$, which would be the shortestpossible distance between $v$ and the goal if every five-letter combinationhappened to be an English word.) The {\sc GB\_\,DIJK} module explains moreabout such heuristics; this option is most interesting to watch when used inconjunction with \.{-v}.@ The program will prompt you for a starting word. If you simply type\<return>, it exits; otherwise you should enter a five-letter word(with no uppercase letters) before typing \<return>.Then the program will prompt you for a goal word. If you simply type\<return> at this point, it will go back and ask for a new starting word;otherwise you should specify another five-letter word.Then the program will find and display an optimal word ladder from the startto the goal, if there is a path from one to the otherthat changes only one letter at a time.And then you have a chance to start all over again, with another starting word.The start and goal words need not be present in the program's graph of``known'' words. They are temporarily added to that graph, but removedagain whenever new start and goal words are given. (Thus you can gofrom \.{sturm} to \.{drang} even though those words aren't English.)If the \.{-f} option is being used, the cost of the goal word will be 20when it is not in the program's dictionary.@ Here is the general layout of this program, as seen by the \CEE/ compiler:@^UNIX dependencies@>@p#include <ctype.h> /* system file for character types */#include "gb_graph.h" /* the standard GraphBase data structures */#include "gb_words.h" /* routines for five-letter word graphs */#include "gb_dijk.h" /* routines for shortest paths */@h@#@<Global variables@>@;@<Subroutines@>@;main(argc,argv)  int argc; /* the number of command-line arguments */  char *argv[]; /* an array of strings containing those arguments */{  @<Scan the command-line options@>;  @<Set up the graph of words@>;  while(1) {    @<Prompt for starting word and goal word; |break| if none given@>;    @<Find a minimal ladder from |start| to |goal|, if one exists,        and print it@>;  }  return 0; /* normal exit */}@* Parsing the options. Let's get the \UNIX/ command-line junk out of theway first, so that we can concentrate on meatier stuff. Our job in this partof the program is to see if the default value zero of external variable|verbose| should change, and/or if the default values of any of the followinginternal variables should change:@<Global variables@>=char alph=0; /* nonzero if the alphabetic distance option is selected */char freq=0; /* nonzero if the frequency-based distance option is selected */char heur=0; /* nonzero if the heuristic search option is selected */char echo=0; /* nonzero if the input-echo option is selected */unsigned long n=0; /* maximum number of words in the graph (0 means infinity) */char randm=0; /* nonzero if we will ignore the weight of words */long seed=0; /* seed for random number generator */@ @<Scan the command-line options@>=while (--argc) {@^UNIX dependencies@>  if (strcmp(argv[argc],"-v")==0) verbose=1;  else if (strcmp(argv[argc],"-a")==0) alph=1;  else if (strcmp(argv[argc],"-f")==0) freq=1;  else if (strcmp(argv[argc],"-h")==0) heur=1;  else if (strcmp(argv[argc],"-e")==0) echo=1;  else if (sscanf(argv[argc],"-n%lu",&n)==1) randm=0;  else if (sscanf(argv[argc],"-r%lu",&n)==1) randm=1;  else if (sscanf(argv[argc],"-s%ld",&seed)==1) ;  else {    fprintf(stderr,"Usage: %s [-v][-a][-f][-h][-e][-nN][-rN][-sN]\n",argv[0]);    return -2;  }}if (alph || randm) freq=0;if (freq) heur=0;@*Creating the graph. The GraphBase |words| procedure will produce thefive-letter words we want, organized in a graph structure.@d quit_if(x,c)  if (x) {    fprintf(stderr,      "Sorry, I couldn't build a dictionary (trouble code %ld)!\n",c);    return c;  }@<Set up the graph of words@>=g=words(n,(randm? zero_vector: NULL), 0L,seed);quit_if(g==NULL,panic_code);@<Confirm the options selected@>;@<Modify the edge lengths, if the |alph| or |freq| option was selected@>;@<Modify the priority queue algorithm, if unequal edge lengths are possible@>;@ @<Glob...@>=Graph *g; /* graph created by |words| */long zero_vector[9]; /* weights to use when ignoring all frequency information */@ The actual number of words might be decreased to the size of the GraphBasedictionary, so we wait until the graph is generated before confirmingthe user-selected options.@<Confirm the options selected@>=if (verbose) {  if (alph) printf("(alphabetic distance selected)\n");  if (freq) printf("(frequency-based distances selected)\n");  if (heur)    printf("(lowerbound heuristic will be used to focus the search)\n");  if (randm) printf("(random selection of %ld words with seed %ld)\n",    g->n,seed);  else printf("(the graph has %ld words)\n",g->n);}@ The edges in a |words| graph normally have length 1, so we must change themif the user has selected |alph| or |freq|. The character position in whichadjacent words differ is recorded in the |loc| field of each arc. Thefrequency of a word is stored in the |weight| field of its vertex.@d a_dist(k) (*(p+k)<*(q+k)? *(q+k)-*(p+k): *(p+k)-*(q+k))@<Modify the edge lengths, if the |alph| or |freq| option was selected@>=if (alph) {@+register Vertex *u;  for (u=g->vertices+g->n-1; u>=g->vertices; u--) {@+register Arc *a;    register char *p=u->name;    for (a=u->arcs; a; a=a->next) {@+register char *q=a->tip->name;      a->len = a_dist(a->loc);    }  }}@+else if (freq) {@+register Vertex *u;  for (u=g->vertices+g->n-1; u>=g->vertices; u--) {@+register Arc *a;    for (a=u->arcs; a; a=a->next)      a->len = freq_cost(a->tip);  }}@ The default priority queue algorithm of |dijkstra| is quite efficientwhen all edge lengths are~1. Otherwise we change it to thealternative method that works best for edge lengths less than~128.@<Modify the priority queue algorithm...@>=if (alph || freq || heur) {  init_queue=init_128;