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

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[], 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 = {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]--;
}
}
}

}```
Program Explanation

1. Take the input of the number of vertexes and their corresponding degree.
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.

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. 