4
\$\begingroup\$

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;

    Graph(Map<Integer, int[]> adjacencyList) {
        initialize(adjacencyList);
    }

    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.get(node).add(neighbor);

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

        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[]>();
        adjacencyList.put(1, new int[]{2});
        adjacencyList.put(2, new int[]{1, 3});
        adjacencyList.put(3, new int[]{4, 5});

        Graph g = new Graph(adjacencyList);
        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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Max Sep 7 '17 at 3:27
1
\$\begingroup\$

The reason more seems to be that the code doesn't need much improvement.

Some minor remarks from my side:

  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) {
  5. Try to have only one top-level class per file in real projects.
\$\endgroup\$
  • \$\begingroup\$ Thank you! Solid feedback, I didn't know it's also possible to use for-each on the primitive arrays. \$\endgroup\$ – Max Sep 8 '17 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.