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.

  1.  
  2. package com.hinguapps.combinatorial;
  3.  
  4. import java.util.ArrayList;
  5. import java.util.List;
  6. import java.util.Scanner;
  7.  
  8. public class GraphUsingDegreeSequence
  9. {
  10.     Integer[][] adjecencyMatrix;
  11.     List<Integer> degreeSequence;
  12.  
  13.     private void addEdges(Integer v, Integer e)
  14.     {
  15.         for (int i = 0; i < adjecencyMatrix.length && e > 0; i++)
  16.         {
  17.             if (degreeSequence.get(i) != 0)
  18.             {
  19.                 adjecencyMatrix[v][i] = adjecencyMatrix[i][v] = 1;
  20.                 Integer val = degreeSequence.get(i);
  21.                 if (val > 0)
  22.                     degreeSequence.set(i, val - 1);
  23.                 e--;
  24.             }
  25.         }
  26.     }
  27.  
  28.     public void generateGraph()
  29.     {
  30.         adjecencyMatrix = new Integer[degreeSequence.size()][degreeSequence
  31.                 .size()];
  32.         for (int i = 0; i < adjecencyMatrix.length; i++)
  33.         {
  34.             for (int j = 0; j < adjecencyMatrix.length; j++)
  35.             {
  36.                 adjecencyMatrix[i][j] = 0;
  37.             }
  38.         }
  39.         for (int i = 0; i < degreeSequence.size(); i++)
  40.         {
  41.             Integer e = degreeSequence.get(i);
  42.             degreeSequence.set(i, 0);
  43.             addEdges(i, e);
  44.         }
  45.     }
  46.  
  47.     public void printGraph()
  48.     {
  49.         System.out.println("The matrix form of graph: ");
  50.         for (int i = 0; i < adjecencyMatrix.length; i++)
  51.         {
  52.             for (int j = 0; j < adjecencyMatrix.length; j++)
  53.             {
  54.                 System.out.print(adjecencyMatrix[i][j] + " ");
  55.             }
  56.             System.out.println();
  57.         }
  58.     }
  59.  
  60.     public static void main(String[] args)
  61.     {
  62.         Scanner sc = new Scanner(System.in);
  63.         System.out.println("Enter the number of vertices: ");
  64.         Integer n = sc.nextInt();
  65.         System.out
  66.                 .println("Enter the Degree Sequence: <Degree sequence is always in non-increasing order>");
  67.         GraphUsingDegreeSequence gds = new GraphUsingDegreeSequence();
  68.         gds.degreeSequence = new ArrayList<Integer>();
  69.         while (n > 0)
  70.         {
  71.             gds.degreeSequence.add(sc.nextInt());
  72.             n--;
  73.         }
  74.         System.out.println("Entered degree sequence: "
  75.                 + gds.degreeSequence.toString());
  76.         gds.generateGraph();
  77.         gds.printGraph();
  78.         sc.close();
  79.     }
  80. }

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.