In C Programming: void link_elimination(graphT *g, int maxW) { In C Programming:
ID: 666470 • Letter: I
Question
In C Programming:
void link_elimination(graphT *g, int maxW)
{
In C Programming: 7. (4pt) Suppose we use the following structures to represent a graph using adjacency list and read the information about the below graph form a file. Accordingly, we create its adjacency list as shown below. Now we want to eliminate/remove the links whose weights are greater than maxW from the graph g. You are asked to write a function, void link_elimination (graphT ^*g, mt maxW) ,which can perform that task and update the necessary fields in graph g and the adjacency lists. For Example, if we call link_elimination (g, 5); the graph g and thus its representation will be:Explanation / Answer
void link_elimination(graphT *g, int maxW)
{
int nodes=g->nvertices,i;
edgenodeT *edge,*temp;
int cnt=0;
for(i=1;i<=nnodes;i++)
{
edge=g->edges[1];
while(edge->w>maxW )//iterate till you get a edge whose weight is less than maxW and delete all the previous edges
{
temp=edge;
edge=edge->next;
free(temp);
cnt++;
}
g->edges[i]=edge;//set first edge as the new edge found whose weight is leas than maxW
while(edge->next)//iterate through list and delete edge nodes whose weight is more than maxW
{
if(edge->next->w>maxW)
{
edge->next=edge->next->next;
free(edge->next);
cnt++;
}
else
edge=edge->next;
}
}
if(g->directed)//update the number of edges
g->nedges-=cnt;
else
g->nedges-=(cnt/2);
}