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]](swenwang-small.png)
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* ri.cmu.edu. Thanks!