Graph Coloring - acnelson12/CS-335-Algorithms GitHub Wiki

As far as I know, there are no issues with the program. I tried to make it easy to switch out the data structure that was used by the iterative backtracker. In doing so, I ran into battles with generics because I needed to create a new instance of a parameterized type. To resolve this, I did something that might be an absolutely terrible thing to do, but I'm not sure if it is because I am unfamiliar with the techniques I used. I'll try to explain what I understand. I added a constructor to BacktrackerIterative which takes in a Class object and stores it as an instance variable. In backtrack(), I used reflection to create a new instance of that class. Unfortunately, this alone makes the instantiation of the BacktrackerIterative object more complicated to the point that it almost defeats the whole point of what I want to do. I want to make it so that changing the data structure only needs to be done in one place. To reclaim this efficiency, I created a static nested class called Type which is simply declared as a subclass of whatever data structure you wish to use. It has no methods of its own; it merely serves as an alias for its superclass. However, there are other issues with this, namely that different data structures have methods which are analogous in function but have different names. Because of this, I created an interface which I named (a bit vaguely) Data to ensure consistency with adding elements, removing elements, and checking if the data structure is empty. The nested class, Type, implements Data, but since it has no methods of its own, this requires that its superclass implements the methods specified by Data. The type parameter passed to BacktrackerIterative also must implement Data.

Another odd thing I did in my program was that I made GraphColoringState an inner class of another class called GraphColoringTask. The reasoning is that for a given graph coloring problem, the list of colors, the list of their weights, and even the graph itself should not change for each state. GraphColoringTask was created to hold all of the data that will be shared between all states of a given graph coloring problem. Originally, I had stored these data as class variables, but I did not feel that this properly represented their implied immutability as well as only allowing one graph coloring problem to be solved at a time. The use of an inner class gives the best of both worlds: it is possible to deal with multiple graph coloring tasks at once, and there is greater efficiency since each state is not holding its own copy of data which should be shared. In the end, this also helps to logically encapsulate all GraphColoringStates with their associated GraphColoringTask and makes it harder for states to become corrupted.

The classes StateStack, StateQueue, and StatePriorityQueue have been created for use in testing. They basically just extend an existing data structure and translate their methods to satisfy the implementation specified by Data.