I will test your GRAPH ADT with a test program of my own so your program must use the following header file with no modifications to define the graph and it's functions.
#define DIRECTED 1
#define UNDIRECTED 0
#define INFINITE_COST -1
enum trav_type {DEPTH_FIRST, BREATH_FIRST};
typedef struct
{
char from_node,to_node;
} edge;
typedef struct The_Graph
{
int ** adj;
char * node_names;
int num_nodes;
int max_nodes;
int directed;
} a_graph;
void init_graph(a_graph *g, int max_num_nodes, int directed_graph);
void destroy_graph(a_graph *g);
void copy_graph(a_graph *orig, a_graph *copy);
int add_edge(a_graph *g, edge new_edge, int cost);
int remove_edge(a_graph *g, edge old_edge);
int adjacent(a_graph *g, edge check_edge);
int cost_to_traverse(a_graph *g, edge the_edge);
int traverse_graph(a_graph *g, enum trav_type t_type, char start_node,
void (*action)(a_graph *g, char node));
void print_graph(a_graph a);
The edge is a structure that holds the two nodes that represent and
edge in a graph. A directed edge will go from the node
from_node to the node to_node. Undirected
edge will go both directions.
The graph structure must use the typedef described above, the description of the parts are:
int ** adj; the adjacency matrix, a 2 dimentional array
of weights
char * node_names; an array of node names
int num_nodes; the number of nodes in the graph
int max_nodes; the max number of nodes supported
int directed; tells if the graph is directed legal values
are DIRECTED and UNDIRECTED (defined in
the #define's in the header file)
This function initializes the graph, getting it ready to be used. This includes dynamically allocating space for the 2 dimentional adjacency matrix, and the array of node names. Make sure that both have enogh room for enough room to allow for max_num_nodes elements to be added to the graph. The weights in the adjacency matrix should be initialized to the defined constant INFINITE_COST. The directed_graph parameter is used to tell if the graph will be DIRECTED and UNDIRECTED. In addition any other initialization work that needs to be done.
This function should free the dynamically allocating space used by a graph.
This function should make the copy graph
a copy of the orig graph. Note that the copy
graph will may not have been initialized with the
init_graph function
prior to this routine.
This function will insert the new edge into the graph with the specified weight. If either of the nodes are not already in the graph, the function should add the nodes. Remember, for UNDIRECTED graphs, the edge goes both ways (from source to destination, and then from destination to source).
This function should return a boolean value telling if it was able to successfully add the edge.
1 : if it was able to add the edge 0 : otherwise
This function will remove the specified edge from the graph
This function should return a boolean value telling if it was able to successfully remove the edge.
1 : if the edge existed and was removed 0 : otherwise
This function should check to see if the nodes in
check_edge are adjacent. Returning:
1 : if the nodes exist and are adjacent
0 : otherwise
This function should return the cost of the edge
the_edge. If the specified nodes, or the
edge doesn't exist, then return the
defined constant INFINITE_COST.
This function should implement a generic graph traversal routine that allows for both depth first and breath first traversal of the graph.
The type of the traversal will be specified by the t_type
parameter, whose values are specified in the enum
trav_type with legal values of DEPTH_FIRST or BREATH_FIRST.
The starting node for the traversal is specified by the
start_node parameter.
The last parameter is a pointer to a function which will be the
action to be performed on each node you visit during the traversal. The
function will take two parameters, the first one a pointer to a graph,
and the second one the name of the node being visited. The function
will return nothing (void). An example of a function that could be
passed as the action parameter would be:
void print_node(a_graph *g, char node)
{
printf("%c ",node);
}
To implement the traversal, you will need a stack (for DEPTH_FIRST) and a queue (for BREATH_FIRST). I have implemented a stack and queue ADT for you, you can find the header file, and object file for these ADTs in my ~paw-grd/pub/icsg707/lab2 directory.
This function should print out the contents of the adjacency matrix in the following format:
a b c d e
a . . . 10 .
b 2 . . . .
c . 8 . . 3
d 10 . . . 2
e . . 3 2 .
Here the top row shows the name of the destination node, the
left column shows the name of the source node. Inside these the
weights in the adjacency matrix should be printed. Here replace all
INFINITE_COST weights with the character '.' (a period).
You must implement a test driver main program that will test your graph to make sure that it is working correctly. This driver program will be graded, so you should make sure that it contains code that will completely tests all the functions of the graph.
I will be testing your graph ADT using my own test program.
The following files have been provided for you, and are located in the directory:
The files are:
You must use the provided graph.h file exactly as provided. To ensure this you will not be submitting the graph.h, I will be using my copy of it. In addition you will be using my stack and queue ADT code, so yet again you will not be submitting that code either.
You must use separate files to contain the code for you graph ADT and your test driver program. Specifically, you must call the file that contains the code for the graph ADT graph.c and the file containing your driver program test.c.
You must submit a file named README with your project. This file should contain information that I should know about your program. This must include how to compile and run your test program. It should also contain a list of all the files submitted describing what the files contain, and why they were submitted. In addition, you include any notes you think would be useful while I grade the assignment.
This project will be graded out of 50 points
For "program design, style, and documentation" I am looking for programs that have broken the tasks up into "meaningful chunks" of manageable size (try to keep all functions to less than one page, ~25 lines of code). As for style, I am looking for code that is neat, clear and consistent. I will also look for good block comments for all program files and functions you submit. Plus comments for sections of the code whose function is not obvious (good variable names will make these comments less important).
submit -v paw-grd lab1 README graph.c test.c
graph.c is your code files for the
implementation of your graph ADT and test.c
is the test driver program that you wrote.
Submit your "Makefile" if you used one to compile your code.
Do not submit any executable or object files.
Feel free to submit any other code, header or data files that you used in the development or testing of your program (as long as you submit the files specified). If you do submit any extra files, make sure that you document their use in the README file.
For information on the submit command check out: