Homework #8

graph.c

/*
 * graph.c
 */
#include <stdlib.h>
#include <string.h>

#include "graph.h"
#include "list.h"
#include "set.h"

void graph_init(Graph *graph, int(*match)(const void *key1, const void *key2),
        void(*destroy)(void *data)) {

    /* Initialize the graph. */
    graph->vcount = 0;
    graph->ecount = 0;
    graph->match = match;
    graph->destroy = destroy;

    /* Initialize the list of adjacency-list structures. */
    list_init(&graph->adjlists, NULL);
}

void graph_destroy(Graph *graph) {

    AdjList *adjlist;

    /* Remove each adjacency-list structure and destroy its adjacency list. */
    while (list_size(&graph->adjlists) > 0) {

        if (list_rem_next(&graph->adjlists, NULL, (void **) &adjlist) == 0) {

            set_destroy(&adjlist->adjacent);

            if (graph->destroy != NULL)
                graph->destroy(adjlist->vertex);

            free(adjlist);
        }
    }

    /* Destroy the list of adjacency-list structures, which is now empty. */
    list_destroy(&graph->adjlists);

    /* No operations are allowed now, but clear the structure as a
     * precaution. */
    memset(graph, 0, sizeof(Graph));
}

int graph_ins_vertex(Graph *graph, const void *data) {

    ListElmt *element;
    AdjList *adjlist;
    int retval;

    /* Do not allow the insertion of duplicate vertices. */
    for (element = list_head(&graph->adjlists); element != NULL; element
            = list_next(element)) {

        if (graph->match(data, ((AdjList *) list_data(element))->vertex))
            return 1;
    }

    /* Insert the vertex. */
    if ((adjlist = (AdjList *) malloc(sizeof(AdjList))) == NULL)
        return -1;

    adjlist->vertex = (void *) data;
    set_init(&adjlist->adjacent, graph->match, graph->destroy);

    if ((retval = list_ins_next(&graph->adjlists, list_tail(&graph->adjlists),
            adjlist)) != 0) {

        return retval;
    }

    /* Adjust the vertex count to account for the inserted vertex. */
    graph->vcount++;

    return 0;
}

int graph_ins_edge(Graph *graph, const void *data1, const void *data2) {

    ListElmt *element;
    int retval;

    /* Do not allow insertion of an edge without both its vertices in the
     * graph. */
    for (element = list_head(&graph->adjlists); element != NULL; element
            = list_next(element)) {

        if (graph->match(data2, ((AdjList *) list_data(element))->vertex))
            break;
    }

    if (element == NULL)
        return -1;

    for (element = list_head(&graph->adjlists); element != NULL; element
            = list_next(element)) {

        if (graph->match(data1, ((AdjList *) list_data(element))->vertex))
            break;
    }

    if (element == NULL)
        return -1;

    /* Insert the second vertex into the adjacency list of the first vertex. */
    if ((retval
            = set_insert(&((AdjList *) list_data(element))->adjacent, data2))
            != 0) {

        return retval;
    }

    /* Adjust the edge count to account for the inserted edge. */
    graph->ecount++;

    return 0;
}

int graph_rem_vertex(Graph *graph, void **data) {

    ListElmt *element, *temp, *prev;
    AdjList *adjlist;
    int found;

    /* Traverse each adjacency list and the vertices it contains. */
    prev = NULL;
    found = 0;

    for (element = list_head(&graph->adjlists); element != NULL; element
            = list_next(element)) {

        /* Do not allow removal of the vertex if it is in an adjacency list. */
        if (set_is_member(&((AdjList *) list_data(element))->adjacent, *data))
            return -1;

        /* Keep a pointer to the vertex to be removed. */
        if (graph->match(*data, ((AdjList *) list_data(element))->vertex)) {

            temp = element;
            found = 1;
        }

        /* Keep a pointer to the vertex before the vertex to be removed. */
        if (!found)
            prev = element;
    }

    /* Return if the vertex was not found. */
    if (!found)
        return -1;

    /* Do not allow removal of the vertex if its adjacency list is not empty. */
    if (set_size(&((AdjList *)list_data(temp))->adjacent) > 0)
        return -1;

    /* Remove the vertex. */
    if (list_rem_next(&graph->adjlists, prev, (void **) &adjlist) != 0)
        return -1;

    /* Free the storage allocated by the abstract data type. */
    *data = adjlist->vertex;
    free(adjlist);

    /* Adjust the vertex count to account for the removed vertex. */
    graph->vcount--;

    return 0;
}

