Can we get a solution to this below in C:

(Graphs graph functions)

At the end of this document, you are given the basic code that we implemented in the slides to create/read/print graphs. First copy/paste it into a file say graph.c and compile/run it.

gcc graph.c o graph

./graph graph_filename For sample graphs, again copy/paste the below graph data into a file

undirectedgraph1.txt and directedgraph1.txt then run your program as ./graph undirectedgraph1.txt ./graph directedgraph1.txt

undirectedgraph1.txt 680 123 136 231 245 352 453 466 561
directedgraph1.txt 681 123 231 316 352 425 453 466 561

After studying and understanding the given code, first modify insert_edge() function so that it can keep the link list sorted with respect to (w.r.t.) neighbor IDs. Second implementgraph_copy() to create a copy of the given graph. User will call the original graph asmyg1 and the copy as myg2, for which we use the same pointer names in the program. Now extend the main function so that it can asks user to enter various commands in a loop and performs these commands on the related graphs. Accordingly, you also need to implement those functions and call them. Finally, when ending the main function, make sure you free the graphs

----- see more explanations that are at the end of this handout------------

Specifically, your program will ask user to enter a command and related parameters (if any) in a loop, and then perform the given commands. Here is the list of commands that your program must implement: [Your command names should be the same as written below so the TA can copy paste his/her test cases... for your own testing you can use initials etc, but your code should be able to handle the full command names below]

* insert * delete 

[myg1 | myg2] [myg1 | myg2] 

xy w xy

// if directed, print both in- and out-degree

* eliminatelinks [myg1 | myg2] minW maxW 

* printgraph * printdegree * printcomplement [myg1 | myg2] 

* differentlinks * commonlinks 

* dfs * bfs * isconnected * numofconncomp 

[myg1 | myg2] [myg1 | myg2] [myg1 | myg2] [myg1 | myg2] 

[myg1 | myg2] x [myg1 | myg2] x [myg1 | myg2] [myg1 | myg2] 

* quit

[myg1 | myg2] [myg1 | myg2] 

----- see more explanations that are at the end of this handout------------

Please make sure your program processes the above comments as is.

As always, make sure you release (free) the dynamically allocated memories if you allocate any memory in your programs. So, before submitting your program, run it with valgrind tosee if there is any memory leakage... Also if you need to debug your program, compile your programs with g option and then run it with gdb and/or ddd.

/* Dont forget to include comments about the problem, yourself and each major

step in your program! */

_________________________________________________________________

graph.c

#include #include typedef enum {FALSE, TRUE} bool; #define MAXV 100 

typedef struct edgenode { int y; 

int weight;

 struct edgenode *next; } edgenodeT; 

typedef struct { edgenodeT *edges[MAXV+1]; int degree[MAXV+1]; int nvertices; int nedges; // number of directed edges.... bool directed; 

} graphT; void initialize_graph(graphT *g, bool directed); void read_graph(graphT *g, char *filename); void insert_edge(graphT *g, int x, int y, int w); void print_graph(graphT *g, char *name); void free_graph(graphT *g); graphT *copy_graph(graphT *g); // put prototypes for other functions here....

int main(int argc, char *argv[]) { 

 graphT *myg1=NULL, *myg2=NULL; 

if(argc

 } myg1 = (graphT *) malloc(sizeof(graphT)); if (myg1==NULL) { 

fprintf(stderr, "Cannot allocate memory for the graph");

exit(-1); }

 initialize_graph(myg1, FALSE); read_graph(myg1, argv[1]); print_graph(myg1, "myg1"); 

// first implement copy_graph function and call it here myg2 = copy_graph(myg1); print_graph(myg2, "myg2");

 // NOW in a loop get commands and // call related functions to perform them... free_graph(myg1); 

}

