C++ Program to Generate a Graph for a Given Fixed Degree Sequence

This is a C++ program to generate a graph for a given fixed degree sequence.

1. This algorithm generates a undirected graph for the given degree sequence.
2. It does not include self-edge and multiple edges.
3. The time complexity of this algorithm is O(v*v).

1. This algorithm takes the input of the number of vertexes and their corresponding degree.
2. It connects vertexes and decreases the degree of both the vertex.

C++ Program to generate a graph for a given fixed degree sequence.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#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);
}

1. Take the input of the number of vertexes and their corresponding degree.
2. Declare adjacency matrix, AdjMat[][] to store the graph.
3. To create the graph, create the first loop to connect each vertex ‘i’.
4. Second nested loop to connect the vertex ‘i’ to the every valid vertex ‘j’, next to it.
5. If the degree of vertex ‘i’ and ‘j’ are more than zero then connect them.
6. Print the adjacency matrix using PrintMat().
7. Exit.

Case 1:
Enter the number of vertex in the graph: 7
Enter the degree of 1 vertex: 5
Enter the degree of 2 vertex: 3
Enter the degree of 3 vertex: 3
Enter the degree of 4 vertex: 2
Enter the degree of 5 vertex: 2
Enter the degree of 6 vertex: 1
Enter the degree of 7 vertex: 0
 
 
         (1)  (2)  (3)  (4)  (5)  (6)  (7)
 
   (1)    0    1    1    1    1    1    0
 
   (2)    1    0    1    1    0    0    0
 
   (3)    1    1    0    0    1    0    0
 
   (4)    1    1    0    0    0    0    0
 
   (5)    1    0    1    0    0    0    0
 
   (6)    1    0    0    0    0    0    0
 
   (7)    0    0    0    0    0    0    0
 
Case 2:
Enter the number of vertex in the graph: 5
Enter the degree of 1 vertex: 2
Enter the degree of 2 vertex: 2
Enter the degree of 3 vertex: 2
Enter the degree of 4 vertex: 2
Enter the degree of 5 vertex: 2
 
 
         (1)  (2)  (3)  (4)  (5)
 
   (1)    0    1    1    0    0
 
   (2)    1    0    1    0    0
 
   (3)    1    1    0    0    0
 
   (4)    0    0    0    0    1
 
   (5)    0    0    0    1    0

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.