I am working with C++. Complete the unweighted graph implementation provided. Yo

Question

I am working with C++.

Complete the unweighted graph implementation provided. You will need to implement the various functions (constructor, addVertex, addEdge, print) and determine the data members. It is an unweighted graph; you can choose a directed/or undirected.

* graph() constructs an empty graph

* addVertex() adds a vertex to your graph and returns its nodeid (an unsigned int). Starts at 0, then 1, etc.

* addEdge(to,from) adds an edge from nodeid to to nodeid from. If your graph is undirected, also adds the other edge.

* print() prints out the structure of the graph (node 0 is connected to nodes i, j, k and etc)

I have included the class file so far. I need help constructing the implementation file and running it with a driver:

// Incomplete unweighted graph implementation. Provides interface

class graph
{
public:
graph();
  
unsigned int addVertex();
void addEdge(unsigned in from, unsigned int to);
void print() const;
  
private:
// Todo: Your choice. Matrix or list?
};

Explanation / Answer

The answer is as follows:

The code is as follows:

#include<iostream.h>

struct node{
   int node_id;
   struct node *edge; // this will point to list of nodes connected to this node
   struct node *next; // this will point to next vertex or node.
};

class graph
{
    private:
      node *first;
      int num_vertex;

    public:
       graph(){
         first = NULL;
         last = first;
         num_vertex = 0;
       }
       int addVertex(){
           node *temp,*ptr;
           num_vertex++;
           temp = new node();
           temp->node_id = num_vertex;
           temp->next = NULL;
           temp->edge = NULL;
           if (first == NULL){
               first = temp;
           }
           else {
               ptr = first;
               while (ptr->next != NULL)
                   ptr = ptr->next;
               ptr->next = temp;
           }
           return num_vertex;
       }
       void addEdge(unsigned int from, unsigned int to){
           node *temp,*ptr;
           temp = new node();
           temp->node_id = to;
           temp->next = NULL;
           temp->edge = NULL;
           if (first == NULL){
               cout << "Graph is empty. Please add the vertices first" << endl;
           }
           else {
               ptr = first;
               while (ptr != NULL){
                   if (ptr->info == from)
                      break;
                   ptr = ptr->next;
               }
               if (ptr != NULL){
                  while (ptr->edge != NULL)
                    ptr = ptr->edge;
                  ptr->edge = temp;
                  cout << "Edge added" << endl;
               }
               else {
                  cout << "From vertex not found" << endl;
               }
           }
       }

      void print(){
           node *ptr, *edge;
           if (first == NULL){
               cout << "Graph is empty." << endl;
           }
           else {
               ptr = first;
               while (ptr != NULL){
                   cout << "Node id:" << ptr->node_id << " Connected to:";
                   edge = ptr->edge;
                   while (edge != NULL){
                         cout << edge->node_id << " ";
                         edge = edge->edge;
                   }
                   cout << endl;
                   ptr = ptr->next;
               }
           }
       }

};

void main(){

     graph gr;
     int choice;
     int from;
     int to;
    
   
     do {
        cout << "1. Add vertex" << endl;
        cout << "2. Add Edge" << endl;
        cout << "3. Print Graph" << endl;
        cout << "4. Quit" << endl;
        cout << "Enter choice:" << endl;
        cin >> choice;
        switch (choice) {
            case 1:
                   cout << "Nodeid:" << gr.addVertex() << " Added" << endl;
            case 2:
                   cout << "Enter from vertex:";
                   cin >> from;
                   cout << "Enter to vertex:";
                   cin >> from;
                   if (from > 0 && to > 0){
                      gr.addEdge(from,to);
                   }
            case 3:
                   gr.print();
        }
     } while (choice != 4)

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.