PLEASE NOTE: IF THE SOLUTION YOU PROVIDE DOES NOT MATCH THE OUTPUT PROVIDED IT W

ID: 3870907 • Letter: P

Question

PLEASE NOTE: IF THE SOLUTION YOU PROVIDE DOES NOT MATCH THE OUTPUT PROVIDED IT WILL BE MARKED AS INCORRECT!!

The output should be as follows:

Here is the code header:

#if !defined ADJLIST

#define ADJLIST

#include

using namespace std;

const int N = 11;

struct Edge

{

int start_vertex;

int end_vertex;

Edge(int v = -1, int w = -1)

{

start_vertex = v;

end_vertex = w;

}

};

class AdjList

{

int vertexCount;

int edgeCount;

bool digraph;

struct node

{

int value;

node* next;

node(int x, node* t)

{

value = x;

next = t;

}

};

typedef node* link;

vector

adj_list;

public:

AdjList(int, bool);

int V() const;

int E() const;

bool directed() const;

void insert(Edge);

void remove(Edge);

bool edge(int, int) const;

void displayList();

void remove_parellel_edge();

void remove_isolated_vertex();

void remove_selfloops();

};

#endif

1. Show, in the style of Figure 17.10, the adjacency-lists structure produced when you use Program 17.9 to insert the edges in the graph 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 (in that order) into an initially empty graph. 2. Provide implementations of remove and edge for the adjacency-lists graph class (Program 17.9). Show the adjacency-lists structure produced when you remove the edges in the graph you created above question (1) 3-7 7-8 5-2 6-4 (in that order) from the graph. 3. Write a client of the graph ADT that returns the result of removing self-loops, parallel edges (which are two or more edges that are incident to the same two vertices), and degree-0 (isolated) vertices from a given graph. Create a graph which includes self-loop parallel edges, and isolated vertices, and test vour progam with the graph.

Explanation / Answer

// implementation file

#include <bits/stdc++.h>
#include <iomanip>
#include "AdjList.h"
using namespace std;

AdjList :: AdjList(int v, bool val)
{
   vertexCount = v;
   digraph = val;
   int i;
   node *temp = NULL;
   for(i=0;i<v;i++)
       adj_list.push_back(temp);
}

void AdjList :: insert(Edge e)
{
   node *temp = new node(e.end_vertex, adj_list[e.start_vertex]);
   adj_list[e.start_vertex] = temp;
   node *temp2 = new node(e.start_vertex, adj_list[e.end_vertex]);
   adj_list[e.end_vertex] = temp2;
   edgeCount++;
}

int AdjList :: V() const
{
return vertexCount;
}

int AdjList :: E() const
{
return edgeCount ;
}

bool AdjList :: directed() const
{
return digraph;
}

bool AdjList :: edge(int a, int b) const
{
   node *temp = adj_list[a];
   if(temp == NULL)
       return false;
   else
   {
       while(temp != NULL)
       {
           if(temp->value == b)
               return true;
           else
               temp = temp->next;
       }
   }
   return false;
}
void AdjList :: remove(Edge e)
{
   edgeCount--;
   int val1 = e.end_vertex;
   int val2 = e.start_vertex;
   node *temp = adj_list[e.start_vertex];
   node *temp2 = adj_list[e.end_vertex];

   if(temp->value == val1)
       adj_list[e.start_vertex] = temp->next;
   else
   {
       node *prev = temp;
       temp = temp->next;
       while(temp->value != val1)
       {
           prev = temp;
           temp = temp->next;
       }
       prev->next = temp->next;
   }

   if(temp2->value == val2)
       adj_list[e.end_vertex] = temp2->next;
   else
   {
       node *prev2 = temp2;
       temp2 = temp2->next;
       while(temp2->value != val2)
       {
           prev2 = temp2;
           temp2 = temp2->next;
       }
       prev2->next = temp2->next;
   }

}

void AdjList :: displayList()
{
   int i;
   for(i=0;i<vertexCount;i++)
   {
       if(adj_list[i] != NULL)
       {
           node *temp = adj_list[i];
           cout<<i<<" --> ";
           while(temp != NULL)
           {
               cout<<temp->value<<" ";
               temp = temp->next;
           }
           cout<<endl;
       }
   }
}

void AdjList :: remove_parellel_edge()
{
   int i;
   for(i=0;i<vertexCount;i++)
   {
       node *temp = adj_list[i], *prev;
       bool arr[vertexCount];
       memset(arr,false,sizeof(arr));
       while(temp != NULL)
       {
           if(arr[temp->value] == false)
           {
               arr[temp->value] = true;
               prev = temp;
               temp = temp->next;
           }
           else
           {
               prev->next = temp->next;
               temp = temp->next;


           }
       }
   }
}

void AdjList :: remove_isolated_vertex()
{
   int i;
   cout<<"after removing isolated vertices"<<endl;
   for(i=0;i<vertexCount;i++)
   {
       cout<<i<<" --> ";
       if(adj_list[i] != NULL)
       {
           node *temp = adj_list[i];

           while(temp != NULL)
           {
               cout<<temp->value<<" ";
               temp = temp->next;
           }

       }
       cout<<endl;
   }
}

void AdjList :: remove_selfloops()
{
   int i;
   for(i=0;i<vertexCount;i++)
   {
       node *temp = adj_list[i], *prev;
       prev = temp;

       while(temp != NULL && temp->value == i)
           temp = temp->next;
       prev = temp;
       while(temp!=NULL)
       {
           if(temp->value == i)
               prev->next = temp->next;

           else
               prev = temp;
           temp = temp->next;

       }
   }
}

// main.cpp for testing is also provided

#include <bits/stdc++.h>
#include "AdjList.h"
using namespace std;

int main()
{
   AdjList graph(11,false);
   Edge e1(3,7);
   Edge e2(1,4);
   Edge e3(7,8);
   Edge e4(0,5);
   Edge e5(5,2);
   Edge e6(3,8);
   Edge e7(2,9);
   Edge e8(0,6);
   Edge e9(4,9);
   Edge e10(2,6);
   Edge e11(6,4);
   graph.insert(e1);
   graph.insert(e2);
   graph.insert(e3);
   graph.insert(e4);
   graph.insert(e5);
   graph.insert(e6);
   graph.insert(e7);
   graph.insert(e8);
   graph.insert(e9);
   graph.insert(e10);
   graph.insert(e11);

cout<<"Initial graph"<<endl;
graph.displayList();

   cout<<"After remving edges"<<endl;
   graph.remove(e1);
   graph.remove(e3);
   graph.remove(e5);
   graph.remove(e11);

graph.displayList();

   Edge e12(2,6);
   Edge e14(3,7);
   Edge e15(4,6);
   Edge e16(5,2);
   Edge e17(7,7);
   Edge e18(7,8);

   graph.insert(e12);
   graph.insert(e14);
   graph.insert(e15);
   graph.insert(e16);
   graph.insert(e17);
   graph.insert(e18);

   cout<<"after adding self edges"<<endl;
   graph.displayList();

   graph.remove_isolated_vertex();

   cout<<"after removing self loops"<<endl;
   graph.remove_selfloops();
   graph.displayList();

   cout<<"after removing parallel edges"<<endl;
   graph.remove_parellel_edge();
   graph.displayList();

return 0;
}

// header file which was intitially given