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
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
Illustrates the effect of the activation threshold. Copies of the same graph are 4-colored using different activation probabilities; clockwise from top left:
  • Low activation threshold (10%) - too slow in removing conflicts.
  • Medium activation threshold (30%) - fast removal of most conflicts.
  • Medium activation threshold (50%) - fast removal of most conflicts.
  • High activation threshold (90%) - thrashing; worse performance than a random colorer.
Effect of tightness of constraints
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:
  • 2 colors - over constrained. The strong patterns are characteristic of 2-colorings. (Note that the colorer achieves a degree of conflict of approximately 27% - the best that could be achieved with 2 colors is 25%.)
  • 3 colors - over-constrained.
  • 4 colors - critically constrained. A proper coloring is possible with 4 colors, but the decentralized algorithm is unlikely to find it. When the number of conflicts is small, their behavior is similar to a random walk.
  • 5 colors - under constrained. The number of conflicts is quickly reduced to almost zero.
  • 6 colors - under constrained. As with 5 colors, the reduction in conflicts is fast.
  • 8 colors - loosely constrained. Compared with the colorings that use 5 or 6 colors, this coloring is actually worse, in spite of the problem being easier. When the number of conflicts is small, a dynamic equilibrium is reached in which the conflict reduction mechanism in the colorer is counter-balanced by the random introduction of conflicts caused by neighbors simultaneously changing color.
  • 10 colors - loosely constrained. Similar behavior to 8 colors.
  • 12 colors - loosely constrained. Similar behavior to 8 colors.
FP vs. CFP
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.