Question

C++

The program you write for this lab will read in the number of nodes and a binary relation representing a graph. The program will create an adjacency matrix from the binary relation. The program will then print the following :

1. The adjacency matrix
2. Determine if there are any isolated nodes and print them
3. Determine if an Euler path exists and said so.

The sample run of the program is as follows. The output should just like this: It starts by asking the user to input the number of nodes, then ask the user to input the adjacency relation and then print out the adjacency matrix first, followed by the node that is isolated and then tells the user if an Euler path exist or not.

This is how the program should run and output

Please input the number of nodes:
6
Please input the adjacency relation:
{(1,2),(1,5),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,1),(5,4)}

The Adjacency matrix is:
0 1 0 0 1 0
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0

6 is an isolated node
An Euler path does exist in the graph.

Answer 1

Solution :

Following is the C++ code with comments :

#include<bits/stdc++.h>
using namespace std;
int graph[100][100]; //the adjacency matrix initially 0
int count = 0,nodes;
vector<int> edgenodes;
vector<int> isolatednodes;
void extractIntegerWords(string s) 
{ 
    for(int i=0;i<s.length();++i)
    if(s[i]>'0' && s[i]<='9')
    edgenodes.push_back(s[i]-'0');
} 
void displayMatrix(int v) {
   int i, j;
   for(i = 0; i < v; i++) {
       int sum=0;
      for(j = 0; j < v; j++) {
         cout << graph[i][j] << " ";
         if(graph[i][j])
         sum++;
      }
      if(!sum)
      isolatednodes.push_back(i+1);
      cout << endl;
   }
}
void add_edge(int u, int v) {       //function to add edge into the matrix
   graph[u-1][v-1] = 1;
   graph[v-1][u-1] = 1;
}
void traverse(int u, bool visited[]) {
   visited[u] = true; //mark v as visited
   for(int v = 0; v<nodes; v++) {
      if(graph[u][v]) {
         if(!visited[v])
            traverse(v, visited);
      }
   }
}
bool isConnected() {
   bool *vis = new bool[nodes];
   //for all vertex u as start point, check whether all nodes are visible or not
   for(int u; u < nodes; u++) {
      for(int i = 0; i<nodes; i++)
         vis[i] = false; //initialize as no node is visited
         traverse(u, vis);
         for(int i = 0; i<nodes; i++){
            if(!vis[i]) //if there is a node, not visited by traversal, graph is not connected
               return false;
         }
   }
   return true;
}
//Check if given graph contains an Eulerian path or not
bool isEulerian() {
   if(isConnected() == false) //when graph is not connected
   return 0;
   vector<int> degree(nodes, 0);
   int oddDegree = 0;
   for(int i = 0; i<nodes; i++) {
      for(int j = 0; j<nodes; j++) {
         if(graph[i][j])
            degree[i]++; //increase degree, when connected edge found
      }
      if(degree[i] % 2 != 0) //when degree of vertices are odd
         oddDegree++; //count odd degree vertices
   }
   if(oddDegree > 2) //when vertices with odd degree greater than 2
      return 0;
   return 1; //when oddDegree is 0, it is Euler circuit, and when 2, it is Euler path
}
int main() {
   int nodes;
   cout<<"Please input the number of nodes : "<<endl;
   cin>>nodes;
   cout<<"Please input the adjacency relation : "<<endl;
   string s;
   cin.ignore();
   getline(cin,s);
   extractIntegerWords(s);
   for(int i=0;i<edgenodes.size();i+=2)
   add_edge(edgenodes[i],edgenodes[i+1]);
   cout<<"\nThe adjacency matrix is : \n";
   displayMatrix(nodes);
   cout<<"\nIsolated nodes are : ";
   for(auto i : isolatednodes)
   cout<<i<<" ";
   if(isEulerian())
   cout<<"\nAn Euler path does exist in the graph.";
   else cout<<"\nAn Euler path does not exist in the graph.";   
}

Code demo for reference :