Instructions
Requirements and Specifications
Source Code
// Nelson Pham, nppham
// CSE101, PA#2
// Graph.c
// Graph.c file for implementing required functions for Graph ADT
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include "Graph.h"
// Color to define if a vertices exists or not
#define COLOR_WHITE ((char)0)
#define COLOR_GRAY ((char)1)
#define COLOR_BLACK ((char)2)
// Struct of Graph and attributes
struct GraphObj {
int order; // number of vertices
int size; // number of undirected edges
List* neighbors;
char* color;
int* parent;
int* distance;
int source;
};
// Creates a New graph
Graph newGraph(int n) {
Graph G = (Graph)malloc(sizeof(struct GraphObj));
G->order = n;
G->size = 0;
G->neighbors = (List*)malloc(sizeof(List) * (n + 1)); // arrays of length n + 1
G->color = (char*)malloc(sizeof(char) * (n + 1));
G->parent = (int*) malloc(sizeof(int) * (n + 1));
G->distance = (int*) malloc(sizeof(int) * (n + 1));
for (int i = 1; i <= n; i ++) {
G->neighbors[i] = newList();
G->color[i] = COLOR_WHITE;
G->parent[i] = NIL;
G->distance[i] = INF;
}
G->source = NIL;
return G;
}
// Free all memory associated with graph
void freeGraph(Graph* pG) {
for (int i = 1; i <= (*pG)->order; i ++) {
List neighbors = (*pG)->neighbors[i];
freeList(&neighbors);
}
free((*pG)->neighbors);
free((*pG)->color);
free((*pG)->parent);
free((*pG)->distance);
free(*pG);
*pG = NULL;
}
// Get number of vertices
int getOrder(Graph G) {
return G->order;
}
// Get the number of edges
int getSize(Graph G) {
return G->size;
}
// Get the source of graph
int getSource(Graph G) {
return G->source;
}
// Get the parent of vertex u
int getParent(Graph G, int u) {
if (u < 1 || u > getOrder(G)) {
printf("getParent ERROR: u < 1 || u > G->getOrder()\n");
exit(EXIT_FAILURE);
}
return G->parent[u];
}
// Get the distance from recent source to vertex u
int getDist(Graph G, int u) {
if (u < 1 || u > getOrder(G)) {
printf("getDist ERROR: u < 1 || u > G->getOrder()\n");
exit(EXIT_FAILURE);
}
return G->distance[u];
}
// Get vertices of shortest parts in G from source to u
void getPath(List L, Graph G, int u) {
if (getSource(G) == NIL) {
printf("getPath ERROR: getSource(G) == NIL\n");
exit(EXIT_FAILURE);
}
if (u < 1 || u > getOrder(G)) {
printf("getPath ERROR: u < 1 || u > G->getOrder()\n");
exit(EXIT_FAILURE);
}
if (G->color[u] == COLOR_WHITE) {
append(L, NIL);
return;
}
List P = newList();
int x = u;
while (x != G->source) {
prepend(P, x);
x = getParent(G, x);
}
prepend(P, G->source);
moveFront(P);
while (index(P) >= 0) {
x = get(P);
append(L, x);
moveNext(P);
}
freeList(&P);
}
// Deletes all edges of G, restoring to no edge state
void makeNull(Graph G) {
int n = G->order;
freeGraph(&G);
G = newGraph(n);
}
// Adds directed edge without modifying size, addEdge and addArc use
// this and modify size differently below
void addArcHelper(Graph G, int u, int v) {
if (u < 1 || u > getOrder(G)) {
printf("addArc ERROR: u < 1 || u > G->getOrder()\n");
exit(EXIT_FAILURE);
}
if (v < 1 || v > getOrder(G)) {
printf("addArc ERROR: v < 1 || v > G->getOrder()\n");
exit(EXIT_FAILURE);
}
List neighbors = G->neighbors[u];
moveFront(neighbors);
while (index(neighbors) >= 0) {
int k = get(neighbors);
if (k > v) {
insertBefore(neighbors, v);
return;
} else if (k == v) {
return;
}
moveNext(neighbors);
}
append(neighbors, v);
}
// Adds edge joining u to v and vice versa
void addEdge(Graph G, int u, int v) {
if (u < 1 || u > getOrder(G)) {
printf("addEdge ERROR: u < 1 || u > G->getOrder()\n");
exit(-1);
}
if (v < 1 || v > getOrder(G)) {
printf("addEdge ERROR: v < 1 || v > G->getOrder()\n");
exit(-1);
}
addArcHelper(G, u, v);
addArcHelper(G, v, u);
G->size++;
}
// Inserts new directed edge from u to v, but not other way around
void addArc(Graph G, int u, int v) {
addArcHelper(G, u, v);
G->size++;
}
void BFS(Graph G, int s) {
if (s < 1 || s > getOrder(G)) {
printf("BFS ERROR: s < 1 || s > G->getOrder()\n");
exit(-1);
}
// initialize vertices
for (int i = 1; i <= G->order; i ++) {
if (i == s) {
G->color[i] = COLOR_GRAY;
G->distance[i] = 0;
G->parent[i] = NIL;
} else {
G->color[i] = COLOR_WHITE;
G->distance[i] = INF;
G->parent[i] = NIL;
}
}
// initialize source
G->source = s;
// initialize Q
List Q = newList();
append(Q, s);
// loop and expand frontier
while (length(Q) != 0) {
moveFront(Q);
int x = get(Q);
deleteFront(Q);
List neighbors = G->neighbors[x];
moveFront(neighbors);
while (index(neighbors) >= 0) {
int y = get(neighbors);
if (G->color[y] == COLOR_WHITE) {
G->color[y] = COLOR_GRAY;
G->distance[y] = G->distance[x] + 1;
G->parent[y] = x;
append(Q, y);
}
moveNext(neighbors);
}
G->color[x] = COLOR_BLACK;
}
freeList(&Q);
}
void printGraph(FILE* out, Graph G) {
for (int i = 1; i <= G->order; i ++) {
fprintf(out, "%d:", i);
List neighbors = G->neighbors[i];
moveFront(neighbors);
while (index(neighbors) >= 0) {
int v = get(neighbors);
fprintf(out, " %d", v);
moveNext(neighbors);
}
fprintf(out, "\n");
}
}