This software solves maximum weight b-matchings using fast belief 
propagation. It is provided as-is, with no warranty, and can be freely 
used for scientific research. Please contact me at bert@cs.columbia.edu if 
you want to use it for commercial reasons. 

If you use this code in research for publication, please cite the papers:

Fast b-Matching via Sufficient Selection Belief Propagation
B. Huang and T. Jebara. Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS) 2011

and

Loopy Belief Propagation for Bipartite Maximum Weight b-Matching.
B. Huang and T. Jebara. Eleventh International Conference on Artificial Intelligence and Statistics (AISTATS) 2007,







Compile the software by using the makefile in the "Release" directory, 
which will create a binary BMatchingSolver program. Or if you wish to use 
the static methods in the BMatchingLibrary as a dynamic library, use the
makefile in "Shared Library", which creates a dylib file. Alternatively, this 
repository is an Eclipse project, which can be imported into your workspace.

See the "html" directory for documentation. 

Please send questions, comments to bert@cs.umd.edu. 

See shell script examples/runExamples.sh for how to call the command line tool, and see the matlab script tester.m for how to call the matlab functions.

Usage: BMatchingSolver <options>
-w, --weights	weight matrix file
-d, --degree	degree file
-x, --data	node descriptor file
-o, --output_file	output file
-n, --total	total number of nodes
-D, --dimensions	dimensionality of node descriptors
-c, --cacheSize	number of cached weights per row
-b, --bipartite	number of nodes in first bipartition
-t, --weight_type	weight type (0 = matrix, 1 = negative Euclidean, 
                                    2 = inner product)
-i, --max_iter	maximum iterations of belief propagation to run
-B, --binary	use binary data files

The weight matrix file is a tab-delimited matrix ascii matrix of size nxn
Alternatively, you can give node descriptor (feature vectors) of size nxd.
The degree file is a file of ascii numbers, one per line, indicating the 
target degree for each node. Parameter n is the total number of nodes in
your input graph, and if the graph is bipartite, parameter b is the number
of nodes in the first bipartition.

A number of matlab toolbox functions are in the matlab directory:

bdmatch_augment.m - create an augmented weight matrix for bd-matching (degree-
                    constrained subgraph) using auxiliary nodes
BMatchingSolver.cpp - mex c++ file for direct matlab interface
BMatchingSolver.mexmaci64 - 64-bit mac binary for mex version
BMatchingSolverCmd.m - command line wrapper that calls the CLI BMatchingSolver
lprelax.m - much slower lp relaxation solver for bd-matchings
makeMex.m - script to compile the mex BMatchingSolver.cpp 
tester.m - tests the mex and the CLI versions against the lprelax on 
            various random problems of different sizes