This assignment will be collected automatically as described in ``Homework handin procedures.'' Also, please put your name and recitation section at the top of your handin.
shave --> stave --> stare --> stars --> sears --> bears --> beard
The assignment consists of three parts. In Part 1, you will build an abstract data type called a Queue. In Part 2, you will build an abstract data type called a Graph. The underlying representation for a Graph will be an adjacency list. In Part 2 you will also write a procedure for reading the description of a maze from a text file and building the corresponding Graph. After completing Part 2, the Queue and the Graph will be used by a search routine (which we provide) that finds a path between two points given by the user. Finally, in Part 3, you will associate a word with each ``room'' in the maze and extend the program from Part 2 to find paths between words.
The code we have given out to you is in five files in the assign2 directory: maze.c, queue.c, queue.h, graph.c, and graph.h. You will add code to the files maze.c, queue.c, and graph.c and then hand them in. You will not need to hand in or make any modifications to the files queue.h or graph.h. This assignment is more difficult than assignment 1, so START EARLY.
At the end of this assignment is a comment sheet; it is entirely optional.
Your solution (a file containing all the routines) should be in a file named ``queue.c''.
For this part you are to write a program that reads in a maze description from a file and builds the corresponding graph. The graph will be represented using an adjacency list. A ``maze description'' is simply a file containing pairs of numbers describing each passage by its end points. The pairs are preceded by two size numbers: the number of rooms and the number of passages. The rooms are numbered from 0 up to (#of rooms - 1). For example the maze above could be described by:
7
6
0 2
0 3
2 4
5 6
1 4
2 3
The Graph corresponding to this maze will have 7 nodes, and 6 edges.
Our representation of a Graph with n nodes will be an array of n node structures called Adj_list. The ith entry in the array, Adj_list[i], corresponds to the ith node in the graph, and is represented by the following structure
struct node {
word_t name; // the 'name' of the node (the 5 letter word associated with it)
int index; // the index of the node in Adj_list
list_element *neighbors; // a list of the neighbors of this node
};
You do not have to worry about the name field until part 3.
In this structure, neighbors is a pointer to a linked list
containing the indices in Adj_list of the node's neighbors.
The list elements are
represented by the following structure.
struct list_element { // an element on a node's list of neighbors
int neighbor; // the index of a neighbor
list_element *next;
};
Since your program will only find out the number of nodes at run-time
(when it reads in the file) the array Adj_list will have type
``node *''. When you read in the number of rooms you will then
allocate enough space for that many nodes.
Your job: Your job consists of two tasks. First, you are to implement the operations Graph::Graph, Graph::insert_edge, Graph::find_node_by_number, and Graph::nodes described in file ``graph.h''. Your solution belongs in file ``graph.c''. Next, you should write a function
Graph *read_maze(fstream &mazefile)that reads the maze from a file and builds the corresponding graph. (If you prefer, you may make this a member function of the Graph class and appropriately change graph.h: if so, you will need to slightly modify the main routine and you should hand in graph.h as well.) We have given you the code for associating an input stream to the input file, just like on Assignment 1. (The ``&'' is needed for passing the input stream into the procedure.) Your code should be in a file called maze.c (or you may put it into graph.c if you write the code as a member funcion). For simplicity in this assignment (all parts), you do not need to check that new returns a valid pointer, but you may if you wish.
In maze.c we have given you one half of a program to find paths through mazes. After doing Parts 1 and 2, you will have completed the second half of that program. You can use the parts we have provided to help you test your code. For example, if after reading in the maze shown above (also in the file tiny.maze) you typed:
0 1
the program should print:
0 2 4 1.
If you typed:
0 6
the program should print:
No path.
The files tiny.maze, small.maze, med.maze, and big.maze contain mazes of different sizes.
We have also given you object code that runs on the DECstations and SPARCstations in files maze.dec and maze.sparc that you can run. It is possible that your program may find somewhat different paths than this one and still be correct.
Hint: If you are having trouble debugging your code, you may wish to write a short routine that prints out the contents of the adjacency list you create. Or, you may wish to continue to part 3, after which it may be easier to observe the execution of your code.
One note: your compiler may give a warning that some line in main is not reachable. That's just because we have a ``while(1)'' loop in the code.
You may be wondering how we created these maze files. These were created by starting from a list of 5-letter words and declaring that two words are neighbors if they differ in only one letter. If 17 and 32 are connected in the maze, this corresponds to words 17 and 32 in the word file (the first word is number 0) differing in only one letter. The file ``small.maze'' was created from ``small.dictionary'' in this way. Similarly for files ``med.maze'' and ``big.maze.''
In Part 3, we ask you to modify the code in graph.c and maze.c so that:
Here are some paths you can use to test out your program. In the small database (small.maze and small.dictionary) words corresponding to the numbers listed in Part 2 are:
bread cheer -> bread breed creed creek cheek cheer
blood sweat -> blood brood broad bread breed creed creek cheek cheer
sheer sheet sweet sweat
blood water -> no path.
You can also try in the big dictionary:
party class -> party parts ports forts foots boots blots blows glows
gloss glass class
We give you object code for this problem in the files wordmaze.dec and wordmaze.sparc that you can try out. Your solution should be in maze.c.
Code in queue.h
/*
* The queue is represented as a linked list, with ``next'' pointers
* pointing from a node to the one behind it in line. Elements are
* inserted into the tail of the queue and removed from the head.
*
*
* An empty queue:
*
* (queue_t) p->+------+
* | NULL | tail
* +------+
* | NULL | head
* +------+
*
* A queue with two elements, 'a' and 'x', inserted in that order:
*
* p->+------+ +------+next +------+
* | *----tail----->| NULL |<-----------* |next
* +------+ +------+ +------+
* | * | head | 'x' |item | 'a' |item
* +---|--+ +------+ +------+
* | /|\
* +----------------------------------+
*/
struct queue_node {
queue_node *next; /* points to the next element, or NULL */
int item;
};
class Queue {
public:
Queue(); // Constructor. Executed when you create new one
int insert(int value); // Insert integer into queue
int remove(void); // If queue is not empty, remove element from the
// queue. Otherwise, return -1.
int length(void); // How many elements are in the queue
private:
queue_node *tail; // points to tail of queue, or NULL
queue_node *head; // points to head of queue, or NULL
int len; // length of the queue
};
Code in queue.c
#include <iostream.h>
#include "queue.h"
// Code for a queue of ints, using linked-list implementation
Queue::Queue() // no type needed for constructor
{
head = NULL;
tail = NULL;
len = 0;
}
int Queue::insert(int value)
{
// Some of your code for Part 1 goes here.
}
int Queue::length(void)
{
// Some of your code for Part 1 goes here.
}
// For cleanliness, sets tail to NULL on empty queue.
int Queue::remove(void)
{
// Some of your code for Part 1 goes here.
}
Code in graph.h
typedef char word_t[6]; // 6, not 5, so we have space for '\0'
struct list_element { // an element on a node's list of neighbors
int neighbor; // the index of a neighbor
list_element *next;
};
struct node {
word_t name; // the 'name' of the node (the 5 letter word associated with it)
int index; // the numeric identifier for the node: index in Adj_list
list_element *neighbors; // a list of the neighbors of this node
};
class Graph {
public:
Graph(int n); // Constructor. Executed when you create a new one.
// n is the number of nodes in the graph
int name_node(int number, char *name); // Part 3 only: Assigns a name to a node
int insert_edge(int neighbor1, int neighbor2); // Inserts an edge into the graph
// returns 0 on a success, -1 on a failure
node *find_node_by_number(int index); // Given a node number, returns that node structure
node *find_node_by_name(char *name); // Part 3 only: Given a node 'name',
// returns that node structure
int nodes(void); // Returns number of nodes in graph.
private:
int number_of_nodes;
node *Adj_list;
};
Code in graph.c
#include <iostream.h>
#include <strings.h>
#include "graph.h"
// Implementing graphs as an adjacency list...
Graph::Graph(int n)
{
// Some of your code for Part 2 goes here.
}
int Graph::name_node(int number, char *word)
{
// Some of your code for Part 3 goes here.
}
int Graph::insert_edge(int neighbor1, int neighbor2)
{
// Some of your code for Part 2 goes here.
}
node *Graph::find_node_by_number(int index)
{
// Some of your code for Part 2 goes here.
}
node *Graph::find_node_by_name(char *word)
{
// Some of your code for Part 3 goes here.
}
int Graph::nodes(void)
{
// Some of your code for Part 2 goes here.
}
Code in maze.c
#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include "queue.h"
#include "graph.h"
#define INIT (-1)
// This routine reads a maze from the stream pointed to by file, and
// builds a new Graph to represent the maze.
//
// The following line is an example of how you could read from the file.
// mazefile >> rooms;
// The first line of the file contains the number of rooms in the maze,
// which is an integer. The second line contains the number of passages,
// another integer. Each succeeding line contains a pair of room
// numbers, which represents a passage.
//
// Note that in the maze file, a passage i j represents a passage from
// room i to room j and a passage from room j to room i.
Graph *read_maze(fstream &mazefile)
{
// *******************************
// Your code for Part 2 goes here.
// *******************************
}
int main(void)
{
fstream mazefile; // the file containing the maze
fstream dictfile; // the file containing the dictionary
char file_name[50]; // temporary space for typing in file names
Graph *maze; // the maze
word_t dict_word; // the words
int i; // an index variable
int *parent; // the parent array;
cout << "Enter the name of the mazefile: " << endl;
cin >> file_name;
mazefile.open(file_name, ios::in); // open in "input mode"
if (!mazefile) {
cout << "Sorry, can't find file " << file_name << endl;
return 1;
}
maze = read_maze(mazefile);
// The following seven lines are needed for Part 3.
// Uncomment them when you start to work on Part 3.
// cout << "Enter the name of the dictionary file: " << endl;
// cin >> file_name;
// dictfile.open(file_name, ios::in); // open in "input mode"
// if (!dictfile) {
// cout << "Sorry, can't find file " << file_name << endl;
// return 1;
// }
// ****************************************************************
// Your code for Part 3 goes here. You access the dictionary using
// dict_file >>
// ****************************************************************
parent = new int[maze->nodes()];
Queue myqueue; // creates an empty queue
while(1) {
int start, end, current;
node *current_node;
list_element *ptr;
// ***********************************************************
// For Part 3, you will have to rewrite the following 3 lines.
// (Your code may take more than three lines.)
// ***********************************************************
// read in start and end room numbers
cout << "Give two vertices: ";
cin >> start;
cin >> end;
// initialize parent array
for(i=0; i < maze->nodes(); ++i) parent[i] = INIT;
// THE SEARCH:
// begin at "end" and go back to start so can print out more easily.
// The following is an implementation of breadth-first search
parent[end] = end; // assign a dummy value to parent[end]
myqueue.insert(end); // start it off
while(myqueue.length() > 0) {
current = myqueue.remove();
if (current == start) break; // can stop now!
// search the adjacency list of current node for
// neighbors that have not yet been visited
current_node = maze->find_node_by_number(current);
for(ptr = current_node -> neighbors; ptr != NULL; ptr = ptr->next) {
if (parent[ptr->neighbor] == INIT) {
parent[ptr->neighbor] = current;
myqueue.insert(ptr->neighbor);
}
}
}
// now, read off the path
if (current != start) cout << "No path." << endl; /* didn't find it */
else {
for (i=start; i != end; i=parent[i])
{
current_node = maze->find_node_by_number(i);
cout << current_node->name << " ";
}
cout << (maze->find_node_by_number(end))->name << endl;
}
// empty out the queue, so can start over
int junk;
while(myqueue.length() > 0)
junk = myqueue.remove();
} /* end while(1) loop */
}