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 VV and not VM.
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));
}
}
