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
```
```
{
```
```
    Integer[][] adjecencyMatrix;
```
```
    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)

```
            {
```

                adjecencyMatrix[v][i] = adjecencyMatrix[i][v] = 1;

                Integer val = degreeSequence.get(i);

```
                if (val > 0)
```

                    degreeSequence.set(i, val - 1);

```
                e--;
```
```
            }
```
```
        }
```
```
    }
```
```
 
```
```
    public void generateGraph()
```
```
    {
```

        adjecencyMatrix = new Integer[degreeSequence.size()][degreeSequence

```
                .size()];
```

        for (int i = 0; i < adjecencyMatrix.length; i++)

```
        {
```

            for (int j = 0; j < adjecencyMatrix.length; j++)

```
            {
```

                adjecencyMatrix[i][j] = 0;

```
            }
```
```
        }
```

        for (int i = 0; i < degreeSequence.size(); i++)

```
        {
```

            Integer e = degreeSequence.get(i);

```
            degreeSequence.set(i, 0);
```
```
            addEdges(i, e);
```
```
        }
```
```
    }
```
```
 
```
```
    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.print(adjecencyMatrix[i][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)
```
```
        {
```

            gds.degreeSequence.add(sc.nextInt());

```
            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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Check if Any Graph is Possible to be Constructed for a Given Degree Sequence

» Next - Java Program to Implement Heap’s Algorithm for Generating Permutations

Related Posts:

Recommended Articles: