Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices. Special request to verify complexity:Complexity:Time:\$O(EV^2)\$ :where \$E\$ is edges and colorNum, and \$V\$ is number of vertices.Note: Although it appears that \$O(EMV)\$ : where, \$M\$ is number of colors, but truth is the for loop for colors, would never count more than number of vertices. Check 4th node. even if numColors M were 25, it would still loop only max V times.  Thus complexity is \$V*V\$ and not \$V*M\$. 1 | \ 2--4 | / 3Space:  \$O(V)\$ - the node-color map used to store precomputed colors.Looking for code-review, optimizations and best practices.class GraphColor<T> implements Iterable<T> {    /* A map from nodes in the graph to sets of outgoing edges.  Each     * set of edges is represented by a map from edges to doubles.     */    private final Map<T, Set<T>> graph = new HashMap<T, Set<T>>();    /**     *  Adds a new node to the graph. If the node already exists then its a     *  no-op.     *      * @param node  Adds to a graph. If node is null then this is a no-op.     * @return      true if node is added, false otherwise.     */    public boolean addNode(T node) {        if (node == null) {            throw new NullPointerException(The input node cannot be null.);        }        if (graph.containsKey(node)) return false;        graph.put(node, new HashSet<T>());        return true;    }    /**     * Given the source and destination node it would add an arc from source      * to destination node. If an arc already exists then the value would be      * updated the new value.     *       * @param nodeA                    the source node.     * @param nodeB                    the destination node.     * @throws NullPointerException     if source or destination is null.     * @throws NoSuchElementException   if either source of destination does not exists.      */    public void addEdge (T nodeA, T nodeB) {        if (nodeA == null || nodeB == null) {            throw new NullPointerException(Source and Destination, both should be non-null.);        }        if (!graph.containsKey(nodeA) || !graph.containsKey(nodeB)) {            throw new NoSuchElementException(Source and Destination, both should be part of graph);        }        /* A node would always be added so no point returning true or false */        graph.get(nodeA).add(nodeB);        graph.get(nodeB).add(nodeA);    }    /**     * Removes an edge from the graph.     *      * @param nodeA        If the source node.     * @param nodeB   If the destination node.     * @throws NullPointerException     if either source or destination specified is null     * @throws NoSuchElementException   if graph does not contain either source or destination     */    public void removeEdge (T nodeA, T nodeB) {        if (nodeA == null || nodeB == null) {            throw new NullPointerException(Source and Destination, both should be non-null.);        }        if (!graph.containsKey(nodeA) || !graph.containsKey(nodeB)) {            throw new NoSuchElementException(Source and Destination, both should be part of graph);        }        graph.get(nodeA).remove(nodeB);        graph.get(nodeB).remove(nodeA);    }    /**     * Given a node, returns the edges going outward that node,     * as an immutable map.     *      * @param node The node whose edges should be queried.     * @return An immutable view of the edges leaving that node.     * @throws NullPointerException   If input node is null.     * @throws NoSuchElementException If node is not in graph.     */    public Set<T> edgesFrom(T node) {        if (node == null) {            throw new NullPointerException(The node should not be null.);        }        Set<T> edges = graph.get(node);        if (edges == null) {            throw new NoSuchElementException(Source node does not exist.);        }        return Collections.unmodifiableSet(edges);    }    /**     * Returns the iterator that travels the nodes of a graph.     *      * @return an iterator that travels the nodes of a graph.     */    @Override public Iterator<T> iterator() {        return graph.keySet().iterator();    }}public final class ColorGraph<T> {    private ColorGraph() {}    /**     * Given a graph and number of colors, colors the graph such that no adjacent nodes have same color.     * Note: the map of nodes and colors is one-of the possible solutions that may eists.     *      * @param graph         the graph to be colored     * @param colorCount    the number of colors      * @return              the map of nodes to the colors.     */    public static <T> Map<T, Integer> getNodeColor (GraphColor<T> graph, int colorCount) {        final Map<T, Integer> nodeColor = new HashMap<T, Integer>();        if (compute(graph, graph.iterator().next(), null, colorCount, 0, new HashSet<T>(), nodeColor)) {            return nodeColor;        } else {            throw new IllegalArgumentException(Number of colors inadequet to color graph.);        }    }    private static <T> boolean compute (GraphColor<T> graph, T node, T parent, int colorCount, int parentColor, Set<T> visited, Map<T, Integer> nodeColor) {        if (visited.contains(node)) return true;        visited.add(node);        // check all colors and pick the color which is valid.        int color = 0;        boolean validColor = false;        for (color = 0; color < colorCount; color++) {            validColor  = true;            for (T neighborNode : graph.edgesFrom(node)) {                 if (nodeColor.containsKey(neighborNode) && nodeColor.get(neighborNode) == color) {                    validColor = false;                }             }            if (validColor) {                break;            }        }        if (!validColor) return false;        nodeColor.put(node, color);        boolean finalResult = true;        for (T node1 : graph.edgesFrom(node)) {             finalResult = finalResult && compute(graph, node1, node, colorCount, parentColor, visited, nodeColor);        }        return finalResult;    }}public class ColorGraphTest {    @Test    public void test1() {        GraphColor<Integer> gcd1 = new GraphColor<Integer>();        gcd1.addNode(1);  gcd1.addNode(2); gcd1.addNode(3);        gcd1.addEdge(1, 2);        gcd1.addEdge(2, 3);         gcd1.addEdge(1, 3);        Map<Integer, Integer> map = new HashMap<Integer, Integer>();        map.put(1, 0);        map.put(2, 1);        map.put(3, 2);        assertEquals(map, ColorGraph.getNodeColor(gcd1, 20));    }    @Test    public void test2() {        GraphColor<Integer> gcd2 = new GraphColor<Integer>();        gcd2.addNode(1); gcd2.addNode(2); gcd2.addNode(3); gcd2.addNode(4); gcd2.addNode(5);         gcd2.addEdge(1, 2);         gcd2.addEdge(2, 3);         gcd2.addEdge(2, 4);        gcd2.addEdge(3, 4);         gcd2.addEdge(4, 5);        Map<Integer, Integer> map = new HashMap<Integer, Integer>();        map.put(1, 0);        map.put(2, 1);        map.put(3, 0);        map.put(4, 2);        map.put(5, 0);        assertEquals(map, ColorGraph.getNodeColor(gcd2, 20));    }    @Test    public void test3() {        GraphColor<Integer> gcd3 = new GraphColor<Integer>();        gcd3.addNode(1); gcd3.addNode(2); gcd3.addNode(3); gcd3.addNode(4); gcd3.addNode(5);         gcd3.addEdge(1, 2);        gcd3.addEdge(2, 3);         gcd3.addEdge(2, 4);         gcd3.addEdge(3, 4);        gcd3.addEdge(4, 5);          gcd3.addEdge(5, 2);        Map<Integer, Integer> map = new HashMap<Integer, Integer>();        map.put(1, 0);        map.put(2, 1);        map.put(3, 0);        map.put(4, 2);        map.put(5, 0);        assertEquals(map, ColorGraph.getNodeColor(gcd3, 3));    }    @Test    public void test4() {        GraphColor<Integer> gcd4 = new GraphColor<Integer>();        gcd4.addNode(1); gcd4.addNode(2); gcd4.addNode(3); gcd4.addNode(4);        gcd4.addEdge(1, 2);         gcd4.addEdge(2, 3);         gcd4.addEdge(2, 4);         Map<Integer, Integer> map = new HashMap<Integer, Integer>();        map.put(1, 0);        map.put(2, 1);        map.put(3, 0);        map.put(4, 0);        assertEquals(map, ColorGraph.getNodeColor(gcd4, 3));    }}
M coloring problem
java;algorithm;graph