#include #include typedef enum {white, gray, black} COLOR; typedef struct Graph { int V; /umber of vertices in G int ** M; //2D array of ints, adjacency matrix } Graph; typedef struct DFS { COLOR color; // white, gray, or black int parent; int discover; int finish; } DFS; int time = 0; // note that this is a global variable (not great programming // practice) but need to have a global time count for DFS // it would be better to pass in a pointer to a variable that // stores the time that dfs could access and update, but // for the purpose of keeping this lab simple, we have a // global variable // prototypes Graph * createEmptyGraph(int numVertices); int addEdge(Graph * g, int src, int dest); int outDegree(Graph * g, int v); int inDegree(Graph * g, int v); int degree(Graph * g, int v); void freeGraph(Graph * g); void printGraph(Graph * g); int isNeighbor(Graph * g, int x, int y); DFS * dfsInit(Graph * g); void dfs(Graph * g, DFS arr[], int src); void printReversePath(Graph * g, DFS arr[], int src, int dest); /* main creates a graph and processes it (degrees, neighbors, DFS, paths) */ int main(void) { // create graph printf("Creating graph. "); Graph * g = createEmptyGraph(6); int ok1 = addEdge(g, 0, 5); int ok2 = addEdge(g, 0, 3); int ok3 = addEdge(g, 1, 2); int ok4 = addEdge(g, 3, 5); int ok5 = addEdge(g, 4, 3); int ok6 = addEdge(g, 2, 1); int ok7 = addEdge(g, 2, 3); int ok8 = addEdge(g, 1, 0); int ok9 = addEdge(g, -2, 0); int ok10 = addEdge(g, 2, 4); int ok11 = addEdge(g, 5, 4); int ok12 = addEdge(g, 4, -1); int ok13 = addEdge(g, 5, 1); int ok14 = addEdge(g, 7, 2); int ok15 = addEdge(g, 3, 1); int ok16 = addEdge(g, 2, 1); printf(" "); printGraph(g); // print degree information printf("out degree of 0: %d ", outDegree(g, 0)); printf("in degree of 0: %d ", inDegree(g, 0)); printf("total degree of 0: %d ", degree(g, 0)); printf(" "); // print neighbor information printf("Neighbors of 0: "); int i; for(i = 0; i V; i++) { if(isNeighbor(g, 0, i)) { printf("%d ", i); } } printf(" "); // print DFS information DFS * arr = dfsInit(g); dfs(g, arr, 0); for(i = 0; i V; i++) { printf("Node %d: %d/%d, parent: %d ", i, arr[i].discover, arr[i].finish, arr[i].parent); } // print paths printReversePath(g, arr, 0, 1); printReversePath(g, arr, 0, 2); printReversePath(g, arr, 0, 3); printReversePath(g, arr, 0, 4); printReversePath(g, arr, 0, 5); freeGraph(g); return EXIT_SUCCESS; } /* createEmptyGraph sets up the graph data structure with numVertices */ Graph * createEmptyGraph(int numVertices) { if(numVertices V = numVertices; g->M = (int **) malloc(sizeof(int *) * numVertices); int i; if(g->M != NULL) { for(i = 0; i M[i] = (int *) malloc(sizeof(int) * numVertices); if(g->M[i] == NULL) { freeGraph(g); return NULL; } } } int j; for(i = 0; i M[i][j] = 0; } } return g; } /* freeGraph frees all memory associated with the graph */ void freeGraph(Graph * g) { if(g == NULL) { return; } int i; for(i = 0; i V; i++) { free(g->M[i]); } free(g->M); free(g); g = NULL; } /* addEdge should do error-checking of the parameters and put a 1 in the adjacency matrix at M[src][dest] */ int addEdge(Graph * g, int src, int dest) { // complete this function return 0; } /* outDegree returns the out degree of a vertex v */ int outDegree(Graph * g, int v) { // complete this function return 0; } /* inDegree returns the in degree of a vertex v */ int inDegree(Graph * g, int v) { // complete this function return 0; } /* degree returns the degree of a vertex v */ int degree(Graph * g, int v) { return inDegree(g, v) + outDegree(g, v); } /* printGraph prints the graph as a matrix */ void printGraph(Graph * g) { if(g == NULL) { return; } int i, j; printf("Matrix for graph: "); for(i = 0; i V; i++) { for(j = 0; j V; j++) { printf("%d ", g->M[i][j]); } printf(" "); } printf(" "); } /* isNeighbor returns 1 if edge (x, y), x to y, exists; 0 otherwise */ int isNeighbor(Graph * g, int x, int y) { // complete this function return 0; } /* dfsInit initializes the array of DFS structs, so that the parent is -1 for all nodes, color is white for all nodes, and discover and finish times are -1 */ DFS * dfsInit(Graph * g) { if(g == NULL || g->V V); int i; for(i = 0; i V; i++) { arr[i].parent = -1; arr[i].color = white; arr[i].discover = -1; arr[i].finish = -1; } time = 0; return arr; } /* dfs does depth-first search of the graph from src, filling in the arr of DFS structs as it processes, should be recursive */ void dfs(Graph * g, DFS arr[], int src) { // do DFS from src node in graph g if(g == NULL || arr == NULL) { return; } if(src = g->V) { return; } // complete this function here: } /* printReversePath prints the path from dest 1. Read through the dfsInit function. This initializes the array of DFS objects prior search. It should print "visited 0" when it visits node 0. Note that the time variable is global, so the recursive function calls have access to the same time variable. Use isNeighbor to determine the vertices adjacent to the node you are currently processing 2. Complete the printReversePath function so that it prints the path from dest to source. Note that a more user-friendly version would reverse the path to print from src to dest, which could easily be done with a stack. To implement this, you start with current node as the dest node. You find its parent and set this to the current node. Print the current node. Keep doing this while the current node is not -1 and current node is not the src. An example printout forpthfom 0 to 1 would look like Checkpoint 2 [20 points]l: Copy and Paste the results of your program execution. 1. Read through the dfsInit function. This initializes the array of DFS objects prior search. It should print "visited 0" when it visits node 0. Note that the time variable is global, so the recursive function calls have access to the same time variable. Use isNeighbor to determine the vertices adjacent to the node you are currently processing 2. Complete the printReversePath function so that it prints the path from dest to source. Note that a more user-friendly version would reverse the path to print from src to dest, which could easily be done with a stack. To implement this, you start with current node as the dest node. You find its parent and set this to the current node. Print the current node. Keep doing this while the current node is not -1 and current node is not the src. An example printout forpthfom 0 to 1 would look like Checkpoint 2 [20 points]l: Copy and Paste the results of your program execution