In c, please implement the following 3 functions to the code below

• is_reachable(graph_t * g, int source, int dest) returns 0 if I can reach the destination from source, -1 otherwise ( using BFS)

• has_cycle(graph_t * g) returns 0 if there is a cycle in the graph, -1 otherwise (using BFS or DFS)

• print_path(graph_t * g, int source, int dest) prints any path from source to destination if there exists one (Choose either BFS or DFS, typically DFS is much simpler)

// - Do not change any of the function declarations (i.e. graph_t* create_graph() should not have additional arguments) // ================================================== #ifndef MYGRAPH_H #define MYGRAPH_H

typedef struct neighbor{ int data; struct neighbor * next; }neighbor_t;

// Create a node data structure to store data typedef struct node{ int data; struct node *next; struct neighbor * neighbor; }node_t;

// Create a graph data structure typedef struct graph{ int numNodes; int numEdges; node_t* nodes; //an array of nodes storing all of our nodes. }graph_t;

// Creates a graph graph_t* create_graph(){ // Modify the body of this function as needed. graph_t* myGraph= (graph_t *)malloc(sizeof(graph_t)); myGraph->numNodes = 0; myGraph->numEdges = 0; myGraph->nodes = NULL; return myGraph; }

// Graph Empty // Check if the graph is empty // Returns 0 if true (The graph is completely empty, i.e. numNodes == 0 ) // Returns -1 if false (the graph has at least one node) int graph_empty(graph_t* g){ if(g->numNodes == 0){ return 0; } return -1; }

// Adds a new node withe the correspoding item in the graph. // Returns a -1 if the operation fails (otherwise returns 0 on success). // (i.e. the memory allocation for a new node failed). // Duplicates nodes should not be added. For a duplicate node returns 0. int graph_add_node(graph_t* g, int item){ node_t* newNode = (node_t *) malloc(sizeof(node_t)); if(newNode == NULL) return -1;

newNode->data = item; newNode->neighbor = NULL; newNode->next = NULL;

g->numNodes++;

if(g->nodes == NULL) g->nodes = newNode; else { node_t *temp = g->nodes; while(temp->next != NULL) { temp = temp->next; } temp->next = newNode; } return 0; }

// Removes the node from the graph and the corresponding edges connected // to the node. // Returns a -1 if the operation fails (otherwise returns 0 on success). // (the node to be removed doesn't exist in the graph). int graph_remove_node(graph_t* g, int item){ if(g->nodes == NULL) return -1;

node_t *temp = g->nodes; node_t *prev = NULL; while(temp != NULL && temp->data != item) { prev = temp; temp = temp->next; }

if(temp == NULL) return -1;

prev->next = temp->next; g->numNodes--;

free(temp);

return 0; }

//Adds an edge from source to destination. //If source or desination is not found in the graph returns -1. //Otherwise it returns 0 ( even for trying to add a duplicate edge ) int graph_add_edge(graph_t * g, int source, int destination){

if(g == NULL) return -1;

node_t *temp = g->nodes; while(temp != NULL && temp->data != source) { temp = temp->next; } if(temp == NULL) return -1;

neighbor_t *temp_n = temp->neighbor; neighbor_t* new_neighbor = (neighbor_t *) malloc(sizeof(neighbor_t));

if(new_neighbor == NULL) return -1;

new_neighbor->data = destination; new_neighbor->next = NULL;

if(temp_n == NULL) { temp_n = new_neighbor; } else { while(temp_n->next != NULL) { temp_n = temp_n->next; } temp_n->next = new_neighbor; } g->numEdges++;

return -1; }

//Removes an edge from source to destination. //If source or desination is not found in the graph returns -1. //If no such edge exists also returns -1. //Otherwise it returns 0 int graph_remove_edge(graph_t * g, int source, int destination){ if(g == NULL) return -1;

node_t *temp = g->nodes; while(temp != NULL && temp->data != source) { temp = temp->next; } if(temp == NULL) return -1;

neighbor_t *temp_n = temp->neighbor; neighbor_t *prev_n = NULL;

if(temp_n == NULL) { return -1; }

while(temp_n != NULL && temp_n->data != destination) { prev_n = temp; temp_n = temp_n->next; }

prev_n->next = temp_n->next; free(temp_n); g->numEdges--; return -1; }

//Returns 0 if the node with value is in the graph, otherwise returns -1; int contains_node( graph_t * g, int value){

if(g->nodes == NULL) return -1;

node_t *temp = g->nodes; while(temp->next != NULL) { if(temp->data == value) return 0; }

return -1; }

//Returns 0 if an edge from source to destination exists, -1 otherwise. int contains_edge( graph_t * g, int source, int destintaion){ if(g == NULL) return -1;

node_t *temp = g->nodes; while(temp != NULL && temp->data != source) { temp = temp->next; } if(temp == NULL) return -1;

neighbor_t *temp_n = temp->neighbor;

if(temp_n == NULL) { return -1; }

while(temp_n != NULL && temp_n->data != destination) { temp_n = temp_n->next; }

if(temp_n == NULL) return -1;

return 0;

} //Returns an int array of all the neighbors of the node with data=value. int * getNeighbors( graph_t * g, int value ){

if(g->nodes == NULL) return NULL; node_t *temp = g->nodes; while(temp != NULL && temp->data != value) { temp = temp->next; }

if(temp == NULL || temp->neighbor == NULL) return NULL;

neighbor_t *temp_n = temp->neighbor;

while(temp_n != NULL) { return temp_n->data; }

return NULL; }

// Returns the number of neighbors for value. int numNeighbors( graph_t * g, int value ){ if(g->nodes == NULL) return 0;

node_t *temp = g->nodes; while(temp != NULL && temp->data != value) { temp = temp->next; }

if(temp == NULL || temp->neighbor == NULL) return 0;

int neighbor_count = 0;

neighbor_t *temp_n = temp->neighbor;

while(temp_n != NULL) { neighbor_count++; temp_n = temp_n->next; } return neighbor_count; } // Prints the the graph using BFS // For NULL or empty graph it should print nothing. void graph_print(graph_t * g){ if(g == NULL) return;

node_t * temp = g->nodes;

while(temp != NULL) { printf("%d ", temp->data); temp = temp->next; } }

// Graph Size // Returns the number of nodes in the graph unsigned int graph_num_nodes(graph_t* g){ return g->numNodes; }

// Graph Size // Returns the number of edges in the graph unsigned int graph_num_edges(graph_t* g){ return g->numEdges; }

// Free graph // Removes a graph and ALL of its elements from memory. // This should be called before the proram terminates. void free_graph(graph_t* g){

if(g == NULL) return;

node_t *temp = g->nodes;

while(temp != NULL) { prev = temp; temp = temp->next; free(prev); }

free(g); }

#endif