CSCE 782: Problem Set 1

Asynchronous Backtracking

You will implement the ABT algorithm as shown in the book and explained in class. Your implementation must have the following features:

1. The setup button will generate a random graph. Let the user choose the number of nodes, the ratio of edges to nodes, and the number of colors. In a random graph every edge is created between 2 randomly chosen nodes. Can you create a graph that is guaranteed to have a coloring?
2. The layout button will layout the graph, making it look pretty.
3. The go buttons will let the user step thru the execution of the algorithm.

Programming Tips

You will need to implement a message queue on each node. At each step of the simulation the agents will fetch the first message from this queue and handle it, possibly placing messages at the end of other agents' queues as a result.

You do not need to implement a full hyper-resolution rule for all pairs. At minimum, you can just use the complete local-view as the nogood. But, if you want to explore with better no-good generators, by all means, be my guest! Note that, since you are not generating all possible no-goods your algorithm will, therefore, not be complete, so it might fail to find solutions when they exist.