int graph_rem_edge(Graph *graph, void *data1, void **data2) {

    ListElmt *element;

    /* Locate the adjacency list for the first vertex. */
    for (element = list_head(&graph->adjlists); element != NULL; element
            = list_next(element)) {

        if (graph->match(data1, ((AdjList *) list_data(element))->vertex))
            break;
    }

    if (element == NULL)
        return -1;

    /* Remove the second vertex from the adjacency list of the first vertex. */
    if (set_remove(&((AdjList *) list_data(element))->adjacent, data2) != 0)
        return -1;

    /* Adjust the edge count to account for the removed edge. */
    graph->ecount--;

    return 0;
}

int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist) {

    ListElmt *element, *prev;

    /* Locate the adjacency list for the vertex. */
    prev = NULL;

    for (element = list_head(&graph->adjlists); element != NULL; element
            = list_next(element)) {

        if (graph->match(data, ((AdjList *) list_data(element))->vertex))
            break;

        prev = element;
    }

    /* Return if the vertex was not found. */
    if (element == NULL)
        return -1;

    /* Pass back the adjacency list for the vertex. */
    *adjlist = list_data(element);

    return 0;
}

int graph_is_adjacent(const Graph *graph, const void *data1, const void *data2) {

    ListElmt *element, *prev;

    /* Locate the adjacency list of the first vertex. */
    prev = NULL;

    for (element = list_head(&graph->adjlists); element != NULL; element
            = list_next(element)) {

        if (graph->match(data1, ((AdjList *) list_data(element))->vertex))
            break;

        prev = element;
    }

    /* Return if the first vertex was not found. */
    if (element == NULL)
        return 0;

    /* Return whether the second vertex is in the adjacency list of the first. */
    return set_is_member(&((AdjList *) list_data(element))->adjacent, data2);
}

graph.h

/*
 * graph.h
 */
#ifndef GRAPH_H
#define GRAPH_H

#include <stdlib.h>

#include "list.h"
#include "set.h"

/* Define a structure for adjacency lists. */
typedef struct AdjList_ {

    void *vertex;
    Set adjacent;

} AdjList;

/* Define a structure for graphs. */
typedef struct Graph_ {

    int vcount;
    int ecount;

    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);

    List adjlists;

} Graph;

/* Define colors for vertices in graphs. */
typedef enum VertexColor_ {
    white, gray, black
} VertexColor;

/* Public Interface */
void graph_init(Graph *graph, int(*match)(const void *key1, const void *key2),
        void(*destroy)(void *data));

void graph_destroy(Graph *graph);

int graph_ins_vertex(Graph *graph, const void *data);

int graph_ins_edge(Graph *graph, const void *data1, const void *data2);

int graph_rem_vertex(Graph *graph, void **data);

int graph_rem_edge(Graph *graph, void *data1, void **data2);

int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist);

int graph_is_adjacent(const Graph *graph, const void *data1, const void *data2);

#define graph_adjlists(graph) ((graph)->adjlists)

#define graph_vcount(graph) ((graph)->vcount)

#define graph_ecount(graph) ((graph)->ecount)

#endif

hw8.c

#include <iso646.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <alloca.h>

#include "graph.h"

#define List_each(var, list) (var = list_head(list); var != NULL; var = list_next(var))
#define Set_each(var, list) List_each(var, list)
#define array_length(array) (sizeof(array) / sizeof(*(array)))

typedef struct
{
	const char index;
	bool     visited;
} Room;

