C++ Discrete Strucs read in the number of nodes and a binary relation representi

Question

C++ Discrete Strucs

read in the number of nodes and a binary relation representing a graph. you will create an adjacency matrix from the binary relation. Then print the adjacency matrix and tell whether or not an Euler path exists. There will be no more than 10 nodes, and you must use a 10X10 2D array for the adjacency matrix. Helpful Note: There is no reason to store the binary relation. Just create the 2D array as you read (so no getline into a string that you then parse). Second helpful note: There are no spaces in the binary relation. Note also that the numbers could be two digits since 10 nodes is possible, so I would read the numbers as ints and the 400's as chars. Sample Run liusta sample run code should work given different input (e.g nodes and binary relation)) How many nodes are in the graph? 6 Please input the binary relation for the graph: (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 101 000 01 01 100 0 0 1 0 1 0 100 100 0 0 0 0 0 0 An Euler path does exist in the graph.

Explanation / Answer

#include<iostream>
#include <list>
using namespace std;
//Class definition
class Graph
{
//To store number of vertices
int V;
// A dynamic array of adjacency lists
list<int> *adjcent;
//For adjacency matrix
int adjacencyMatrix [50][50];

public:
// Constructor and destructor
Graph(int v)
{
V = v;
adjcent = new list<int> [V];
for(int x = 0; x < 50; x++)
for(int y = 0; y < 50; y++)
adjacencyMatrix[x][y] = 0;
}//End of constructor
//Destructor
~Graph()
{
delete[] adjcent;
} // End of destructor

//To add an edge to graph
void addEdge(int v, int w);
//To check if this graph is Eulerian or not
int isEulerian();
//To check if all Non - Zero degree vertices are connected
bool isConnected();
//To do DFS starting from v. Used in isConnected();
void DFSMethod(int v, bool visitedArray[]);
//To make an edge
void makeEdge(int, int, int);
//To return edges
int getEdge(int, int);
//To display adjacency matrix
void printAdjacencyMatrix();
};//End of class
//To make an edge
void Graph::makeEdge(int to, int from, int edge)
{
try
{
   //If the edge is available 1 otherwise default value zero
adjacencyMatrix[to][from] = edge;
}
catch (int i)
{
cout<<"The vertices does not exists";
}
}//End of method

//To return edges
int Graph::getEdge(int to, int from)
{
try
{
return adjacencyMatrix[to][from];
}
catch (int i)
{
cout<<"The vertices does not exists";
}
return -1;
}//End of method

//To display adjacency matrix
void Graph::printAdjacencyMatrix()
{
cout<<"The adjacency matrix for the given graph is: ";
cout<<" ";
//Displays the column number
for (int i = 1; i <= V; i++)
cout<<i<<" ";
cout<<endl;
//Loops upto Vertices
for (int i = 1; i <= V; i++)
{
   //Displays row number
cout<<i<<" -> ";
for (int j = 1; j <= V; j++)
   //Displays matrix data
cout<<getEdge(i, j)<<" ";
cout<<endl;
}//End of for
}//End of method

void Graph::addEdge(int pos, int wait)
{
adjcent[pos].push_back(wait);
}//End of function

//For DFS
void Graph::DFSMethod(int pos, bool visitedArray[])
{
// Mark the current node as visited
visitedArray[pos] = true;

// Iterates all the vertices adjacent to this vertex
list<int>::iterator c;
for (c = adjcent[pos].begin(); c != adjcent[pos].end(); ++c)
{
if (!visitedArray[*c])
{
DFSMethod(*c, visitedArray);
}//End of if
}//End of for
}//End of function

//To check if all Non - Zero degree vertices are connected.
bool Graph::isConnected()
{
// Mark all the vertices as not visited
bool visitedArray[V];
int c;
for (c = 0; c < V; c++)
visitedArray[c] = false;
// Find a vertex with Non - Zero degree
for (c = 0; c < V; c++)
if (adjcent[c].size() != 0)
break;
// If there are no edges in the graph, return true
if (c == V)
return true;

// Start DFS traversal from a vertex with Non - Zero degree
DFSMethod(c, visitedArray);
// Check if all Non - Zero degree vertices are visited
for (c = 0; c < V; c++)
if (visitedArray[c] == false && adjcent[c].size() > 0)
return false;
return true;
}//End of function

// Function returns:
// 0 If graph 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 oddNo = 0;
for (int c = 0; c < V; c++)
if (adjcent[c].size() & 1)
oddNo++;

// If count is more than 2, then graph is not Eulerian
if (oddNo > 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 (oddNo) ? 1 : 2;
}//End of function

//To run test cases
void test(Graph &g)
{
int myRes = g.isEulerian();
if (myRes == 0)
cout << "Graph is not Eulerian ";
else if (myRes == 1)
cout << "Graph has a Euler path ";
else
cout << "Graph has a Euler cycle ";
}//End of function

// Driver function to test above function
int main()
{
int to = 0, from = 0;
int ver, ed;
   //Creates edges
   int edge[50][2];
   //Accepts number of vertices
cout<<" Enter number of vertices: ";
cin>>ver;
//Create Graphs with edges information
Graph g1(ver);
//Accepts number of edges
cout<<" Enter number of edges: ";
cin>>ed;
//Accepts edges
cout<<" Enter the edges: ";
//Loops till edges
for(int x = 0; x < ed; x++)
{
   for(int y = 0; y < 1; y++)
   {
   //Accept from and to of the edges
   cout<<" Enter From Edge: ";
   cin>>edge[x][1];
   cout<<" Enter To Edge: ";
   cin>>edge[x][0];
   g1.addEdge(edge[x][0], edge[x][1]);
       to = edge[x][0];
       from = edge[x][1];
       g1.makeEdge(to, from, 1);
   }//End of inner loop
}//End of outer loop
test(g1);
g1.printAdjacencyMatrix();

   return 0;

}//End of main function

Sample Run 1:

Enter number of vertices: 6

Enter number of edges: 10

Enter the edges:

Enter From Edge: 1

Enter To Edge: 2

Enter From Edge: 1

Enter To Edge: 5

Enter From Edge: 2

Enter To Edge: 1

Enter From Edge: 2

Enter To Edge: 3

Enter From Edge: 3

Enter To Edge: 2

Enter From Edge: 3

Enter To Edge: 4

Enter From Edge: 4

Enter To Edge: 3

Enter From Edge: 4

Enter To Edge: 5

Enter From Edge: 5

Enter To Edge: 1

Enter From Edge: 5

Enter To Edge: 4

Graph has a Euler cycle
The adjacency matrix for the given graph is:
1 2 3 4 5 6
1 -> 0 1 0 0 1 0
2 -> 1 0 1 0 0 0
3 -> 0 1 0 1 0 0
4 -> 0 0 1 0 1 0
5 -> 1 0 0 1 0 0
6 -> 0 0 0 0 0 0

Sample Run 2:

Enter number of vertices: 5

Enter number of edges: 6

Enter the edges:

Enter From Edge: 1

Enter To Edge: 0

Enter From Edge: 0

Enter To Edge: 2

Enter From Edge: 2

Enter To Edge: 1

Enter From Edge: 0

Enter To Edge: 3

Enter From Edge: 3

Enter To Edge: 4

Enter From Edge: 1

Enter To Edge: 3
Graph is not Eulerian
The adjacency matrix for the given graph is:
1 2 3 4 5
1 -> 0 1 0 0 0
2 -> 0 0 0 0 0
3 -> 1 0 0 0 0
4 -> 0 0 1 0 0
5 -> 0 0 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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