Advertisement
Pweebs

Graph.c

Nov 23rd, 2019
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.12 KB | None | 0 0
  1. // Jevin Olano
  2. // jolano
  3. // CSE 101
  4. // November 22, 2019
  5. // Graph.c - implementation file for List ADT
  6.  
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <assert.h>
  10. #include "Graph.h"
  11. #include "List.h"
  12.  
  13. // "constant macros"
  14. #define WHITE 0
  15. #define GRAY 1
  16. #define BLACK 2
  17.  
  18. // Constructors & Destructors ---------------------------
  19.  
  20. // newGraph()
  21. // Creates and returns a new empty Graph
  22. Graph newGraph(int n) {
  23.  
  24. Graph graph = malloc(sizeof(GraphObj));
  25. graph->adjacency = calloc((n + 1), sizeof(List));
  26. graph->color = calloc((n + 1), sizeof(int));
  27. graph->parent = calloc((n + 1), sizeof(int));
  28. graph->distance = calloc((n + 1), sizeof(int));
  29.  
  30. for (int i = 0; i < (n + 1); i++) {
  31. graph->adjacency[i] = newList();
  32. graph->color[i] = WHITE;
  33. graph->parent[i] = NIL;
  34. graph->distance[i] = INF;
  35. }
  36.  
  37. graph->order = n;
  38. graph->size = 0;
  39. graph->source = NIL;
  40.  
  41. return graph;
  42. }
  43.  
  44. // freeGraph()
  45. // Frees all heap memory associated with *pG, and sets *pG to null
  46. void freeGraph(Graph* pG) {
  47. Graph G = *pG;
  48. freeList(G->adjacency);
  49.  
  50. for (int i = 0; i <= getOrder(G); i++) {
  51. freeList(&(G->adjacency[i]));
  52. }
  53.  
  54. free(G->adjacency);
  55. free(G->color);
  56. free(G->parent);
  57. free(G->distance);
  58.  
  59. free(*pG);
  60. *pG = NULL;
  61. }
  62.  
  63. // Access Functions -------------------------------------
  64.  
  65. // getOrder()
  66. // returns order of G
  67. int getOrder(Graph G) {
  68. if (G == NULL) {
  69. printf("Graph error: cannot call getOrder on NULL Graph reference\n");
  70. exit(1);
  71. }
  72. return G->order;
  73. }
  74.  
  75. // getSize()
  76. // returns size of G
  77. int getSize(Graph G) {
  78. if (G == NULL) {
  79. printf("Graph error: cannot call getSize on NULL Graph reference\n");
  80. exit(1);
  81. }
  82. return G->size;
  83. }
  84.  
  85. // getSource()
  86. // returns the source vertex most recently used in BFS(), or NIL if BFS() hasn't been called
  87. int getSource(Graph G) {
  88. if (G == NULL) {
  89. printf("Graph error: cannot call getSource on NULL Graph reference\n");
  90. exit(1);
  91. }
  92. return G->source;
  93. }
  94.  
  95. // getParent()
  96. int getParent(Graph G, int u) {
  97. if (G == NULL) {
  98. printf("Graph error: cannot call getParent on NULL Graph reference\n");
  99. exit(1);
  100. }
  101. if (!(1 <= u && u <= getOrder(G))) {
  102. printf("Graph error: cannot call getParent if value 'u' is out of bounds\n");
  103. exit(1);
  104. }
  105. return G->parent[u];
  106. }
  107.  
  108. // getDist()
  109. int getDist(Graph G, int u) {
  110. if (G == NULL) {
  111. printf("Graph error: cannot call getDist on NULL Graph reference\n");
  112. exit(1);
  113. }
  114. if (!(1 <= u && u <= getOrder(G))) {
  115. printf("Graph error: cannot call getDist if value 'u' is out of bounds\n");
  116. exit(1);
  117. }
  118. if (getSource(G) == NIL) {
  119. return INF;
  120. }
  121. return G->distance[u];
  122. }
  123.  
  124. // getPath()
  125. void getPath(List L, Graph G, int u) {
  126. if (G == NULL) {
  127. printf("Graph error: cannot call getPath on NULL Graph reference\n");
  128. }
  129. if (!(1 <= u && u <= getOrder(G))) {
  130. printf("Graph error: cannot call getPath if value 'u' is out of bounds\n");
  131. exit(1);
  132. }
  133. if (u == getSource(G)) {
  134. append(L, getSource(G)); // appends source of G
  135. } else if (G->parent[u] == NIL) {
  136. append(L, NIL); // if the parent of the vertex is NIL, append NIL to path
  137. } else {
  138. getPath(L, G, G->parent[u]);
  139. append(L, u);
  140. }
  141. }
  142.  
  143. // Manipulation Procedures ------------------------------
  144.  
  145. // makeNull()
  146. // deletes all edges of G, restoring it to its original (no edge) state
  147. void makeNull(Graph G) {
  148. if (G == NULL) {
  149. printf("Graph error: cannot call makeNull on NULL Graph reference\n");
  150. }
  151. // we want to clear both graph + adjacency lists within the graph
  152. for (int i = 0; i < getOrder(G); i++) {
  153. clear(G->adjacency[i]);
  154. }
  155. G->size = 0; // no more edges = size is 0
  156. }
  157.  
  158. // sortEdge()
  159. // helper method for addEdge() and addArc()
  160. // InsertionSort ish
  161. void sortEdge(List list, int v) {
  162. if (list == NULL) {
  163. printf("List error: cannot call sortEdge on NULL List reference\n");
  164. }
  165. if (length(list) == 0) {
  166. append(list, v);
  167. return; // add and return
  168. }
  169. moveFront(list);
  170. while (index(list) != -1) {
  171. if (v < get(list)) {
  172. insertBefore(list, v);
  173. break;
  174. }
  175. moveNext(list);
  176. }
  177. if (index(list) == -1) {
  178. append(list, v);
  179. }
  180. }
  181.  
  182. // addEdge()
  183. // pre: both u and v are between 1 and getOrder(G)
  184. void addEdge(Graph G, int u, int v) {
  185. if (G == NULL) {
  186. printf("Graph error: cannot call addEdge on NULL Graph reference\n");
  187. }
  188. sortEdge(G->adjacency[u], v);
  189. sortEdge(G->adjacency[v], u);
  190. G->size++;
  191. }
  192.  
  193. // addArc()
  194. // pre: both u and v are between 1 and getOrder(G)
  195. void addArc(Graph G, int u, int v) {
  196. if (G == NULL) {
  197. printf("Graph error: cannot call addArc on NULL Graph reference\n");
  198. }
  199. sortEdge(G->adjacency[u], v);
  200. G->size++;
  201. }
  202.  
  203. // BFS()
  204. // runs the BFS algorithm on the Graph G with source s,
  205. // setting the color, distance, parent, and source fields of G accordingly
  206. void BFS(Graph G, int s) {
  207.  
  208. for (int i = 0; i < getOrder(G); i++) {
  209. if (s != getSource(G)) {
  210. G->color = WHITE;
  211. G->distance[i] = INF;
  212. G->parent[i] = NIL;
  213. }
  214. }
  215.  
  216. G->source = s;
  217.  
  218. G->color[s] = GRAY; // discover the source S
  219. G->distance[s] = 0;
  220. G->parent[s] = NIL;
  221. List list = newList();
  222. append(list, s); // equivalent to enqueue
  223. while (length(list) > 0) {
  224.  
  225. // equivalent to dequeue
  226. int x = front(list);
  227. deleteFront(list);
  228.  
  229. List getAdjacency = G->adjacency[x];
  230. moveFront(getAdjacency);
  231.  
  232. while (index(getAdjacency) != -1) {
  233. int y = get(getAdjacency);
  234. if (G->color[y] == WHITE) { // y is undiscovered
  235. G->color[y] = GRAY; // discover y
  236. G->distance[y] = G->distance[x] + 1;
  237. G->parent[y] = x;
  238. append(list, y);
  239. }
  240. moveNext(getAdjacency);
  241. }
  242. G->color[x] = BLACK; // finish x
  243. }
  244. freeList(&list);
  245. }
  246.  
  247. // Other Operations -------------------------------------
  248.  
  249. // printGraph()
  250. // prints the adjacency list representation of G to the file pointed to by "out"
  251. void printGraph(FILE* out, Graph G) {
  252. if (G == NULL) {
  253. printf("Graph error: cannot call printGraph on NULL Graph reference\n");
  254. exit(1);
  255. }
  256. for (int i = 1; i <= getOrder(G); i++) {
  257. List L = G->adjacency[i];
  258. fprintf(out, "%d:", i);
  259. moveFront(L);
  260. while (index(L) != -1) {
  261. fprintf(out, " %d", get(L));
  262. }
  263. fprintf(out, "\n");
  264. }
  265. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement