//c program modify insert_edge() function so that it can keep the link list sort
ID: 3775641 • Letter: #
Question
//c program
modify insert_edge() function so that it can keep the link list sorted w.r.t. neighbor IDs.
implement graph_copy() to create a copy of the given graph. User will call the original graph as myg1 and the copy as myg2, for which we use the same pointer names in the program.
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:
* insert [myg1 | myg2] x y w
* delete [myg1 | myg2] x y
* printgraph [myg1 | myg2]
* printdegree [myg1 | myg2] // if directed, print both in- and out-degree
* printcomplement [myg1 | myg2]
* eliminatelinks [myg1 | myg2] minW maxW
* differentlinks [myg1 | myg2] [myg1 | myg2]
* commonlinks [myg1 | myg2] [myg1 | myg2]
* dfs_print [myg1 | myg2] x
* bfs_print [myg1 | myg2] x
* isconnected [myg1 | myg2]
* numofconncomp [myg1 | myg2] * quit
//graph.c program
#include <stdio.h>
#include <stdlib.h>
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;
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);
main()
// Assume that MAXV is 6
{
graphT *myg1 = NULL, *myg2 = NULL;
if(argc < 2){
fprintf(stderr, "Usage: %s graph_filename", argv[0]);
exit(-1);
}
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");
myg2 = copy_graph(myg1);
print_graph(myg2, "myg2");
// NOW in a loop get commands and
// call related functions to perform them...
free_graph(myg1);
}
initialize_graph (graphT*g, bool directed)
{
int i;
g->nvertices= 0;
g->nedges= 0;
g->directed = directed;
for (i=1; i<=MAXV; i++)
g->edges[i] = NULL;
for(i=1; i<=MAXV; i++)
g->degree[i] = 0;
}
read_graph(graphT *g)
{
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);
}
scanf(”%d %d %d”, &n, &m, &dir);
g->nvertices= n;
g->nedges= 0;
g->directed= dir;
for (i=1; i<=m; i++) {
scanf(”%d %d %d”, &x, &y, &w);
insert _edge(g, x, y, w);
if(dir==FALSE)
insert _edge(g, y, x, w);
}
fclose(fp);
}
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;
pe->next = g->edges[x];
g->edges[x] = pe;
g->degree[x]++;
g->nedges++;
}
print_graph (graphT *g, char *name)
{
edgenodeT *pe;
int i;
if(!g) return;
printf("Graph Name: %s ", name);
for(i=1; i<=g->nvertices; i++){
printf("Node %d: ", i);
pe = g->edges[i];
while(ge){
printf(" %d %d,", pe->y, pe->weight);
pe = pe->next;
}
printf(" ");
}
}
free_graph(graphT *g)
{
edgenodeT *pe, *olde;
int i;
for(i=1; i<=g->nvertices;i++){
pe = g->edges[i];
while(pe){
olde = ps;
pe = pe->next;
free(olde);
}
}
free(g);
}
graphT *copy_graph(graphT *g)
{
graphT *newg;
newg = g;
return newg;
}
Explanation / Answer
1)
insert_edge(graphT *g, int x, int y, int w)
{
edgenodeT *pe;
pe= malloc(sizeof(edgenodeT));
if(pe != null){
while(g->next != null){
if(g->y < y){
pe->weight = w;
pe->y = y;
pe->next = g->edges[x];
g->edges[x] = pe;
g->degree[x]++;
g->nedges++;
break;
}
}
}}
2)
delete(graphT *g, int x, int y){
edgenodeT *pe;
pe=g->edges[x];
while (g->!= null){
if(pe->y == g->y){
g->edges[x-1]->y = g->edges[x+1];
g->degree[x]--;
g->nedges--;
free(pe);
break;
}
}
}
3)
printgraph(graphT *g){
while(g->next != null){
printf("%d %d",g->y,g->weight)
;}
}
4)
printgraph(graphT *g){
while(g->next != null){
if(g->directed != 1)
printf("%d",g->nedges);
else{
printf(" indegree=%d out degree=",g->nedges,g->edges[g->y]);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.