Write a function named colorGraph that attempts to assign colors to vertexes of an undirected connected graph from a given collection of available colors such that no neighboring vertexes have the same color as each other.
Your function accepts two parameters: a reference to a BasicGraph, and a reference to a Vector of strings representing available colors.
You should return a Map from vertex names to strings representing colors to assign to each vertex.
The diagram below shows an example graph that might be passed to your algorithm.
Our BasicGraph collection is generally used to represent directed graphs, but in this case you may assume that the graph represents an undirected graph and that for every edge A → B there will also be an edge B → A.
The second image is an example coloring of the graph using 3 colors: blue (vertexes A, C, E), green (vertexes B, G, I), and red (vertexes D, F, H).
This particular graph cannot be colored successfully with fewer than 3 colors, but any value of 3 or greater must work successfully.
If the graph above is represented by a BasicGraph object named graph, and a Vector named colors contains the strings {"blue", "green", "red"}, then the call of colorGraph(graph, colors) should return a map like the following, where the letters like A, B, C represent pointers to those corresponding Vertex structures in the graph:If the graph above is represented by a BasicGraph object named graph, and a vector named colors contains the strings {"blue", "green", "red"}, then the call of colorGraph(graph, colors) should return a map like the following:
{"A":"blue", "B":"green", "C":"blue", "D":"red", "E":"blue", "F":"red", "G":"green", "H":"red", "I":"green"}
If there are multiple valid ways to color the graph, your function can return any one of them.
If the coloring cannot be performed with the given number of colors, or if the colors vector is empty, return an empty map.
Efficiency: Note that in order to be certain that you have exhaustively found a suitable coloring (or verified with certainty that there is no coloring), you must try every possible combination of vertex/color mappings.
This can be a slow process, so your code must avoid exploring options that are certain to be unable to find a valid result.
For example, if your code assigned vertex A the color blue, it should not explore giving vertex B (A's neighbor) the same color of blue.
Assumptions:
You may assume that the graph is connected.
You may assume that the graph's state is valid and that no two vertices have the same name.
You may also assume that the graph is connected (that there exists a path from every vertex to every other vertex) and that it is undirected, in the sense that if there is an edge from vertex V1 to V2, there is also an edge from V2 to V1.
You may assume that the graph contains no self-edges (e.g. from V1 to V1).
Constraints:
You may define private helper functions if so desired, and you may construct auxiliary collections as needed to solve this problem.
You should not modify the structure of the graph (e.g., add or remove vertexes or edges), but you may wish to modify the state variables inside individual vertexes/edges (e.g., cost, visited, color, etc.).