void initialize_graph(graphT *g, bool directed) {

 int i; g->nvertices = 0; g->nedges = 0; g->directed = directed; 

 for (i=1; iedges[i] = NULL; 

 for (i=1; idegree[i] = 0; 

}

void read_graph(graphT *g, char *filename) { 

 int i; int n, m, dir; int x, y, w; FILE *fp; if((fp=fopen(filename,"r"))==NULL){ 

 fprintf(stderr, "Cannot open the graph file"); 

exit(-1); }

 fscanf(fp,%d %d %d, &n, &m, &dir); g->nvertices = n; g->nedges = 0; // insert function will increase it; g->directed = dir; for (i=1; i 
 fscanf(fp,%d %d %d, &x, &y, &w); insert_edge(g, x, y, w); if(dir==FALSE) 
 
 insert_edge(g, y, x, w); 
 
}
 
 fclose(fp); } 
 
void insert_edge(graphT *g, int x, int y, int w) { 
 
edgenodeT *pe; pe = malloc(sizeof(edgenodeT)); // check if NULL pe->weight = w; pe->y = y;
 
// YOU MUST MODIFY THIS FUNCTION SO IT WILL KEEP LINK LIST SORTED // W.R.T. NEIGHBOR IDs.
 
 pe->next = g->edges[x]; g->edges[x] = pe; 
 
 g->degree[x]++; 
 
 g->nedges++; } 
 
void print_graph(graphT *g, char *name) { 
 
 edgenodeT *pe; int i; if(!g) return; printf("Graph Name: %s ", name); for(i=1; invertices; i++) { 
 
 printf("Node %d: ", i); pe = g->edges[i]; while(pe){ 
 
 // printf(" %d", pe->y); printf(" %d(w=%d),", pe->y, pe->weight); pe = pe->next; 
 
}
 
 printf(" "); } 
 
}
 
void free_graph(graphT *g) { 
 
 edgenodeT *pe, *olde; int i; for(i=1; invertices; i++) { 
 
 pe = g->edges[i]; while(pe){ 
 
 olde = pe; pe = pe->next; free(olde); 
 
} }
 
free(g); }
 
graphT *copy_graph(graphT *g) { 
 
 graphT *newg; 
 
 // I simply return the same graph as a copy // but you really need to dynamically create // another copy of the given graph newg = g; 
 
 return newg; } 
 
// your other functions 
 
here are some clarifications 
 
* insert myg1 3 4 20 insert a new edge 3-4 into myg1 graph with weight of 20. If this is an undirected graph also insert edge 4-3 with weight 20. If that edge is already in the graph, don't insert a new edge but update the weight based on the newly given weight... Remember you need to insert edges in a sorted manner 
 
* delete myg1 2 4 delete edge 2-4 from myg1. If this is an undirected graph also delete edge 4-2. If that edge is not in the graph, don't delete anything... 
 
* printgraph myg1 print graph using the code given... 
 
* printdegree myg1 if myg1 is undirected, then simply count the number of neighbors in the adjacency list for each node and print that number as the degree of each node.. 
 
if the graph is directed, then again you can simply count the number of neighbors in the adjacency list for each node and print that number as the out-degree of each node... BUT you also need to find in-degree. For this, you can check every node (say node i)and count how many times node i appears in the all adjacency lists, and print that count as the in-degree for node i. 
 
* printcomplement myg2 First create the complement graph of myg2 as cg, and call printgraph(cg) then free complement graph cg. Don't worry about weight in the new graph cg. for example, you can set all weights to 1 in cg 
 
* eliminatelinks myg1 minW maxW check each edge pe if (pe->w w > maxW) delete that edge 
 
* differentlinks myg1 myg2 print edges that are in myg1 but not in myg2 
 
* commonlinks myg1 myg2 print edges that are both in myg1 and in myg2 
 
*dfs myg1x print in which order nodes are visited according to dfs
 
then for each node i print the path from x to node i 
 
* bfs myg2 x print in which order nodes are visited according to bfs then for each node i print the path from x to node i 
 
* isconnected myg1 * numofconncomp myg2 
 
last two commands isconnected numofconncomp will be performed if the graph is UNdirected ... if the graph is directed don't do anything or just print 
  6 undirectedgraphl. txt directedgraph1.txt 6 8 1 1 2 3 1 2 3 3 5 2  6 undirectedgraphl. txt directedgraph1.txt 6 8 1 1 2 3 1 2 3 3 5 2