static Room rooms[] =
{
//	  ID  Visited
	{ 'A', false },
	{ 'B', false },
	{ 'C', false },
	{ 'D', false },
	{ 'E', false },
	{ 'F', false },
	{ 'G', false }
};

static int     rooms_match(const void* room1, const void* room2)
{
	return room1 == room2 ? 1 : 0;
}

static Room*       room_at(char index)
{
	return rooms + (index - 'A');
}

static void    rooms_reset( )
{
	for (unsigned i = 0; i < array_length(rooms); ++i)
	{
		rooms[i].visited = false;
	}
}

Graph*        create_maze1(Graph* this)
{
	graph_init(this, rooms_match, NULL);

	graph_ins_vertex(this, room_at('A') );
	graph_ins_vertex(this, room_at('B') );
	graph_ins_vertex(this, room_at('C') );
	graph_ins_vertex(this, room_at('D') );
	graph_ins_vertex(this, room_at('E') );
	graph_ins_vertex(this, room_at('F') );
	graph_ins_vertex(this, room_at('G') );

	graph_ins_edge(this, room_at('A'), room_at('C') );
	graph_ins_edge(this, room_at('C'), room_at('F') );
	graph_ins_edge(this, room_at('D'), room_at('A') );
	graph_ins_edge(this, room_at('D'), room_at('B') );
	graph_ins_edge(this, room_at('D'), room_at('E') );
	graph_ins_edge(this, room_at('D'), room_at('G') );
	graph_ins_edge(this, room_at('F'), room_at('G') );
	graph_ins_edge(this, room_at('G'), room_at('E') );
	return this;
}

Graph*        create_maze2(Graph* this)
{
	graph_init(this, rooms_match, NULL);

	graph_ins_vertex(this, room_at('A') );
	graph_ins_vertex(this, room_at('B') );
	graph_ins_vertex(this, room_at('C') );
	graph_ins_vertex(this, room_at('D') );
	graph_ins_vertex(this, room_at('E') );
	graph_ins_vertex(this, room_at('F') );
	graph_ins_vertex(this, room_at('G') );

	graph_ins_edge(this, room_at('A'), room_at('C') );
	graph_ins_edge(this, room_at('B'), room_at('D') );
	graph_ins_edge(this, room_at('C'), room_at('F') );
	graph_ins_edge(this, room_at('D'), room_at('A') );
	graph_ins_edge(this, room_at('E'), room_at('G') );

	return this;
}

static int search_in(const Graph* graph, Room* room, const Room* exit)
{
	static const int found = 1;

	if (room->visited)
	{
		return not found;
	}
	else
	{
		room->visited = true;

		if (graph_is_adjacent(graph, room, exit) == found)
		{
			return found;
		}
		else
		{
			AdjList*  adjlist;
			ListElmt* element;

			if (graph_adjlist(graph, room, &adjlist) == -1)
			{
				return not found;
			}
			else for Set_each(element, &adjlist->adjacent)
			{
				Room* adjacent_room = element->data;

				if (search_in(graph, adjacent_room, exit) == found)
				{
					return found;
				}
			}
			return not found;
		}
	}
}


int isExitReachable(const Graph* graph, char entrance_id, char exit_id)
{
	Room* entrance = room_at(entrance_id);
	Room*     exit = room_at(exit_id);

        rooms_reset();
	return search_in(graph, entrance, exit);
}

int main(void)
{
	Graph* maze1 = create_maze1(alloca(sizeof(*maze1)));
	Graph* maze2 = create_maze2(alloca(sizeof(*maze2)));

	assert(isExitReachable(maze1, 'A', 'G') ==  true);
        assert(isExitReachable(maze2, 'A', 'G') == false);

	assert(isExitReachable(maze2, 'E', 'G') ==  true);
        assert(isExitReachable(maze2, 'B', 'F') ==  true);

	graph_destroy(maze1);
	graph_destroy(maze2);
	return EXIT_SUCCESS;
}

