Question

Write a C++ program that will read in the number of nodes (less than 10) and a adjacency relation representing a graph. The program will create an adjacency matrix from the adjacency relation. The program will then print the following items:
1. Print the adjacency matrix
2. Determine if there are any isolated nodes and print them
3. Determine if an Euler path exists

Sample run (to make program output more clear, I have put it in boldface):
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

Assumptions made:

• The input format for adjacency relation is a string.
• The nodes are numbered from 1 to n, where n is the number of nodes.

// A C++ program to check if a given graph is Eulerian or not
#include<iostream>
#include <list>
using namespace std;

// A class that represents an undirected graph
class Graph
{
   int V; // No. of vertices
   list<int> *adj; // A dynamic array of adjacency lists
public:
   // Constructor and destructor
   Graph(int V) {this->V = V; adj = new list<int>[V]; }
   ~Graph() { delete [] adj; } // To avoid memory leak

   // function to add an edge to graph
   void addEdge(int v, int w);

   // Method to check if this graph is Eulerian or not
   int isEulerian();

   // Method to check if all non-zero degree vertices are connected
   bool isConnected();

   // Function to do DFS starting from v. Used in isConnected();
   void DFSUtil(int v, bool visited[]);
};

void Graph::addEdge(int v, int w)
{
   adj[v].push_back(w);
   adj[w].push_back(v); // Note: the graph is undirected
}

void Graph::DFSUtil(int v, bool visited[])
{
   // Mark the current node as visited and print it
   visited[v] = true;

   // Recur for all the vertices adjacent to this vertex
   list<int>::iterator i;
   for (i = adj[v].begin(); i != adj[v].end(); ++i)
       if (!visited[*i])
           DFSUtil(*i, visited);
}

// Method to check if all non-zero degree vertices are connected.
// It mainly does DFS traversal starting from
bool Graph::isConnected()
{
   // Mark all the vertices as not visited
   bool visited[V];
   int i;
   for (i = 0; i < V; i++)
       visited[i] = false;

   // Find a vertex with non-zero degree
   for (i = 0; i < V; i++)
       if (adj[i].size() != 0)
           break;

   // If there are no edges in the graph, return true
   if (i == V)
       return true;

   // Start DFS traversal from a vertex with non-zero degree
   DFSUtil(i, visited);

   // Check if all non-zero degree vertices are visited
   for (i = 0; i < V; i++)
   if (visited[i] == false && adj[i].size() > 0)
           return false;

   return true;
}

/* The function returns one of the following values
0 --> If grpah is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian) */
int Graph::isEulerian()
{
   // Check if all non-zero degree vertices are connected
   if (isConnected() == false)
       return 0;

   // Count vertices with odd degree
   int odd = 0;
   for (int i = 0; i < V; i++)
       if (adj[i].size() & 1)
           odd++;

   // If count is more than 2, then graph is not Eulerian
   if (odd > 2)
       return 0;

   // If odd count is 2, then semi-eulerian.
   // If odd count is 0, then eulerian
   // Note that odd count can never be 1 for undirected graph
   return (odd)? 1 : 2;
}

// Function to run test cases
void test(Graph &g)
{
   int res = g.isEulerian();
   if (res == 0)
       cout << "graph is not Eulerian\n";
   else if (res == 1)
       cout << "graph has a Euler path\n";
   else
       cout << "graph has a Euler cycle\n";
}

// Driver program to test above function
int main()
{
   // Let us create and test graphs shown in above figures
   Graph g1(5);
   g1.addEdge(1, 0);
   g1.addEdge(0, 2);
   g1.addEdge(2, 1);
   g1.addEdge(0, 3);
   g1.addEdge(3, 4);
   test(g1);

   Graph g2(5);
   g2.addEdge(1, 0);
   g2.addEdge(0, 2);
   g2.addEdge(2, 1);
   g2.addEdge(0, 3);
   g2.addEdge(3, 4);
   g2.addEdge(4, 0);
   test(g2);

   Graph g3(5);
   g3.addEdge(1, 0);
   g3.addEdge(0, 2);
   g3.addEdge(2, 1);
   g3.addEdge(0, 3);
   g3.addEdge(3, 4);
   g3.addEdge(1, 3);
   test(g3);

   // Let us create a graph with 3 vertices
   // connected in the form of cycle
   Graph g4(3);
   g4.addEdge(0, 1);
   g4.addEdge(1, 2);
   g4.addEdge(2, 0);
   test(g4);

   // Let us create a graph with all veritces
   // with zero degree
   Graph g5(3);
   test(g5);

   return 0;
}