Question

1 Approved Answer

Posted on Sep 21, 2024

The following functions need to be updated: add_node(graph_t * g, int value) add_edge(graph_t * g, int source, int destintaion) this adds an edge from source

The following functions need to be updated:

add_node(graph_t * g, int value)
add_edge(graph_t * g, int source, int destintaion) this adds an edge from source to destination but not the other way.
remove_edge(graph_t * g, int source, int destination) this removes an edge from source to destination but not the other way.
remove_node(graph_t * g, int value) this removes the node from the graph along with any edges associated with it. That is, this node would have to be removed from all the neighbor's lists that countain it.
contains_node( graph_t * g, int value) returns 1 if the node exists 0 otherwise
contains_edge( graph_t * g, int source, int destintaion) returns 1 if an edge from source to destination exists, false otherwise.
getNeighbors( graph_t * g, int value ) returns an int array of all the neighbors of the node with data=value.
numNeighbors( graph_t * g, int value) returns the number of neighbors for the node with value.

Here is the paste able code:

Copy Pasteable:

// - Implement each of the functions to create a working graph. // - Do not change any of the function declarations // - (i.e. graph_t* create_graph() should not have additional arguments) // - You should not have any 'printf' statements in your graph functions. // - (You may consider using these printf statements to debug, but they should be removed from your final version) // ================================================== #ifndef MYGRAPH_H #define MYGRAPH_H // Create a neighbor data structure to server as the neighbor's list. // In our case, we will stores 'integers' as our neighbors that // corresponding to the data that the actual nodes store. typedef struct neighbor{ int data; struct neighbor * next; }neighbor_t; // Create a node data structure to store data within // our graph. In our case, we will stores 'integers' // as our data in the nodes typedef struct node{ int data; struct node *next; struct neighbor * neighbor; }node_t; // Create a graph data structure // Our graph keeps track of the number of nodes, the number of edges and an array // of all the nodes in the graph, and the maximum number of nodes we store in our graph. typedef struct graph{ int numNodes; int numEdges; node_t* nodes; //an array of nodes storing all of our nodes. }graph_t; // Creates a graph // Returns a pointer to a newly created graph. // The graph should be initialized with data on the heap. // The graph fields should also be initialized to default values. graph_t* create_graph(){ // Modify the body of this function as needed. graph_t* myGraph= 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){ 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){ return -1; } // 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){ return -1; } //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){ 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){ return -1; } //Returns 0 if the node with value is in the graph, otherwise returns -1; int contains_node( graph_t * g, int value){ return -1; } //Returns 0 if an edge from source to destination exists, -1 otherwise. int contains_edge( graph_t * g, int source, int destintaion){ return -1; } //Returns an int array of all the neighbors of the node with data=value. int * getNeighbors( graph_t * g, int value ){ return NULL; } // Returns the number of neighbors for value. int numNeighbors( graph_t * g, int value ){ return 0; } // Prints the the graph using BFS // For NULL or empty graph it should print nothing. void graph_print(graph_t * g){ } // Graph Size // Returns the number of nodes in the graph unsigned int graph_num_nodes(graph_t* g){ return 0; } // Graph Size // Returns the number of edges in the graph unsigned int graph_num_edges(graph_t* g){ return 0; } // 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){ }

image text in transcribed

