CSE 373: Data Structures and Algorithms
Autumn 1994
Programming Assignment 3 Solution
/***********************************************************************
************************************************************************
****
****
**** Eulerian Circuit/Path Finder
****
**** by Brian Van Horne
**** CSE 373A
**** Autumn 1994
**** Programming Assignment #3
**** 5 December 1994
****
**** Takes as input a data file containing graph descriptions and,
**** for each graph in turn, it finds an Eulerian Circuit or Path,
**** if possible. The process of finding the path does destroy the
**** graph in memory (deleting each edge as it is traversed insures
**** that it won't be traversed again). The Graph is stored as an
**** array (from 1 to # of Vertices) of adjacency lists. The array
**** contains the header node for each list. The data element in
**** header indicates the current degree of that vertex, while the
**** data element in the 0th (unused) element of the array is used
**** as a counter for the number of un-traversed edges in the
**** graph. Each node in an adjacency list is linked to its mirror
**** image (or TWIN) node in another list. This allows for easy
**** access to both nodes that represent a single edge at the same
**** time.
****
**** Filename: EULER.C
**** Executable: EULER.EXE
****
****
************************************************************************
***********************************************************************/
/***********************************************************
************************************************************
****
**** Preprocessor Directives
***/
#include
#include
#define MAX_PRINT_POS 68 /* Used by Path-Print Function */
/***********************************************************
************************************************************
****
**** Global Type Declarations
***/
typedef FILE *file_ptr;
/* Graph - Adjacency List Representation */
typedef struct graph_node *graph_ptr;
struct graph_node {
int adj;
graph_ptr twin;
graph_ptr prev;
graph_ptr next;
};
/* Linked List for Path */
typedef struct path_node *path_ptr;
struct path_node {
int vertex;
path_ptr next;
};
/***********************************************************
************************************************************
****
**** Global Variables
***/
int print_pos = 0; /* Used to keep track of screen position */
/***********************************************************
************************************************************
****
**** Function Prototypes
***/
void find_euler(graph_ptr graph, int num_ver);
void dfs(graph_ptr graph, int vertex, path_ptr path);
int graph_read(file_ptr fp, graph_ptr *graph);
graph_ptr graph_init(int num_ver);
void graph_add(graph_ptr graph, int vertex, int adj);
void graph_add_node(graph_ptr list, int adj);
void graph_del(graph_ptr graph, graph_ptr node);
void graph_del_node(graph_ptr node);
void graph_print(graph_ptr graph, int num_ver);
void graph_free(graph_ptr graph, int num_ver);
path_ptr path_init(void);
void path_add(path_ptr node, int vertex);
void path_print(path_ptr list);
void path_free(path_ptr list);
file_ptr open_file(void);
void print_header(void);
void print_footer(void);
void error(const char *message);
void print_line(int length, char ch);
/***********************************************************
************************************************************
****
**** Functions
****
************************************************************
***********************************************************/
/***********************************************************
************************************************************
****
**** Main Function: Opens the data file, and then reads
**** each graph in, calls the Find Euler function on
**** it, and then calls the Free Graph function to
**** clean up for the next graph.
***/
void main(void)
{
int num_ver; /* Number of Vertices in Graph */
file_ptr fp; /* The Data File */
graph_ptr graph; /* The Graph (adjancency list) */
print_header();
fp = open_file();
while((num_ver=graph_read(fp, &graph)) != 0) {
find_euler(graph, num_ver);
graph_free(graph, num_ver);
}
fclose(fp);
print_footer();
return;
}
/***********************************************************
************************************************************
****
**** Find Euler Function: Displays the graph, checks
**** for the necessary and sufficient condition and
**** then, if appropriate, calls the Depth First Search
**** function and finally displays the path.
***/
void find_euler(graph_ptr graph, int num_ver)
{
int i;
int odd = 0; /* Number of Vertices w/ Odd Degree */
int start = 1; /* Default Start Position for Traversal */
path_ptr path; /* The Linked List for the Path */
/* Display the Graph (in adjancency list format) */
print_line(72, '-');
graph_print(graph, num_ver);
/* Check for Necessary and Sufficient Condition */
for(i=num_ver; i>0; i--)
if(graph[i].adj%2) {
odd++;
start = i;
}
switch(odd) {
case 0: /* No Vertices w/ Odd Degree */
printf("Eulerian Circuit: %n", &print_pos);
break;
case 2: /* Exactly 2 Vertices w/ Odd Degree */
printf("Eulerian Circuit: Impossible\n");
printf("Eulerian Path: %n", &print_pos);
break;
default: /* Vertices w/ Odd Degree: >0 but !=2 */
printf("Eulerian Circuit: Impossible\n");
printf("Eulerian Path: Impossible\n\n");
return;
}
path = path_init(); /* Initialize Linked List */
dfs(graph, start, path); /* Traverse Graph (the REAL work) */
if(graph[0].adj) /* If there are still untraversed edges . . . */
printf("Impossible\nGraph is Unconnected\n\n");
else /* Otherwise, Print the Path */
path_print(path->next);
path_free(path);
return;
}
/***********************************************************
************************************************************
****
**** Depth First Search Function: Add the vertex to the
**** path list, and then if there are adjacent vertices
**** it calls itself on each one in turn, after
**** deleting the connecting edge (this insures that
**** it won't traverse that edge again). When there
**** are no more adjacent vertices, it returns. Note
**** that when it returns to the calling copy of
**** itself, the path pointer is in the appropriate
**** place for inserting the next sub-path (thus, there
**** is no need for splicing seperate lists together).
***/
void dfs(graph_ptr graph, int vertex, path_ptr path)
{
int next_ver; /* The Next Vertex to Traverse */
graph_ptr edge; /* The edge (adj list node) between this vertex and next */
path_add(path, vertex); /* Add this vertex to path list */
if(graph[vertex].adj == 0) return; /* Return if this is a Dead End */
while((edge=graph[vertex].next) != NULL) { /* For all Adj Vertices . . . */
next_ver = edge->adj;
graph_del(graph, edge); /* Delete Connecting Edge */
dfs(graph, next_ver, path->next); /* Search on Adj Vertex */
}
return;
}
/***********************************************************
************************************************************
****
**** Graph - Read Function: Reads a graph from the data
**** file. This function returns the number of
**** vertices in the graph. (Thus, when it returns a
**** zero, the calling function knows it has reached
**** the end of the data file.)
***/
int graph_read(file_ptr fp, graph_ptr *graph)
{
int i, j, num_ver, vertex, num_adj, adj;
/* Read Number of Vertices */
fscanf(fp, "%d ", &num_ver);
if(num_ver == 0) return(0);
/* Initialize Graph for the Right Number of Vertices */
*graph = graph_init(num_ver);
for(i=1; i<=num_ver; i++) { /* For Each Vertex . . . */
/* Read Vertex Number */
fscanf(fp, "%d ", &vertex);
if(vertex != i) error("Bad File Format\0");
/* Read Number of Adjacencies */
fscanf(fp, "%d ", &num_adj);
/* Read and Add to Graph the Adjancencies */
for(j=1; j<=num_adj; j++) {
fscanf(fp, "%d ", &adj);
graph_add(*graph, vertex, adj);
}
}
return(num_ver);
}
/***********************************************************
************************************************************
****
**** Graph - Init Function: Allocates and Initializes an
**** array of header nodes for the adjancency lists.
***/
graph_ptr graph_init(int num_ver)
{
int i;
graph_ptr temp;
/* Allocate the Array from 0 the Number of Vertices */
temp = (graph_ptr)calloc(num_ver+1, sizeof(struct graph_node));
if(!temp) error("Out of Memory\0");
/* Initialize Array w/ Null Values */
for(i=0; i<=num_ver; i++) {
temp[i].adj = 0;
temp[i].twin = NULL;
temp[i].prev = NULL;
temp[i].next = NULL;
}
return(temp);
}
/***********************************************************
************************************************************
****
**** Graph - Add Function: Adds a node to the adjacency
**** list for vertex, and also a TWIN node to the
**** adjacent nodes list, the twins are linked together
**** so that when one is accessed, the other can be
**** found easily (they both, after all, represent the
**** same edge).
***/
void graph_add(graph_ptr graph, int vertex, int adj)
{
/* Add Node to Vertex and Twin Node to Adjacent Vertex */
graph_add_node(&graph[vertex], adj);
graph_add_node(&graph[adj], vertex);
/* Link the Twin Nodes Together */
graph[vertex].next->twin = graph[adj].next;
graph[adj].next->twin = graph[vertex].next;
/* Increment the Number of Adjacencies at Each Node */
graph[vertex].adj++;
graph[adj].adj++;
/* Increment the Edge Count */
graph[0].adj++;
return;
}
/***********************************************************
************************************************************
****
**** Graph - Add Node Function: Adds a node to an
**** adjacency list. (Used by the Add function -- see
**** above.)
***/
void graph_add_node(graph_ptr list, int adj)
{
graph_ptr temp;
/* Allocate Node */
temp = (graph_ptr)malloc(sizeof(struct graph_node));
if(!temp) error("Out of Memory\0");
/* Link it into List and Initialize */
temp->adj = adj;
temp->twin = NULL;
temp->prev = list;
temp->next = list->next;
if(list->next) list->next->prev = temp;
list->next = temp;
return;
}
/***********************************************************
************************************************************
****
**** Graph - Delete Function: Deletes the node passed to
**** it by the calling function and also that nodes
**** twin.
***/
void graph_del(graph_ptr graph, graph_ptr node)
{
/* Decrement Number of Adjacencies at Each Vertex */
graph[node->adj].adj--;
graph[node->twin->adj].adj--;
/* Delete the Node and its Twin */
graph_del_node(node->twin);
graph_del_node(node);
/* Decrement Edge Counter */
graph[0].adj--;
return;
}
/***********************************************************
************************************************************
****
**** Graph - Delete Node Function: Deletes a node from
**** an adjacency list. (Used by the Delete function
**** -- see above.)
***/
void graph_del_node(graph_ptr node)
{
node->prev->next = node->next;
if(node->next) node->next->prev = node->prev;
free(node);
return;
}
/***********************************************************
************************************************************
****
**** Graph - Print Function: Prints the graph in
**** adjacency list format (Vertex (# of Adj): Adj
**** Vertices).
***/
void graph_print(graph_ptr graph, int num_ver)
{
int i;
graph_ptr j;
if(num_ver==0) {
printf("\nEmpty Graph\n");
return;
}
for(i=1; i<=num_ver; i++) {
printf("\nVertex %d (%d): ", i, graph[i].adj);
j = graph[i].next;
while(j) {
printf("%d ", j->adj);
j = j->next;
}
}
printf("\n\n");
return;
}
/***********************************************************
************************************************************
****
**** Graph - Free Function: Frees the memory used by a
**** graph.
***/
void graph_free(graph_ptr graph, int num_ver)
{
int i;
graph_ptr j, kill;
for(i=0; i<=num_ver; i++)
while((kill = graph[i].next) != NULL)
graph_del_node(kill);
free(graph);
return;
}
/***********************************************************
************************************************************
****
**** Path - Init Function: Creates the header node for
**** the Path linked list.
***/
path_ptr path_init(void)
{
path_ptr temp;
/* Allocate Space for Header Node */
temp = (path_ptr)malloc(sizeof(struct path_node));
if(!temp) error("Out of Memory");
/* Initialize w/ Null Values */
temp->vertex = 0;
temp->next = NULL;
return(temp);
}
/***********************************************************
************************************************************
****
**** Path - Add Function: Inserts a node into the Path
**** linked list.
***/
void path_add(path_ptr node, int vertex)
{
path_ptr temp;
/* Allocate Space for Node */
temp = (path_ptr)malloc(sizeof(struct path_node));
if(!temp) error("Out of Memory\0");
/* Link into List and Store Data */
temp->vertex = vertex;
temp->next = node->next;
node->next = temp;
return;
}
/***********************************************************
************************************************************
****
**** Path - Print Function: Prints the Path List,
**** formatting so that no line is longer than 72
**** characters.
***/
void path_print(path_ptr path)
{
int chars_printed;
/* Print First Vertex */
if(path) {
printf("%d%n", path->vertex, &chars_printed);
print_pos += chars_printed;
path = path->next;
}
/* Print remaining Vertices */
while(path) {
/* If Screen Position is anywhere but the left edge, Print comma */
if(print_pos) {
printf(", ");
print_pos += 2;
}
/* If Screen Position is at right edge, Start New Line */
if(print_pos > MAX_PRINT_POS) {
printf("\n");
print_pos = 0;
}
/* Print Vertex */
printf("%d%n", path->vertex, &chars_printed);
print_pos += chars_printed;
path = path->next;
}
printf("\n\n");
return;
}
/***********************************************************
************************************************************
****
**** Path - Free Function: Frees the memory used by the
**** Path linked list.
***/
void path_free(path_ptr path)
{
path_ptr i;
for(i=path; i != NULL; i=path) {
path = path->next;
free(i);
}
return;
}
/***********************************************************
************************************************************
****
**** Open File Function: Prompts the user for a filename
**** and then attempts to open that file. If a file of
**** that name can't be found (or another error occurs)
**** then program execution is terminated with an error
**** message.
***/
file_ptr open_file(void)
{
file_ptr fp;
char filename[80];
int i;
for(i=0;i<80;i++)
filename[i] = '\0';
printf("Data File: ");
scanf("%s", filename);
printf("\n");
if((fp=fopen(filename, "r")) == NULL)
error("Cannot Open File\0");
return(fp);
}
/***********************************************************
************************************************************
****
**** Print Header/Footer: Displays the title of program
**** and header and footer lines.
***/
void print_header(void)
{
printf("\n");
print_line(72, '=');
printf("Eulerian Circuit/Path Finder\n");
print_line(72, '=');
printf("\n");
return;
}
void print_footer(void)
{
print_line(72, '=');
return;
}
/***********************************************************
************************************************************
****
**** Error Function: Displays the given error message
**** and then immediately exits the program.
***/
void error(const char *message)
{
printf("\n");
printf("ERROR: ");
printf(message);
printf("\n");
exit(1);
}
/***********************************************************
************************************************************
****
**** Print Line Function: Displays a line of the
**** length and made of the specified character.
***/
void print_line(int length, char ch)
{
int i;
for(i=0; i