# Greedy graph coloring

For taking part in a course, I need to learn some Java. Unfortunately they only teach Java 1.6, so I understand that later versions could simplify the below code a lot, but I have to stick with 1.6 though, at least for the course.

I have zero prior knowledge of Java, in order to prepare for the course, I implemented a simple greedy algorithm for coloring a simple graph based on a given adjacency list. Any comments for improving the code are welcome, but please keep in mind it has to be compatible with Java version 1.6.

import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.BitSet;
import java.util.TreeMap;
import java.util.Comparator;

class Graph {
final private static int UNCOLORED = -1;

private int maxDegree = 0;
private Map<Integer, Set<Integer>> edges = new HashMap<Integer, Set<Integer>>();
private Map<Integer, Integer> nodesSortedByDegree;

}

private void initialize(Map<Integer, int[]> adjacencyList) {
Map<Integer, Integer> degrees = new HashMap<Integer, Integer>();

for (Map.Entry<Integer, int[]> entry : adjacencyList.entrySet()) {
int node = entry.getKey();
int[] neighbors = entry.getValue();

// calculate degree for node
int degree = degrees.getOrDefault(node, 0);
int newDegree = degree + neighbors.length;

if (newDegree > maxDegree) {
maxDegree = newDegree;
}

degrees.put(node, newDegree);

for (int i = 0; i < neighbors.length; i++) {
int neighbor = neighbors[i];

// calculate degree for neighbors
degree = degrees.getOrDefault(neighbor, 0);
newDegree = degree + 1;

if (newDegree > maxDegree) {
maxDegree = newDegree;
}

degrees.put(neighbor, newDegree);

// add edge from/to node and neighbor
edges.putIfAbsent(node, new HashSet<Integer>());

edges.putIfAbsent(neighbor, new HashSet<Integer>());
}
}

nodesSortedByDegree = new TreeMap<Integer, Integer>(new MapValuesComparator(degrees));
nodesSortedByDegree.putAll(degrees);
}

public Map<Integer,Integer> greedyColoring() {
int maxColors = maxDegree + 1;
System.out.printf("# We can color G using at most %d colors.\n", maxColors);

Map<Integer, Integer> coloring = new HashMap<Integer, Integer>();
BitSet used = new BitSet(maxColors);

for (Map.Entry<Integer, Integer> entry : nodesSortedByDegree.entrySet()) {
int node = entry.getKey();
Set<Integer> neighbors = edges.get(node);

// color neighbors first
for (Integer neighbor : neighbors) {
int neighborColor = coloring.getOrDefault(neighbor, UNCOLORED);

if (neighborColor == UNCOLORED) {
int nextColor = used.nextClearBit(0);
coloring.put(neighbor, nextColor);

used.flip(nextColor);
} else {
used.flip(neighborColor);
}
}

// then assign the first left over color to node
int nodeColor = used.nextClearBit(0);
coloring.put(node, nodeColor);

used.clear();
}

return coloring;
}
}

public class Main {
final private static String[] COLORS = new String[] {
"red", "green", "blue", "yellow", "pink", "black",
};

public static void main(String[] args) {
Map<Integer, int[]> adjacencyList = new HashMap<Integer, int[]>();

Map<Integer, Integer> coloring = g.greedyColoring();

dumpColoring(coloring);
}

private static void dumpColoring(Map<Integer, Integer> coloring) {
System.out.println("=====================");

for (Map.Entry<Integer, Integer> e : coloring.entrySet()) {
System.out.printf("# Color %d in %s\n", e.getKey(), COLORS[e.getValue()]);
}
}
}

class MapValuesComparator implements Comparator<Integer> {
private Map<Integer, Integer> m;

public MapValuesComparator(Map<Integer, Integer> m) {
this.m = m;
}

public int compare(Integer a, Integer b) {
int compare = m.get(b).compareTo(m.get(a));

if (compare == 0) {
return 1;
}

return compare;
}
}


The program roughly works like this:

• Build a list with edges in both directions from the given adjacency list.
• Compute max. degree to find out how much colors we need to use at most.
• Sort vertices by degree.

The actual coloring:

• iterates the vertices sorted by degree.
• colors all neighbors and the node itself.

The output should be sth like:

# We can color G using at most 4 colors.
=====================
# Color 1 in red
# Color 2 in blue
# Color 3 in yellow
# Color 4 in red
# Color 5 in red

• Haha no one want's to have a look at my java code from the stoneage. Maybe it's a bit unreasonable constraint to expect people to review outdated code … let's me also doubt a bit for what kind of course I signed up.
– BMBM
Sep 7, 2017 at 3:27

1. The following of your statements are actually not compatible with Java 1.6: Map.getOrDefault and Map.putIfAbsent. You can verify this by looking at the JavaDoc expression @since 1.8.
2. Use a logger instead of System.out.println if you're implementing more than just quick and dirty demo code.
3. The Java Style Guidelines recommend that final should go after private static
4. You can use for-each loops on primitive arrays to eliminate the need for non-describing variables such as i: for (final int neighbor : neighbors) {