6 I1-Implement each of the functions to create a working graph I1-Do not change any of the function declarations (i.e. graph t* create_graph) should not have additional arguments) 9 II-You should not have any 'printf' statements in your graph functions. - (You may consider using these printf statements to debug, but they should be 12 #ifndefMYGRAPH_A 13 #define MYGRAPHH 14 15 II Create a neighbor data structure to server as the neighbor's list 16 // In our case, we will stores integers' as our neighbors that 17 // corresponding to the data that the actual nodes store. 18 typedef struct neighborf 19 20 21 neighbor_t; int data struct neighbor next; 23 I/Create a node data structure to store data within 24 // our graph. In our case, we will stores integers" 25 I/ as our data in the nodes 26 typedef struct node 27 28 29 30 node_t; 31 32 II Create a graph data structure 33 // 0Our graph keeps track of the number of nodes, the number of edges and an array 34 I/ of all the nodes in the graph, and the maximum number of nodes we store in our gra 35 typedef struct graph 36 37 38 9 graph_t; 40 1 I/ Creates a graph 42 // Returns a pointer to a newly created graph. 43 I1 The graph should be initialized with data on the heap. 44 1/ The graph fields should also be initialized to default values 45 graph_t* create_graph) 46 47 48 49 50 51 52 II Graph Empty 53 I/ Check if the graph is empty 54 I1 Returns 0 if true (The graph is completely empty, i.e. numNodes) 55 I/ Returns-1 if false (the graph has at least one node) 56 int graph_empty (graph_t* g)f 57 58 59 60 // Adds a new node withe the correspoding item in the graph. 61 I/ Returns a -1 if the operation fails (otherwise returns on success) 62 11 (i.e. the memory allocation for a new node failed) 63 Duplicates nodes should not be added. For a duplicate node returns 0 64 int graph_add_node (graph_t* g, int item) 65 int data struct node next; struct neighbor neighbor; int numNodes; int numEdges node t* nodes; //an array of nodes storing all of our nodes. // Modify the body of this function as needed. graph_tmyGraph- NULL; return myGraph; return-1 return-1; 68 I/ Removes the node from the graph and the corresponding edges connected 69 11 to the node. 70 I/ Returns a -1 if the operation fails (otherwise returns 0 on success) 71 11 (the node to be removed doesn't exist in the graph) 72 int graph_remove_node (graph_t* g, int item) 73 74 75 return-1; 76 //Adds an edge from source to destination. 77 //If source or desination is not found in the graph returns -1. 78 //0therwise it returns even for trying to add a duplicate edge) 79 int graph_add_edge(graph_t * g, int source, int destination) 80 return-1; 81 82 83 //Removes an edge from source to destination. 84 //If source or desination is not found in the graph returns-1 85 //If no such edge exists also returns -1. 86 //0therwise it returns0 87 int graph_remove_edge(graph t return-1; g, int source, int destination) 89 90 //Returns 0 if the node with value is in the graph, otherwise returns-1; 91 int contains node( graph_t* g, int value) 92 return -1; 93 94 95 //Returns 0 if an edge from source to destination exists, -1 otherwise. 96 int contains_edge( graph t * g, int source, int destintaion) 97 return-1; 98 99 //Returns an int array of all the neighbors of the node with data-value. 100 int *getNeighbors( graph t *g, int value 101 102 103 return NULL; 104 11 Returns the number of neighbors for value. 105 int numNeighbors( graph_t g, int value ) 106 107 108 return 0; 189 17 Prints the the graph using BFS 110 I/ For NULL or empty graph it should print nothing. 111 void graph_print(graph_t *g) 112 113 114 115 / Graph Size 116 I/ Returns the number of nodes in the graph 117 unsigned int graph_num_nodes(graph_t* g) 118 119 120 121 II Graph Size 122 // Returns the number of edges in the graph 123 unsigned int graph_num_edges(graph t* g) 124 125 126 127 I/ Free graph 128 II Removes a graph and ALL of its elements from memory 129 II This should be called before the proram terminates. 130 void free_graph (graph t* g) 131 132 133 134 135 136 #endif return 0; return 0; 6 I1-Implement each of the functions to create a working graph I1-Do not change any of the function declarations (i.e. graph t* create_graph) should not have additional arguments) 9 II-You should not have any 'printf' statements in your graph functions. - (You may consider using these printf statements to debug, but they should be 12 #ifndefMYGRAPH_A 13 #define MYGRAPHH 14 15 II Create a neighbor data structure to server as the neighbor's list 16 // In our case, we will stores integers' as our neighbors that 17 // corresponding to the data that the actual nodes store. 18 typedef struct neighborf 19 20 21 neighbor_t; int data struct neighbor next; 23 I/Create a node data structure to store data within 24 // our graph. In our case, we will stores integers" 25 I/ as our data in the nodes 26 typedef struct node 27 28 29 30 node_t; 31 32 II Create a graph data structure 33 // 0Our graph keeps track of the number of nodes, the number of edges and an array 34 I/ of all the nodes in the graph, and the maximum number of nodes we store in our gra 35 typedef struct graph 36 37 38 9 graph_t; 40 1 I/ Creates a graph 42 // Returns a pointer to a newly created graph. 43 I1 The graph should be initialized with data on the heap. 44 1/ The graph fields should also be initialized to default values 45 graph_t* create_graph) 46 47 48 49 50 51 52 II Graph Empty 53 I/ Check if the graph is empty 54 I1 Returns 0 if true (The graph is completely empty, i.e. numNodes) 55 I/ Returns-1 if false (the graph has at least one node) 56 int graph_empty (graph_t* g)f 57 58 59 60 // Adds a new node withe the correspoding item in the graph. 61 I/ Returns a -1 if the operation fails (otherwise returns on success) 62 11 (i.e. the memory allocation for a new node failed) 63 Duplicates nodes should not be added. For a duplicate node returns 0 64 int graph_add_node (graph_t* g, int item) 65 int data struct node next; struct neighbor neighbor; int numNodes; int numEdges node t* nodes; //an array of nodes storing all of our nodes. // Modify the body of this function as needed. graph_tmyGraph- NULL; return myGraph; return-1 return-1; 68 I/ Removes the node from the graph and the corresponding edges connected 69 11 to the node. 70 I/ Returns a -1 if the operation fails (otherwise returns 0 on success) 71 11 (the node to be removed doesn't exist in the graph) 72 int graph_remove_node (graph_t* g, int item) 73 74 75 return-1; 76 //Adds an edge from source to destination. 77 //If source or desination is not found in the graph returns -1. 78 //0therwise it returns even for trying to add a duplicate edge) 79 int graph_add_edge(graph_t * g, int source, int destination) 80 return-1; 81 82 83 //Removes an edge from source to destination. 84 //If source or desination is not found in the graph returns-1 85 //If no such edge exists also returns -1. 86 //0therwise it returns0 87 int graph_remove_edge(graph t return-1; g, int source, int destination) 89 90 //Returns 0 if the node with value is in the graph, otherwise returns-1; 91 int contains node( graph_t* g, int value) 92 return -1; 93 94 95 //Returns 0 if an edge from source to destination exists, -1 otherwise. 96 int contains_edge( graph t * g, int source, int destintaion) 97 return-1; 98 99 //Returns an int array of all the neighbors of the node with data-value. 100 int *getNeighbors( graph t *g, int value 101 102 103 return NULL; 104 11 Returns the number of neighbors for value. 105 int numNeighbors( graph_t g, int value ) 106 107 108 return 0; 189 17 Prints the the graph using BFS 110 I/ For NULL or empty graph it should print nothing. 111 void graph_print(graph_t *g) 112 113 114 115 / Graph Size 116 I/ Returns the number of nodes in the graph 117 unsigned int graph_num_nodes(graph_t* g) 118 119 120 121 II Graph Size 122 // Returns the number of edges in the graph 123 unsigned int graph_num_edges(graph t* g) 124 125 126 127 I/ Free graph 128 II Removes a graph and ALL of its elements from memory 129 II This should be called before the proram terminates. 130 void free_graph (graph t* g) 131 132 133 134 135 136 #endif return 0; return 0