list.c

/*
 * list.c
 */
#include <stdlib.h>
#include <string.h>

#include "list.h"

void list_init(List *list, void (*destroy)(void *data)) {
    /* Initialize the list */
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
}

void list_destroy(List *list)
{
    void *data;

    /* Remove each element */
    while (list_size(list) > 0) {
        if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy !=
                NULL) {
            /* Call a user-defined function to free dynamically allocated
               data. */
            list->destroy(data);
        }
    }

    /* No operations are allowed now, but clear the structure as a
       precaution. */
    memset(list, 0, sizeof(List));
}

int list_ins_next(List *list, ListElmt *element, const void *data)
{
    ListElmt *new_element;

    /* Allocate storage for the element. */
    if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
        return -1;

    /* Insert the element into the list. */
    new_element->data = (void *)data;
    if (element == NULL) {
        /* Handle insertion at the head of the list. */
        if (list_size(list) == 0)
            list->tail = new_element;
        new_element->next = list->head;
        list->head = new_element;
    }
    else {
        /* Handle insertion somewhere other than at the head. */
        if (element->next == NULL)
            list->tail = new_element;
        new_element->next = element->next;
        element->next = new_element;
    }

    /*  Adjust the size of the list to account for the inserted element. */
    list->size++;

    return 0;
}

int list_rem_next(List *list, ListElmt *element, void **data)
{
    ListElmt *old_element;

    /* Do not allow removal from an empty list. */
    if (list_size(list) == 0)
        return -1;

    /* Remove the element from the list. */
    if (element == NULL) {
        /* Handle removal from the head of the list. */
        *data = list->head->data;
        old_element = list->head;
        list->head = list->head->next;

        if (list_size(list) == 1)
            list->tail = NULL;
    }
    else {
        /* Handle removal from somewhere other than the head. */
        if (element->next == NULL)
            return -1;

        *data = element->next->data;
        old_element = element->next;
        element->next = element->next->next;

        if (element->next == NULL)
            list->tail = element;
    }

    /* Free the storage allocated by the abstract data type. */
    free(old_element);

    /* Adjust the size of the list to account for the removed element. */
    list->size--;

    return 0;
}

list.h

/*
 * list.h
 */
#ifndef LIST_H
#define LIST_H

#include <stdlib.h>

/*
 * Singly-linked list element
 */
typedef struct ListElmt_
{
    void               *data;
    struct ListElmt_   *next;
} ListElmt;

/*
 * Singly-linked list
 */
typedef struct List_
{
    int                size;

    int                (*match)(const void *key1, const void *key2);
    void               (*destroy)(void *data);

    ListElmt           *head;
    ListElmt           *tail;
} List;

/*
 * Public interface
 */
void list_init(List *list, void (*destroy)(void *data));

void list_destroy(List *list);

int list_ins_next(List *list, ListElmt *element, const void *data);

int list_rem_next(List *list, ListElmt *element, void **data);

#define list_size(list) ((list)->size)

#define list_head(list) ((list)->head)

#define list_tail(list) ((list)->tail)

#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)

#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

#define list_data(element) ((element)->data)

#define list_next(element) ((element)->next)

#endif

set.c

/*
 * set.c
 */
#include <stdlib.h>
#include <string.h>

#include "list.h"
#include "set.h"

void set_init(Set *set, int (*match)(const void *key1, const void *key2),
   void (*destroy)(void *data))
{
    /* Initialize the set. */
    list_init(set, destroy);
    set->match = match;

    return;
}

int set_insert(Set *set, const void *data)
{
    /* Do not allow the insertion of duplicates. */
    if (set_is_member(set, data))
        return 1;

    /* Insert the data. */
    return list_ins_next(set, list_tail(set), data);
}

int set_remove(Set *set, void **data)
{
    ListElmt *member,
             *prev;

    /* Find the member to remove. */
    prev = NULL;
    for (member = list_head(set); member != NULL; member = list_next(member)) {
        if (set->match(*data, list_data(member)))
            break;
        prev = member;
    }

    /* Return if the member was not found. */
    if (member == NULL)
        return -1;

    /* Remove the member. */
    return list_rem_next(set, prev, data);
}

