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(E * V*V) :where E is edges and colorNum, and V is number of vertices.
> Note:
> Although it appears that
> O(E * M*V) : 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));
}
}