\input cwebmac
% This file is part of the Stanford GraphBase (c) Stanford University 1993
% This material goes at the beginning of all Stanford GraphBase CWEB files

\def\topofcontents{
  \leftline{\sc\today\ at \hours}\bigskip\bigskip
  \centerline{\titlefont\title}}

\font\ninett=cmtt9
\def\botofcontents{\vskip 0pt plus 1filll
    \ninerm\baselineskip10pt
    \noindent\copyright\ 1993 Stanford University
    \bigskip\noindent
    This file may be freely copied and distributed, provided that
    no changes whatsoever are made. All users are asked to help keep
    the Stanford GraphBase files consistent and ``uncorrupted,''
    identical everywhere in the world. Changes are permissible only
    if the modified file is given a new name, different from the names of
    existing files in the Stanford GraphBase, and only if the modified file is
    clearly identified as not being part of that GraphBase.
    (The {\ninett CWEB} system has a ``change file'' facility by
    which users can easily make minor alterations without modifying
    the master source files in any way. Everybody is supposed to use
    change files instead of changing the files.)
    The author has tried his best to produce correct and useful programs,
    in order to help promote computer science research,
    but no warranty of any kind should be assumed.
    \smallskip\noindent
    Preliminary work on the Stanford GraphBase project
    was supported in part by National Science
    Foundation grant CCR-86-10181.}

\def\prerequisite#1{\def\startsection{\noindent
    Important: Before reading {\sc\title},
    please read or at least skim the program for {\sc#1}.\bigskip
    \let\startsection=\stsec\stsec}}
\def\prerequisites#1#2{\def\startsection{\noindent
    Important: Before reading {\sc\title}, please read
    or at least skim the programs for {\sc#1} and {\sc#2}.\bigskip
    \let\startsection=\stsec\stsec}}



\def\title{QUEEN}


\N{1}{1}Queen moves.
This is a short demonstration of how to generate and traverse graphs
with the Stanford GraphBase. It creates a graph with 12 vertices,
representing the cells of a $3\times4$ rectangular board; two
cells are considered adjacent if you can get from one to another
by a queen move. Then it prints a description of the vertices and
their neighbors, on the standard output file.

An ASCII file called \.{queen.gb} is also produced. Other programs
can obtain a copy of the queen graph by calling \PB{\\{restore\_graph}(%
\.{"queen.gb"})}.
You might find it interesting to compare the output of {\sc QUEEN} with
the contents of \.{queen.gb}; the former is intended to be readable
by human beings, the latter by computers.

\Y\B\8\#\&{include} \.{"gb\_graph.h"}\C{ we use the {\sc GB\_\,GRAPH} data
structures }\6
\8\#\&{include} \.{"gb\_basic.h"}\C{ we test the basic graph operations }\6
\8\#\&{include} \.{"gb\_save.h"}\C{ and we save our results in ASCII format }\7
\\{main}(\,)\1\1\2\2\6
${}\{{}$\5
\1\&{Graph} ${}{*}\|g,{}$ ${}{*}\\{gg},{}$ ${}{*}\\{ggg};{}$\7
${}\|g\K\\{board}(\T{3\$L},\39\T{4\$L},\39\T{0\$L},\39\T{0\$L},\39{-}\T{1\$L},%
\39\T{0\$L},\39\T{0\$L}){}$;\C{ a graph with rook moves }\6
${}\\{gg}\K\\{board}(\T{3\$L},\39\T{4\$L},\39\T{0\$L},\39\T{0\$L},\39{-}\T{2%
\$L},\39\T{0\$L},\39\T{0\$L}){}$;\C{ a graph with bishop moves }\6
${}\\{ggg}\K\\{gunion}(\|g,\39\\{gg},\39\T{0\$L},\39\T{0\$L}){}$;\C{ a graph
with queen moves }\6
${}\\{save\_graph}(\\{ggg},\39\.{"queen.gb"}){}$;\C{ generate an ASCII file for
\PB{\\{ggg}} }\6
\X2:Print the vertices and edges of \PB{\\{ggg}}\X;\6
\&{return} \T{0};\C{ normal exit }\6
\4${}\}{}$\2\par
\fi

\M{2}\B\X2:Print the vertices and edges of \PB{\\{ggg}}\X${}\E{}$\6
\&{if} ${}(\\{ggg}\E\NULL){}$\1\5
${}\\{printf}(\.{"Something\ went\ wron}\)\.{g\ (panic\ code\ \%ld)!\\}\)%
\.{n"},\39\\{panic\_code});{}$\2\6
\&{else}\5
${}\{{}$\1\6
\&{register} \&{Vertex} ${}{*}\|v{}$;\C{ current vertex being visited }\7
\\{printf}(\.{"Queen\ Moves\ on\ a\ 3x}\)\.{4\ Board\\n\\n"});\6
${}\\{printf}(\.{"\ \ The\ graph\ whose\ o}\)\.{fficial\ name\ is\\n\%s\\}\)%
\.{n"},\39\\{ggg}\MG\\{id});{}$\6
${}\\{printf}(\.{"\ \ has\ \%ld\ vertices\ }\)\.{and\ \%ld\ arcs:\\n\\n"},\39%
\\{ggg}\MG\|n,\39\\{ggg}\MG\|m);{}$\6
\&{for} ${}(\|v\K\\{ggg}\MG\\{vertices};{}$ ${}\|v<\\{ggg}\MG\\{vertices}+%
\\{ggg}\MG\|n;{}$ ${}\|v\PP){}$\5
${}\{{}$\1\6
\&{register} \&{Arc} ${}{*}\|a{}$;\C{ current arc from \PB{\|v} }\7
${}\\{printf}(\.{"\%s\\n"},\39\|v\MG\\{name});{}$\6
\&{for} ${}(\|a\K\|v\MG\\{arcs};{}$ \|a; ${}\|a\K\|a\MG\\{next}){}$\1\5
${}\\{printf}(\.{"\ \ ->\ \%s,\ length\ \%ld}\)\.{\\n"},\39\|a\MG\\{tip}\MG%
\\{name},\39\|a\MG\\{len});{}$\2\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\U1.\fi

\N{1}{3}Index.
\fi

\inx
\fin
\con