# Implement Graph Adts in C Assignment Solution.

## Instructions

Objective
Write a program to implement graph ADTs in C.

## 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");   } }```