# Java Program to Generate a Graph for a Given Fixed Degree Sequence

This is a java program to generate a graph from given degree sequence. The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees.The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The converse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs by a matching, and fill out the remaining even degree counts by self-loops.

Here is the source code of the Java Program to Generate a Graph for a Given Fixed Degree Sequence. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

package com.hinguapps.combinatorial;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class GraphUsingDegreeSequence
{
List<Integer> degreeSequence;

private void addEdges(Integer v, Integer e)
{
for (int i = 0; i < adjecencyMatrix.length && e > 0; i++)
{
if (degreeSequence.get(i) != 0)
{
Integer val = degreeSequence.get(i);
if (val > 0)
degreeSequence.set(i, val - 1);
e--;
}
}
}

public void generateGraph()
{
.size()];
for (int i = 0; i < adjecencyMatrix.length; i++)
{
for (int j = 0; j < adjecencyMatrix.length; j++)
{
}
}
for (int i = 0; i < degreeSequence.size(); i++)
{
Integer e = degreeSequence.get(i);
degreeSequence.set(i, 0);
}
}

public void printGraph()
{
System.out.println("The matrix form of graph: ");
for (int i = 0; i < adjecencyMatrix.length; i++)
{
for (int j = 0; j < adjecencyMatrix.length; j++)
{
}
System.out.println();
}
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of vertices: ");
Integer n = sc.nextInt();
System.out
.println("Enter the Degree Sequence: <Degree sequence is always in non-increasing order>");
GraphUsingDegreeSequence gds = new GraphUsingDegreeSequence();
gds.degreeSequence = new ArrayList<Integer>();
while (n > 0)
{
n--;
}
System.out.println("Entered degree sequence: "
+ gds.degreeSequence.toString());
gds.generateGraph();
gds.printGraph();
sc.close();
}
}


Output:

$javac GraphUsingDegreeSequence.java$ java GraphUsingDegreeSequence

Enter the number of vertices:
7
Enter the Degree Sequence: <Degree sequence is always in non-increasing order>
5 3 3 2 2 1 0
Entered degree sequence: [5, 3, 3, 2, 2, 1, 0]
The matrix form of graph:
0 1 1 1 1 1 0
1 0 1 1 0 0 0
1 1 0 0 1 0 0
1 1 0 0 0 0 0
1 0 1 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0