# C++ codes for estimating permanents, hafnians and the number of
forests in a graph

This file describes how to use a series of programs written to implement
the estimates given in
Random weighting, asymptotic counting and
inverse isoperimetry ,
by Alexander Barvinok and Alex Samorodnitsky.
The programs are given by Alexander Yong (email: ayong@umich.edu).
Please report and suggestions or bugs.
We use implementations of the Hungarian algorithm (LAP code due to
R. Jonker and A. Volgenant, email: roy_jonker@majiclogic.com) and
H. Gabow's N-cubed weighted perfect matching algorithm, written by
Ed Rothberg, found at:
ftp://ftp.zib.de/pub/Packages/mathprog/matching/weighted/index.html

span_forest.c :
Computes estimates for the number of forests of a graph,
input as a 0-1 incidence matrix.
Notes: Compile in C++, "g++ -o span_forest span_forest.c". The program
does not demand that the matrix is symmetric with 0 diagonal, but uses
only the upper triangular part.

permanent.c :
Computes the permanent of a nonnegative integer matrix.
Notes: Compile in C++, "g++ -o permanent permanent.c".

hafnian.c :
Computes the hafnian of a nonnegative integer matrix.
Notes: Copy hafnian.c to main.c, in the same directory as Rothberg's
code (see above). You can download the .tar directory with the code
weighted-match.tar here.
Then "make" the codes (this codes are in C, not C++).
The program is then run by the command "wmatch".