Generalized Matching Code
Stuart Andrews and Tony Jebara, 2007

A command-line tool for solving generalized matching problems (a.k.a. b-matchings, or degree-constrained subgraphs) is available here. The archive contains binaries for Linux and MacOSX. There is also a precompiled MEX interface for Matlab. To get started follow these instructions. There's a README with more details if you have questions, or if things do not work as expected.

Command-line tool
tar xvfz bmatch.tgz cd bmatch make ./bmatch -h
Matlab tool
tar xvfz bmatch.tgz cd bmatch make ./matlab_bmatch help bmatch

Help file

Usage> bmatch [-arg1 value] [-arg2 value] ... Solves: max_Yij sum_ij W_ij Y_ij s.t. sum_j Y_ij <= b_i, 1 <= i <= n and Wij and Yij are symmetric Arguments [with default values]: -w -weights [NULL] input file, NULL => std. input -d -degrees [NULL] input file, NULL => std. input -o -output [NULL] output file, NULL => std. output -c -const_b [-1 ] positive integer, negative => std. input -s -sparse [0 ] 0 => matrix, 1 => IJW input format -m -method [1 ] selects algorithm -v -verbose [0 ] positive integer Algorithm: 1. exact solution using goblin mincost solver via subgraph complement 2. exact solution using goblin mincost solver via negated weights 3. greedy 1/2 approximation 5. greedy 1/2 approximation with recursion 7. bipartite relaxation using belief propagation Notes: Self-loops are handled: a self-loop increases the degree of a node by 2. Weights must be positive (Wij >= 0). Edges with zero-weight (Wij==0) are not allowed to partake in the matching. If the weights, degrees or output file is not specified, then the corresponding input [output] data is entered in [written to] the display. The format should match the examples given in the data directory. Enter a blank line to terminate input of a given data. The output weight is calculated as sum_{i<=j} Wij Yij, except when beleif propagation is used, whose output is not necessarily symmetric. For BP, the output weight is 0.5 * sum_{i,j} Wij Yij. The reduction in methods 2 yields the optimal matching if the upper bounds are tight at the solution. Otherwise, this method may not satisfy the upper bounds. For Known Issues and Troubleshooting tips, see the full README.

Many thanks to Vlad Shchogolev and Bert Huang for their code and examples. Vlad implemented prototypes for method 2 and 3. This tool integrates Bert's BP code directly. For a stand-alone loopy BP implementation, use Bert's code.

This tool links to the impressive Goblin Graph Library and LGPL licensing issues apply. To experiment with this library, please download the source code directly from the Goblin site. I would be happy to share the source that has been modified slightly for Mac OS X.