C++ Programming Code Examples

C++ > Sorting Searching Code Examples

Check if any Graph is Possible to be Constructed for a Given Degree Sequence



Check if any Graph is Possible to be Constructed for a Given Degree Sequence

- This algorithm checks whether a undirected graph can be generated from a given degree sequence.
- The graph should not have a self-edge and multiple edges.
- The time complexity of this algorithm is O(v*v).

- This algorithm takes the input of the number of vertexes and their corresponding degree.
- It Checks various constraints and tries to build the graph.
- If it fails, no valid graph can be created from the given sequence.
- Exit.

#include<iostream>
#include<iomanip>
 
using namespace std;
 
// A function to print the adjacency matrix.
void PrintMat(int mat[][20], int n)
{
	int i, j;
 
	cout<<"\n\n"<<setw(3)<<"       ";
	for(i = 0; i < n; i++)
		cout<<setw(3)<<"("<<i+1<<")";
	cout<<"\n\n";
 
	// Print 1 if the corresponding vertexes are connected otherwise 0.
	for(i = 0; i < n; i++)
	{
		cout<<setw(4)<<"("<<i+1<<")";
		for(j = 0; j < n; j++)
		{
			cout<<setw(5)<<mat[i][j];
		}
		cout<<"\n\n";
	}
}
 
int main()
{
	int NOV, i, j, AdjMat[20][20] = {0};
	cout<<"Enter the number of vertex in the graph: ";
	cin>>NOV;
 
	int degseq[NOV];
	// Take input of the degree sequence.
	for(i = 0; i < NOV; i++)
	{
		cout<<"Enter the degree of "<<i+1<<" vertex: ";
		cin>>degseq[i];
	}
 
	for(i = 0; i < NOV; i++)
	{
		for(j = i+1; j < NOV; j++)
		{
			// For each pair of vertex decrement the degree of both vertex.
			if(degseq[i] > 0 && degseq[j] > 0)
			{
				degseq[i]--;
				degseq[j]--;
				AdjMat[i][j] = 1;
				AdjMat[j][i] = 1;
			}
		}
	}
 
	PrintMat(AdjMat, NOV);
}