§1  QUEEN  QUEEN MOVES 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 × 4 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 is also produced. Other programs can obtain a copy of the queen graph by calling restore graph( ). You might find it interesting to compare the output of QUEEN with the contents of ; the former is intended to be readable by human beings, the latter by computers. #include /∗ we use the GB GRAPH data structures ∗/ #include /∗ we test the basic graph operations ∗/ #include /∗ and we save our results in ASCII format ∗/

main( ) { Graph ∗g, ∗gg , ∗ggg ;

g = board (3_{L}, 4_{L}, 0_{L}, 0_{L}, −1_{L}, 0_{L}, 0_{L}); /∗ a graph with rook moves ∗/ gg = board (3_{L}, 4_{L}, 0_{L}, 0_{L}, −2_{L}, 0_{L}, 0_{L}); /∗ a graph with bishop moves ∗/ ggg = gunion(g, gg , 0_{L}, 0_{L}); /∗ a graph with queen moves ∗/ save graph(ggg , ); /∗ generate an ASCII file for ggg ∗/ ⟨ Print the vertices and edges of ggg 2 ⟩; return 0; /∗ normal exit ∗/

}

2. ⟨ Print the vertices and edges of ggg 2 ⟩ ≡ if (ggg ≡ Λ) printf ( ␣ ␣ ␣ ␣ ␣ , panic code); else {

register Vertex ∗v; /∗ current vertex being visited ∗/ printf ( ␣ ␣ ␣ ␣ ␣ ); printf ( ␣␣ ␣ ␣ ␣ ␣ ␣ , ggg id ); printf ( ␣␣ ␣ ␣ ␣ ␣ ␣ , ggg n, ggg m); for (v = ggg vertices ; v < ggg vertices + ggg n; v^{++}) {

register Arc ∗a; /∗ current arc from v ∗/

printf ( , v name);

for (a = v arcs ; a; a = a next ) printf ( ␣␣ ␣ ␣ ␣ , a tip name, a len); }

}

This code is used in section 1.

2  INDEX  QUEEN §3

3. Index.

a: \underline{2}. Arc: 2. arcs : 2. board : 1. g: \underline{1}. gg : \underline{1}. ggg : \underline{1}, 2. Graph: 1. gunion: 1. id : 2. len: 2. main: \underline{1}. name: 2. next : 2. panic code: 2. printf : 2. restore graph: 1. save graph: 1. tip: 2. v: \underline{2}. Vertex: 2. vertices : 2.

QUEEN NAMES OF THE SECTIONS 3

⟨ Print the vertices and edges of ggg 2 ⟩ Used in section 1.

March 30, 2004 at 09:48

QUEEN

Section Page

Queen moves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2

\begin{matrix}c \\ ◯ \end{matrix} 1993 Stanford University

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 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. Preliminary work on the Stanford GraphBase project was supported in part by National Science Foundation grant CCR-86-10181.