Question

Write a C++ program 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

ALGORITHM

• As input of adjacency relation is given in the form of string so we can se that there is a pattern in the string to make it as a adjacency matrix.
• The patter is every 6 position element is our x and 6+2 is our y element and we start loop from 2 example {(1,2),(1,5),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,1),(5,4)} at position 2 we have x=1 and y will be at positon 4(2+2) so y=2 again adding 6 in the loop next x will be at 8th and y will be at 10th and so on.
• Then we find indegree of each vertices to find isolated vertices and then we find eulerian path.

#include<bits/stdc++.h>
using namespace std;
void MakeAdj(string s,vector<vector<int>> &mat,int n,int ind[])
{
   for(int i=2;i<s.size()-2;i+=6)
   {
           
           int x=(int)s[i]-'0';
           int y=(int)s[i+2]-'0';
           // for undirected graph
           mat[x-1][y-1]=1;
           mat[y-1][x-1]=1;
           
           // increasing indegree to find isolated vertices
           ind[y]++;
           ind[x]++;
   }
}
bool hasEulerPath(vector<vector<int>> mat,int n)
{
        vector<int> adj; 
  
    for (int i = 0; i < n; i++) 
        adj.push_back(accumulate(mat[i].begin(),mat[i].end(), 0)); 
  
    int start = 0, odd = 0; 
    for (int i = n - 1; i >= 0; i--) 
    { 
        if (adj[i] % 2 == 1) 
        { 
            odd++; 
            start = i; 
        } 
    } 
    if (odd > 2)  
    { 
        return false; 
    } 
    
     
    stack<int> st; 
    vector<int> path; 
    int cur = start; 
  
    while (!st.empty() || accumulate(mat[cur].begin(),mat[cur].end(), 0) != 0) 
    { 
        if (accumulate(mat[cur].begin(), mat[cur].end(), 0) == 0) 
        { 
            path.push_back(cur); 
            cur = st.top(); 
            st.pop(); 
        } 
        else 
        { 
            for (int i = 0; i < n; i++) 
            { 
                if (mat[cur][i] == 1)  
                { 
                    st.push(cur); 
                    mat[cur][i] = 0; 
                    mat[i][cur] = 0; 
                    cur = i; 
                    break; 
                } 
            } 
        } 
    } 
  
    if(path.size()>0)
    return true;
    else
    return false;
}
int main()
{
        int n;
        cout<<"Please input the number of nodes:\n";
        cin>>n;
        cin.ignore();
        string s;
        cout<<"Please input the adjacency relation:\n";
        getline(cin,s);
        int ind[n+1]={0};
        vector<vector<int>> mat(n,vector<int>(n,0));
        
        // String Parsing
        MakeAdj(s,mat,n,ind);
        
        //Adjacency Matrix
        cout<<"The Adjacency matrix is:\n";
        
        for(int i=0;i<n;i++)
        {
                for(int j=0;j<n;j++)
                {
                        cout<<mat[i][j]<<" ";
                }
                cout<<endl;
        }
        
        
        //Isolated node
        for(int i=1;i<=n;i++)
        if(ind[i]==0)
                cout<<i<<" ";
        cout<<"is an isolated node\n";
        
        
        //Euler Path
        int x=hasEulerPath(mat,n);
        if(x==1)
        {
                cout<<"An Euler path does exist in the graph.\n";
        }
        else
        cout<<"An Euler path does not exist in the graph.\n";
}

OUTPUT