int set_union(Set *setu, const Set *set1, const Set *set2)
{
    ListElmt *member;
    void *data;

    /* Initialize the set for the union. */
    set_init(setu, set1->match, NULL);

    /* Insert the members of the first set. */
    for (member = list_head(set1); member != NULL;
            member = list_next(member)) {

        data = list_data(member);

        if (list_ins_next(setu, list_tail(setu), data) != 0) {
            set_destroy(setu);
            return -1;
        }
    }

    /* Insert the members of the second set. */
    for (member = list_head(set2); member != NULL;
            member = list_next(member)) {

        if (set_is_member(set1, list_data(member))) {
            /* Do not allow the insertion of duplicates. */
            continue;
        }
        else {
            data = list_data(member);

            if (list_ins_next(setu, list_tail(setu), data) != 0) {
                set_destroy(setu);
                return -1;
            }
        }
    }

    return 0;
}

int set_intersection(Set *seti, const Set *set1, const Set *set2)
{
    ListElmt *member;
    void *data;

    /* Initialize the set for the intersection. */
    set_init(seti, set1->match, NULL);

    /* Insert the members present in both sets. */
    for (member = list_head(set1); member != NULL;
            member = list_next(member)) {

        if (set_is_member(set2, list_data(member))) {
            data = list_data(member);

            if (list_ins_next(seti, list_tail(seti), data) != 0) {
                set_destroy(seti);
                return -1;
            }
        }
    }

    return 0;
}

int set_difference(Set *setd, const Set *set1, const Set *set2) {
    ListElmt *member;
    void *data;

    /* Initialize the set for the difference. */
    set_init(setd, set1->match, NULL);

    /* Insert the members from set1 not in set2. */
    for (member = list_head(set1); member != NULL;
            member = list_next(member)) {

        if (!set_is_member(set2, list_data(member))) {
            data = list_data(member);

            if (list_ins_next(setd, list_tail(setd), data) != 0) {
                set_destroy(setd);
                return -1;
            }
        }
    }

    return 0;
}

int set_is_member(const Set *set, const void *data) {
    ListElmt *member;

    /* Determine if the data is a member of the set. */
    for (member = list_head(set); member != NULL; member = list_next(member)) {
        if (set->match(data, list_data(member)))
            return 1;
    }

    return 0;
}

int set_is_subset(const Set *set1, const Set *set2) {
    ListElmt *member;

    /* Do a quick test to rule out some cases. */
    if (set_size(set1) > set_size(set2))
        return 0;

    /* Determine if set1 is a subset of set2. */
    for (member = list_head(set1); member != NULL; member = list_next(member)) {
        if (!set_is_member(set2, list_data(member)))
            return 0;
    }

    return 1;
}

int set_is_equal(const Set *set1, const Set *set2) {
    /* Do a quick test to rule out some cases. */
    if (set_size(set1) != set_size(set2))
        return 0;

    /* Sets of the same size are equal if they are subsets. */
    return set_is_subset(set1, set2);
}

set.h

/*
 * set.h
 */
#ifndef SET_H
#define SET_H

#include <stdlib.h>

#include "list.h"

/*
 * Implement sets as linked lists.
 */
typedef List Set;

/*
 * Public Interface
 */
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
   void (*destroy)(void *data));

#define set_destroy list_destroy

int set_insert(Set *set, const void *data);

int set_remove(Set *set, void **data);

int set_union(Set *setu, const Set *set1, const Set *set2);

int set_intersection(Set *seti, const Set *set1, const Set *set2);

int set_difference(Set *setd, const Set *set1, const Set *set2);

int set_is_member(const Set *set, const void *data);

int set_is_subset(const Set *set1, const Set *set2);

int set_is_equal(const Set *set1, const Set *set2);

#define set_size(set) ((set)->size)

#endif