ChromaSA

Draw a graph, then watch simulated annealing color it.

ChromaSA is an interactive visualizer for the graph coloring problem. You build a graph by clicking, and the annealer searches for an assignment of three colors in which no edge joins two nodes of the same color. Conflicting edges are drawn in red, so the quantity being minimized is visible on the canvas rather than buried in a counter.

---

Quick start

You need a JDK 21 or newer. Maven is not required — the wrapper fetches it on first use.

./mvnw package          # Windows: mvnw.cmd package
java -jar target/chromasa.jar

Using it

Action	Result
Click empty canvas	Adds a node with a random starting color
Click a node	Selects it (an orange ring appears)
Click a second node	Connects the two
Click the selected node again	Deselects it
Start	Runs the annealer
Stop	Ends the run early, keeping the best coloring found
Clear	Empties the canvas
Speed	Delay between iterations, from 50 ms down to none

While a run is in progress the canvas and the parameter fields are locked, because the solver is reading the graph you would otherwise be editing.

The status bar reports the iteration, the current energy, the best energy seen, and the current temperature.

How it works

The energy of a coloring is the number of edges whose endpoints share a color. A valid coloring has energy zero, so coloring the graph becomes minimizing this function.

The move is to recolor a single node: pick a random edge, pick either of its endpoints, and give it one of the other two colors. Only that node's incident edges can change, so the energy change is computed locally in O(degree) rather than by rescanning the whole graph.

The acceptance rule is the standard Metropolis criterion. A move that lowers the energy is always taken; a move that raises it by delta is taken with probability

P = exp(-delta / T)

which is near 1 while the temperature T is high and near 0 once it is low. That is what lets the search climb out of a local minimum early on and settle into one later.

The cooling schedule controls how T falls. Two are offered:

Schedule	Formula	Second parameter
Exponential decay	T(i) = T0 * a^i	cooling rate a, in (0, 1); nearer 1 cools more slowly
Logarithmic decay	T(i) = T0 / (1 + c * ln(1 + i))	log factor c > 0; larger values cool faster

A run ends at the first of: a valid coloring, the temperature floor (T <= 0.01), the iteration budget (1200), or Stop.

A note on temperature scale

The energy here is a small integer, and a single move changes it by 1 or 2. So the acceptance probability that matters is exp(-1/T), and that number tells you which temperatures are actually meaningful:

T	1000	10	3	1	0.3	0.1
exp(-1/T)	0.999	0.90	0.72	0.37	0.036	0.00005

At T = 1000 every uphill move is accepted and the search is a random walk; the annealing really happens between roughly 3 and 0.1. The default starting temperature of 10 sits just above that band, and the run stops at 0.01 rather than at 1 — stopping at T = 1 would end while the search was still taking a third of all uphill moves.

Logarithmic cooling is the schedule with the classic convergence guarantee, and it is genuinely slow: with c = 1 the temperature falls only by a factor of about eight over the whole 1200 iterations, so those runs end on the iteration budget. Raise c to cool harder.

Project layout

src/main/java/chromasa/
  ChromaSA.java            JFrame, controls, and the SwingWorker that drives a run
  GraphModel.java          nodes, edges, colors, and the energy function
  SimulatedAnnealing.java  the search - no Swing dependency at all
  GraphPanel.java          rendering
src/test/java/chromasa/    JUnit 5 tests for the model and the solver

SimulatedAnnealing takes an injected Random and reports through a listener interface, so it runs headlessly and deterministically under test. The UI and the solver share no mutable state: the worker is handed immutable snapshots and returns a finished color array.

Tests

./mvnw test

The suite covers the energy function, duplicate and self-edge rejection, the solver reaching a valid coloring on 3-colorable graphs under both schedules, correct failure reporting on K4 (which needs four colors, so one conflict is unavoidable), the incremental energy never drifting from a full recount, both schedules cooling monotonically, and parameter validation.

Implementation notes

This started as a coursework prototype in a single file. Turning it into this repo meant fixing a number of defects that are worth naming, since most of them are the kind that only show up under interaction:

• The canvas stayed editable during a run. Adding a node reallocated the color array the background thread was indexing, adding an edge could throw ConcurrentModificationException from the energy loop, and Clear could null the array out from under it. The solver now works on immutable snapshots, and the controls lock while it runs.
• The node selection survived Clear, so selecting a node, clearing, and clicking again could record an edge pointing at a node that no longer existed.
• Logarithmic cooling could not terminate. The stop condition was T > 1 with T = T0 / (1 + ln(1 + i)); from T0 = 1000 that needs about e^999 iterations, so the run was bounded only by the iteration cap and stayed hot enough to accept essentially every move. The schedules are now closed-form functions of the iteration count, and the temperature scale was corrected as described above.
• The reported energy did not describe the picture. The final coloring restored was the best one found, but the number on screen was the last one tried.
• Duplicate edges were accepted, and each copy counted separately toward the energy.
• A perfect coloring did not stop the run, which then idled for the remaining iterations.
• Only one endpoint of the chosen edge was ever recolored, biasing the search.
• The SwingWorker's publish/process pair was declared but never used; every iteration instead posted several separate tasks to the event thread.
• Edges were painted over the nodes rather than behind them, and nothing was anti-aliased.