/*Write a program to find union, intersection,
complement,
sum and difference of two graphs. Use adjacency list for
representing the graph.
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int adjmat1[100][100], adjmat2[100][100];
void Union(int n1, int n2)
{
int n3 = max(n1, n2);
int answer[n3 + 1][n3 + 1], i, j;
for (i = 0; i <= n3; i++)
{
for (j = 0; j <= n3; j++)
answer[i][j] = 0;
}
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n1; j++)
{
if (adjmat1[i][j] == 1)
answer[i][j] = 1;
}
}
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
{
if (adjmat2[i][j] == 1)
answer[i][j] = 1;
}
}
cout << "Union of both the Graphs is : " << endl;
for (i = 0; i <= n3; i++)
{
for (j = 0; j <= n3; j++)
{
if (answer[i][j] == 1)
{
cout << i << " " << j << endl;
answer[i][j] = 0;
answer[j][i] = 0;
}
}
}
}
void Intersection(int n1, int n2)
{
int n3 = min(n1, n2);
int answer[n3 + 1][n3 + 1], i, j;
for (i = 0; i <= n3; i++)
{
for (j = 0; j <= n3; j++)
{
if ((adjmat1[i][j] == 1 && adjmat1[j][i] == 1)
&& (adjmat2[i][j] == 1 && adjmat2[j][i] == 1))
answer[i][j] = 1;
}
}
cout << "Intersection of both the graphs is : " << endl;
for (i = 0; i <= n3; i++)
{
for (j = 0; j <= n3; j++)
{
if (answer[i][j] == 1)
{
cout << i << " " << j << endl;
answer[i][j] = 0;
answer[j][i] = 0;
}
}
}
}
void Complement(int n1, int n2)
{
int i, j, temp1[100][100], temp2[100][100];
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n1; j++)
temp1[i][j] = adjmat1[i][j];
}
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n1; j++)
{
if (adjmat1[i][j] == 1)
{
adjmat1[i][j] = -1;
adjmat1[j][i] = -1;
}
else if (i != 0 && j != 0 && adjmat1[i][j] == 0)
{
adjmat1[i][j] = 2;
adjmat1[j][i] = 2;
}
}
}
cout << "Complement of Graph 1 :" << endl;
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n1; j++)
{
if (adjmat1[i][j] == 2 && i != j)
{
cout << i << " " << j << endl;
adjmat1[i][j] = 0;
adjmat1[j][i] = 0;
}
}
}
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
temp2[i][j] = adjmat2[i][j];
}
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
{
if (adjmat2[i][j] == 1)
{
adjmat2[i][j] = -1;
adjmat2[j][i] = -1;
}
else if (i != 0 && j != 0 && adjmat2[i][j] == 0)
{
adjmat2[i][j] = 2;
adjmat2[j][i] = 2;
}
}
}
cout << "Complement of Graph 2 :" << endl;
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
{
if (adjmat2[i][j] == 2 && i != j)
{
cout << i << " " << j << endl;
adjmat2[i][j] = 0;
adjmat2[j][i] = 0;
}
}
}
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n1; j++)
adjmat1[i][j] = temp1[i][j];
}
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
adjmat2[i][j] = temp2[i][j];
}
}
void Difference(int n1, int n2)
{
int i, j;
int temp1[100][100], temp2[100][100];
int choose;
cout << "Enter you choice :\n1.Graph1 -
Graph2\n2.Graph2 - Graph1" << endl;
cin >> choose;
if (choose == 1)
{
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n1; j++)
{
temp1[i][j] = adjmat1[i][j];
if (adjmat1[i][j] == 1 && (adjmat2[i][j] == 1
&& adjmat2[j][i] == 1))
{
adjmat1[i][j] = 0;
adjmat1[i][j] = 0;
}
}
}
cout << "Difference of Graph1 - Graph2 : " << endl;
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n2; j++)
{
if (adjmat1[i][j] == 1)
{
cout << i << " " << j << endl;
adjmat1[i][j] = 0;
adjmat1[j][i] = 0;
}
}
}
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n1; j++)
{
adjmat1[i][j] = temp1[i][j];
}
}
}
else
{
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
{
temp2[i][j] = adjmat2[i][j];
if (adjmat2[i][j] == 1 && (adjmat1[i][j] == 1
&& adjmat1[j][i] == 1))
{
adjmat2[i][j] = 0;
adjmat2[i][j] = 0;
}
}
}
cout << "Difference of Graph2 - Graph1 : " << endl;
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
{
if (adjmat2[i][j] == 1)
{
cout << i << " " << j << endl;
adjmat2[i][j] = 0;
adjmat2[j][i] = 0;
}
}
}
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
{
adjmat2[i][j] = temp2[i][j];
}
}
}
}
void ringsum(int n1,int n2)
{
int n3 = max(n1, n2);
int answer1[n3 + 1][n3 + 1], i, j;
for (i = 0; i <= n3; i++)
{
for (j = 0; j <= n3; j++)
answer1[i][j] = 0;
}
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n1; j++)
{
if (adjmat1[i][j] == 1)
answer1[i][j] = 1;
}
}
for (i = 0; i <= n2; i++)
{
for (j = 0; j <= n2; j++)
{
if (adjmat2[i][j] == 1)
answer1[i][j] = 1;
}
}
int n4 = min(n1, n2);
int answer2[n4 + 1][n4 + 1];
for (i = 0; i <= n4; i++)
{
for (j = 0; j <= n4; j++)
{
if ((adjmat1[i][j] == 1 && adjmat1[j][i] == 1)
&& (adjmat2[i][j] == 1 && adjmat2[j][i] == 1))
answer2[i][j] = 1;
}
}
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n2; j++)
{
if (answer1[i][j] == 1 && (answer2[i][j] == 1
&& answer2[j][i] == 1))
{
answer1[i][j] = 0;
answer1[i][j] = 0;
}
}
}
cout << "Ring sum of Graph1 - Graph2 : " << endl;
for (i = 0; i <= n1; i++)
{
for (j = 0; j <= n2; j++)
{
if (answer1[i][j] == 1)
{
cout << i << " " << j << endl;
}
}
}
}
int main()
{
int vertex_1, vertex_2, number_of_edges_1,
number_of_edges_2;
int number_of_vertices_1, number_of_vertices_2;
cout << "Enter the number of vertices of 1st graph : ";
cin >> number_of_vertices_1;
cout << "Enter the number of edges of 1st graph : ";
cin >> number_of_edges_1;
cout << "Enter the edges like 1 2: " << endl;
for (int i = 0; i <= number_of_vertices_1; i++)
{
for (int j = 0; j <= number_of_vertices_1; j++)
adjmat1[i][j] = 0;
}
for (int i = 0; i < number_of_edges_1; i++)
{
cin >> vertex_1 >> vertex_2;
adjmat1[vertex_1][vertex_2] = 1;
adjmat1[vertex_2][vertex_1] = 1;
}
cout << "Enter the number of vertices of 2nd graph :
";
cin >> number_of_vertices_2;
cout << "Enter the number of edges of 2nd graph : ";
cin >> number_of_edges_2;
for (int i = 0; i <= number_of_vertices_2; i++)
{
for (int j = 0; j <= number_of_vertices_2; j++)
adjmat2[i][j] = 0;
}
cout << "Enter the edges like 1 3 : " << endl;
for (int i = 0; i < number_of_edges_2; i++)
{
cin >> vertex_1 >> vertex_2;
adjmat2[vertex_1][vertex_2] = 1;
adjmat2[vertex_2][vertex_1] = 1;
}
int choose = 1;
while (choose == 1)
{
cout << "Enter your choice : \n1.Union of
graphs\n2.Intersection of graphs\n3.Complement of
graphs\n4.Ringsum of graphs\n5.Difference of graphs"
<< endl;
int choice;
cin >> choice;
switch (choice)
{
case 1:
Union(number_of_vertices_1,
number_of_vertices_2);
break;
case 2:
Intersection(number_of_vertices_1,
number_of_vertices_2);
break;
case 3:
Complement(number_of_vertices_1,
number_of_vertices_2);
break;
case 4:
ringsum(number_of_vertices_1,
number_of_vertices_2);
break;
case 5:
Difference(number_of_vertices_1,
number_of_vertices_2);
break;
default:
cout << "You enter wrong Choice";
break;
}
cout << "Do you want to run again ?\nEnter 1 for
Yes\nEnter 2 for No\n";
cin >> choose;
}
}
Comments
Post a Comment