Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Jevin Olano
- // jolano
- // CSE 101
- // November 22, 2019
- // Graph.c - implementation file for List ADT
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- #include "Graph.h"
- #include "List.h"
- // "constant macros"
- #define WHITE 0
- #define GRAY 1
- #define BLACK 2
- // Constructors & Destructors ---------------------------
- // newGraph()
- // Creates and returns a new empty Graph
- Graph newGraph(int n) {
- Graph graph = malloc(sizeof(GraphObj));
- graph->adjacency = calloc((n + 1), sizeof(List));
- graph->color = calloc((n + 1), sizeof(int));
- graph->parent = calloc((n + 1), sizeof(int));
- graph->distance = calloc((n + 1), sizeof(int));
- for (int i = 0; i < (n + 1); i++) {
- graph->adjacency[i] = newList();
- graph->color[i] = WHITE;
- graph->parent[i] = NIL;
- graph->distance[i] = INF;
- }
- graph->order = n;
- graph->size = 0;
- graph->source = NIL;
- return graph;
- }
- // freeGraph()
- // Frees all heap memory associated with *pG, and sets *pG to null
- void freeGraph(Graph* pG) {
- Graph G = *pG;
- freeList(G->adjacency);
- for (int i = 0; i <= getOrder(G); i++) {
- freeList(&(G->adjacency[i]));
- }
- free(G->adjacency);
- free(G->color);
- free(G->parent);
- free(G->distance);
- free(*pG);
- *pG = NULL;
- }
- // Access Functions -------------------------------------
- // getOrder()
- // returns order of G
- int getOrder(Graph G) {
- if (G == NULL) {
- printf("Graph error: cannot call getOrder on NULL Graph reference\n");
- exit(1);
- }
- return G->order;
- }
- // getSize()
- // returns size of G
- int getSize(Graph G) {
- if (G == NULL) {
- printf("Graph error: cannot call getSize on NULL Graph reference\n");
- exit(1);
- }
- return G->size;
- }
- // getSource()
- // returns the source vertex most recently used in BFS(), or NIL if BFS() hasn't been called
- int getSource(Graph G) {
- if (G == NULL) {
- printf("Graph error: cannot call getSource on NULL Graph reference\n");
- exit(1);
- }
- return G->source;
- }
- // getParent()
- int getParent(Graph G, int u) {
- if (G == NULL) {
- printf("Graph error: cannot call getParent on NULL Graph reference\n");
- exit(1);
- }
- if (!(1 <= u && u <= getOrder(G))) {
- printf("Graph error: cannot call getParent if value 'u' is out of bounds\n");
- exit(1);
- }
- return G->parent[u];
- }
- // getDist()
- int getDist(Graph G, int u) {
- if (G == NULL) {
- printf("Graph error: cannot call getDist on NULL Graph reference\n");
- exit(1);
- }
- if (!(1 <= u && u <= getOrder(G))) {
- printf("Graph error: cannot call getDist if value 'u' is out of bounds\n");
- exit(1);
- }
- if (getSource(G) == NIL) {
- return INF;
- }
- return G->distance[u];
- }
- // getPath()
- void getPath(List L, Graph G, int u) {
- if (G == NULL) {
- printf("Graph error: cannot call getPath on NULL Graph reference\n");
- }
- if (!(1 <= u && u <= getOrder(G))) {
- printf("Graph error: cannot call getPath if value 'u' is out of bounds\n");
- exit(1);
- }
- if (u == getSource(G)) {
- append(L, getSource(G)); // appends source of G
- } else if (G->parent[u] == NIL) {
- append(L, NIL); // if the parent of the vertex is NIL, append NIL to path
- } else {
- getPath(L, G, G->parent[u]);
- append(L, u);
- }
- }
- // Manipulation Procedures ------------------------------
- // makeNull()
- // deletes all edges of G, restoring it to its original (no edge) state
- void makeNull(Graph G) {
- if (G == NULL) {
- printf("Graph error: cannot call makeNull on NULL Graph reference\n");
- }
- // we want to clear both graph + adjacency lists within the graph
- for (int i = 0; i < getOrder(G); i++) {
- clear(G->adjacency[i]);
- }
- G->size = 0; // no more edges = size is 0
- }
- // sortEdge()
- // helper method for addEdge() and addArc()
- // InsertionSort ish
- void sortEdge(List list, int v) {
- if (list == NULL) {
- printf("List error: cannot call sortEdge on NULL List reference\n");
- }
- if (length(list) == 0) {
- append(list, v);
- return; // add and return
- }
- moveFront(list);
- while (index(list) != -1) {
- if (v < get(list)) {
- insertBefore(list, v);
- break;
- }
- moveNext(list);
- }
- if (index(list) == -1) {
- append(list, v);
- }
- }
- // addEdge()
- // pre: both u and v are between 1 and getOrder(G)
- void addEdge(Graph G, int u, int v) {
- if (G == NULL) {
- printf("Graph error: cannot call addEdge on NULL Graph reference\n");
- }
- sortEdge(G->adjacency[u], v);
- sortEdge(G->adjacency[v], u);
- G->size++;
- }
- // addArc()
- // pre: both u and v are between 1 and getOrder(G)
- void addArc(Graph G, int u, int v) {
- if (G == NULL) {
- printf("Graph error: cannot call addArc on NULL Graph reference\n");
- }
- sortEdge(G->adjacency[u], v);
- G->size++;
- }
- // BFS()
- // runs the BFS algorithm on the Graph G with source s,
- // setting the color, distance, parent, and source fields of G accordingly
- void BFS(Graph G, int s) {
- for (int i = 0; i < getOrder(G); i++) {
- if (s != getSource(G)) {
- G->color = WHITE;
- G->distance[i] = INF;
- G->parent[i] = NIL;
- }
- }
- G->source = s;
- G->color[s] = GRAY; // discover the source S
- G->distance[s] = 0;
- G->parent[s] = NIL;
- List list = newList();
- append(list, s); // equivalent to enqueue
- while (length(list) > 0) {
- // equivalent to dequeue
- int x = front(list);
- deleteFront(list);
- List getAdjacency = G->adjacency[x];
- moveFront(getAdjacency);
- while (index(getAdjacency) != -1) {
- int y = get(getAdjacency);
- if (G->color[y] == WHITE) { // y is undiscovered
- G->color[y] = GRAY; // discover y
- G->distance[y] = G->distance[x] + 1;
- G->parent[y] = x;
- append(list, y);
- }
- moveNext(getAdjacency);
- }
- G->color[x] = BLACK; // finish x
- }
- freeList(&list);
- }
- // Other Operations -------------------------------------
- // printGraph()
- // prints the adjacency list representation of G to the file pointed to by "out"
- void printGraph(FILE* out, Graph G) {
- if (G == NULL) {
- printf("Graph error: cannot call printGraph on NULL Graph reference\n");
- exit(1);
- }
- for (int i = 1; i <= getOrder(G); i++) {
- List L = G->adjacency[i];
- fprintf(out, "%d:", i);
- moveFront(L);
- while (index(L) != -1) {
- fprintf(out, " %d", get(L));
- }
- fprintf(out, "\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement