### Question:
SaturationDegreeColoring implements VertexColoringAlgorithm<V> { @Override @SuppressWarnings("unchecked") public Coloring<V> getColoring() { int n = graph.vertexSet().size(); int maxColor = -1; Map<V, Integer> colors = new HashMap<>(n); Map<V, BitSet> adjColors = new HashMap<>(n); Map<V, Integer> saturation = new HashMap<>(n); int maxDegree = 0; Map<V, Integer> degree = new HashMap<>(n); for (V v : graph.vertexSet()) { int d = graph.edgesOf(v).size(); degree.put(v, d); maxDegree = Math.max(maxDegree, d); adjColors.put(v, new BitSet()); saturation.put(v, 0); } Heap heap = new Heap(n, new DSaturComparator(saturation, degree)); Map<V, HeapHandle> handles = new HashMap<>(); for (V v : graph.vertexSet()) { handles.put(v, new HeapHandle(v)); } heap.bulkInsert( handles.values().toArray((HeapHandle[]) Array.newInstance(HeapHandle.class, 0))); while (heap.size() > 0) { V v = heap.deleteMin().vertex; BitSet used = adjColors.get(v); int c = used.nextClearBit(0); maxColor = Math.max(maxColor, c); colors.put(v, c); adjColors.remove(v); for (E e : graph.edgesOf(v)) { V u = Graphs.getOppositeVertex(graph, e, v); if (!colors.containsKey(u)) { int uSaturation = saturation.get(u); BitSet uAdjColors = adjColors.get(u); HeapHandle uHandle = handles.get(u); if (uAdjColors.get(c)) { heap.delete(uHandle); degree.put(u, degree.get(u) - 1); heap.insert(uHandle); } else { uAdjColors.set(c); saturation.put(u, uSaturation + 1); degree.put(u, degree.get(u) - 1); heap.fixup(uHandle); } } } } return new ColoringImpl<>(colors, maxColor + 1); } SaturationDegreeColoring(Graph<V, E> graph); @Override @SuppressWarnings("unchecked") Coloring<V> getColoring();  }### Answer:
@Test public void testSaturationDegree() { Graph<Integer, DefaultEdge> g = new Pseudograph<>(DefaultEdge.class); Graphs.addAllVertices(g, Arrays.asList(1, 2, 3, 4, 5, 6)); g.addEdge(2, 3); g.addEdge(4, 5); g.addEdge(4, 6); g.addEdge(5, 6); g.addEdge(5, 3); Coloring<Integer> coloring = new SaturationDegreeColoring<>(g).getColoring(); assertEquals(3, coloring.getNumberColors()); Map<Integer, Integer> colors = coloring.getColors(); assertEquals(0, colors.get(1).intValue()); assertEquals(0, colors.get(2).intValue()); assertEquals(1, colors.get(3).intValue()); assertEquals(1, colors.get(4).intValue()); assertEquals(0, colors.get(5).intValue()); assertEquals(2, colors.get(6).intValue()); }