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.

Problem Description

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).

Problem Solution

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.

advertisement
Program/Source Code

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);
}
Program Explanation

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.

advertisement
Runtime Test Cases
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn