2
\$\begingroup\$

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
 | /
 3

Space: \$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));
    }
}
\$\endgroup\$
1
\$\begingroup\$

The most blatant error is running time analysis is wrong. Running time is T(E,V,M) with E,V, M as you said above.

Since you call compute() recursively, in the best case scenario the number of nodes being colored is at most 1, the size of the input will be reduced by at best one. Speaking from my experience, this is the sign of exponential running time. (T(n) = p(n) + c*T(n-1), where p(n) a polynomial)

And I am not convinced that this is guaranteed to complete either because you seem to make even more calls on compute() when the size of the input to each compute() will now shrink only by a constant. ie, you decrease the input but increase the number of recursive calls. You will not have guaranteed result.

\$\endgroup\$

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.