Graph coloring algorithm (Greedy coloring)

Question

I'm working on a graph-coloring project using Java. I need to implement four different graph coloring algorithms using four-color theorem. I have a problem with one of the algorithms named few neighbors greedy algorithm.

I have a map which contains bunch of polygon objects (stored in an arraylist) in it. Also, I have a 2D boolean array that represents the adjacencies of different polygons.

I know the algorithm theoretically: I have a priorityqueue that stores my uncolored polygons. The order of the queue based on adjacency counts. If a polygon has few neighbors, it is considered better than a polygon which has a lot of neighbots. Anyway, the algorithm should repeatedly draw a polygon from the priorityqueue and attemp to color it based on its adjacencies.

Unfortunately, I have problems with the implementation part. I got the priorityqueue based on thie adjacency counts, but I have problems while assigning colors to those polygons. If is there anyone who worked on that kind of algorithms, or anyone with an idea, please share with me. I need some ideas to speed up the implementation part.

Thanks in advance.

Answer 1

You should state exactly what kind of help you need with the implementation part. "I have problems when assigning colors" how?

A map which contains Polygon objects stored in an array list with a separate 2D boolean array for adjacencies is the input? I assume your polygons are Nodes in the graph.

You should probably build a Graph data structure and navigate it. The classical, C-style approach is using arrays for nodes and edges and making it look complex.

Since OOP using Composition naturally generates a graph of objects that's a good approach to use here.

Graphs are essentially composed of 2 elements: Nodes and Edges.

Start with a Node class. It has a color, an id, and an ArrayList of Edges. Edges form a relationship between 2 nodes, and may have a weight and a direction.

Make your nodes and edges from the inputs (remember, if a new node doesn't exist, then make it). Then run the nearest neighbor algorithm by picking an unmarked node (a static method may work well for this, or you can really practice for real life and implement the Strategy Pattern).

Look out for cycles, though!

Answer 2

You sound like you're trying to color the lowest degree nodes first. That seems backwards, you should color the highest degree nodes first. For instance, nodes of degree 3 will always be colorable if you have 4 colors to choose from.

You do realize that any greedy algorithm might very well fail to find a 4-coloring, even if the graph is 4 colorable.

Check out the Wikipedia page for some helpful pointers.