DEV Community

Matt Ryan
Matt Ryan

Posted on

Havel–Hakimi Algorithm in Java

The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: Given a finite list of nonnegative integers, is there a simple graph such that its degree sequence is exactly this list? The degree sequence is a list of numbers that for each vertex of the graph states how many neighbors it has. For a positive answer, the list of integers is called graphic. The algorithm constructs a special solution if one exists or proves that one cannot find a positive answer. This construction is based on a recursive algorithm. The algorithm was published by Havel (1955), and later by Hakimi (1962).

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
public class HavelHakimi { //Delete all zeros from the list 
  public static void deleteZeros(ArrayList < Integer > list) {
        for (int i = 0; i < list.size(); i++) {
            int num
                = list.get(i);
            if (num == 0) {
                list.remove(i);
                i = 0;
            }
        }
    } //Put thelist in descending order 
    public static void descendingSort(ArrayList list) {
        Collections.sort(list, Collections.reverseOrder());
    }
    //Check the length of the list against a given number       
    public static boolean lengthCheck(int length, ArrayList list) {
        if (length > list.size()) {
            return true;
        } else {
            return false;
        }
    } //Subtract 1 from the first N numbers in the list
    public static void frontElim(int numElim, ArrayList list) {
        System.out.println(numElim);
        System.out.println(list.size());
        if (numElim >= list.size()) {
            System.out.println("Shits fucked.");
        }
        for (int i = 0; i <= numElim; i++) {
            list.set(i, (Integer) list.get(i) -
                1);
        }
    } //Recursively perform the Havel-Hakimi algorithm on a given list 
    public static boolean HavelHakimi(ArrayList list) {
        int N = 0;
        deleteZeros(list);
        if (list.size() == 0) return
        true;
        descendingSort(list);
        N = (int) list.remove(0);
        if (N > list.size()) return false;
        frontElim(N, list);
        return HavelHakimi(list);
    }
    public static void main(String[] args) {
        int numWitness = 10; //create a random list
        Random random = new Random();
        ArrayList < Integer > randList = new ArrayList < Integer > ();
        for (int i = 0; i <= numWitness - 1; i++) {
            randList.add(random.nextInt(15));
        } //Make a pre defined list for testing
        ArrayList < Integer > testList = new ArrayList < Integer > ();
        testList.add(4);
        testList.add(2);
        testList.add(0);
        testList.add(1);
        testList.add(5);
        testList.add(0);
        //Test the algorithm and print the result           
        System.out.println(HavelHakimi(testList));
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)