C++ 2DArrays binary relations The program you write for this lab will read in th

Question

C++ 2DArrays

binary relations

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 adjacency matrix and 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. 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 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 {,()}'s as chars.

Sample Run

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

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

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;
   //Creates edges
   int edge[10][2] = { {1,2}, {1,5}, {2, 1}, {2,3}, {3,2}, {3,4}, {4,3}, {4,5}, {5,1}, {5,4} };
//Create Graphs with edges information
Graph g1(6);
g1.addEdge(1, 2);
g1.addEdge(1, 5);
g1.addEdge(2, 1);
g1.addEdge(2, 3);
g1.addEdge(3, 2);
g1.addEdge(3, 4);
g1.addEdge(4, 3);
g1.addEdge(4, 5);
g1.addEdge(5, 1);
g1.addEdge(5, 4);
test(g1);
for(int x = 0; x < 10; x++)
{
   for(int y = 0; y < 1; y++)
   {
       to = edge[x][0];
       from = edge[x][1];
       g1.makeEdge(to, from, 1);
   }//End of inner loop
}//End of outer loop
g1.printAdjacencyMatrix();
/*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);
cout<<"Result for Graph 2: ";
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);
cout<<"Result for Graph 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);
cout<<"Result for Graph 4: ";
test(g4);

// Let us create a graph with all veritces
// with zero degree
Graph g5(3);
cout<<"Result for Graph 5: ";
test(g5);*/

return 0;
}

Ourtput:

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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