[up]

Soft Graph Coloring Animations

These animated screen captures illustrate the process of (decentralized) soft graph coloring. The are AVI files and should play on a modern Windows PC without requiring any software to be installed.

In each case, the graph being colored has 900 nodes and a chromatic number of 4.

Visualization of the FP algorithm: AVI
Shows the basic process of the Fixed Probability coloring algorithm. The colorer is using 4 colors and has an activation probability of 30%.
Effect of activation threshold: AVI
Illustrates the effect of the activation threshold. Copies of the same graph are 4-colored using different activation probabilities; clockwise from top left:
Effect of tightness of constraints: AVI
Illustrates FP's behaviour when over-constrained, critically constrained, under-constrained and loosely constrained. Copies of the same graph are colored using a fixed activation probability (30%) but different numbers of colors; clockwise from top left:
FP vs. CFP AVI
Compares the FP algorithm with the "conservative" variant CFP, which has the better performance for under-constrained and loosely constrained colorings. FP is displayed along the top row, CFP along the bottom row. Each algorithm colors (copies of) the same graph using (from left to right) 5, 6, 8 and 10 colors. Note that CFP quickly eliminates all conflicts in all but the 5-colors case.