Generalized Swendsen-Wang implementation

NOTE: A new version is in the works with improved functionality and some bugfixes. If you need this code, please send me an e-mail; otherwise I'll wait until later to pack it up.

Offered here is a templated C++ implementation of the stochastic graph partitioning technique described in

Adrian Barbu and Song-Chun Zhu, Stochastic Graph Partition: Generalizing the Swendsen-Wang Method. Technical report, UCLA Department of Statistics, Paper 2003010120, 2003,
among other places. The image below is a link to a 6 MB MPEG-4 video showing the code at work on a graph whose configuration changes over time.

[Link to the video]

Figure 1  The algorithm operating on a small graph where vertices are associated with a number of randomly-moving points. The probability of two vertices belonging in the same subgraph is related to the distance between the closest pair of points from the vertices (thin gray lines). Each frame is derived from a number of sampled partitions: the thickness and redness of lines between vertices is proportional to the frequency of the connected vertices being in the same subgraph together. The inset histogram shows the proportions of sampled partitions with 1,2,...,6 subsets.

The current version of the code is 0.1, last updated on 10 February 2008. From here you may

If you use this code and/or have comments or improvements, I hope you'll drop me a line at tss *at* Thanks!
Back to Tom Stepleton's academic webpage