Graph Colouring AppletInstructions 1)Choose the number of variables, amount of colours you wish the graph to be coloured with, and the graph complexity, and click Generate. 2)Choose the algorithm you want to colour the graph, and click Start. 3)If at any point you want to stop the algorithm working, click Stop. This will stop the algorithm from running, but keep the current assignment of colours to nodes. A new graph can be generated, the previous graph can be reset, or a new algorithm can takeover from where the previous algorithm left off. 4)If you wish to reset the graph you have generated to attempt to solve with a different number of colours or a different algorithm, select the amount of colours to be used and click Reset. How the applet works The applet works by generating random nodes on the plane and placing clauses (edges) between them based on each generation method e.g low/high. The exception to this is the bipartite graphs, which always generate fixed points and clauses on the plane. Once these have been generated, a clause is coloured red if the nodes which it connects have the same colour, or green if they have a different colour (unsatisfied/satisfied). Once the graph has been created, the amount of colours that provide an upper bound to the number of colours needed to solve the graph is displayed in the “Definitely n-colourable” section. Generally the amount of colours needed will be in the region of 3-4 for low and high graphs, 2 for the bipartite graphs and 5 for the Erdos-Renyi graphs.
Once start has been clicked, the selected algorithm begins colouring the graph. CFL is a decentralized algorithm, SLS stands for Stochastic Local Search and represents a Schoning-like algorithm, and DPLL is an algorithm based on the Davis-Putnam-Logemann-Loveland algorithm.
The ticker tape that the applet creates as it is running displays two separate pieces of information in real time. One is a ticker tape of the amount of unsatisfied variables remaining versus the number of iterations, and is represented in red. The other ticker tape is the number of unsatisfied clauses versus the number of Iterations. The scale of the y-axis is logarithmic, and the ticker tape restarts itself after every 500 loops to accommodate for spacial limitations.
Some interesting features to note The SLS algorithm has difficulty finding a solution to the bipartite graphs. The algorithm will most likely reset any assignment it is given due to the small number of assignments in the solution set.
As can be seen from running the CFL algorithm, the majority of any graph remains satisfied throughout the time that a solution is trying to be found. Because of this, a network for example can use the majority of its resources efficiently even while the algorithm is running.
GraphsLow Complexity
These graphs are generated using the lune method. This is done by first randomly populating the plane with points. Each point will be compared with every other point on the plane in pairs. A pair is compared by constructing circles centered at each point with a radius equal to the distance between the pair. If no other points lie in the intersection between the two circles ( the lune ) a line will be drawn between the two points. This type of graph is called a relative neighbourhood graph. We call each edge between two points a clause. The complexity level is measured by how many clauses there are divided by the amount of variables. This is called the clause/variable ratio. This method generally produces a clause/variable ratio of 2.4.
High Complexity
These graphs are generated using the Gabriele method. This is done by first randomly populating the plane with points. Each point will be compared with every other point on the plane in pairs. A pair is compared by constructing a circle with a diameter equal to the distance between the two points. If no other points lie in the circle a line will be drawn between the two points.This method generally produces a clause/variable ratio of 3.7.
Erdos - Renyi
these graphs are randomly generated graphs.a line has a probability p of being drawn between two points. The probability is given by p = log(n)/n, where n is the amount of variables being used. Generating graphs in this way will almost surely give a connected graph and these graphs are generally colourable with 5 colours
Bipartite
Bipartite graphs are two colourable and are difficult to solve with stochastic algorithms. The Star graph is also a bipartite graph.
Papers
|
 |
Links |
