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: firstname.lastname@example.org).
Please report and suggestions or bugs.
We use implementations of the Hungarian algorithm (LAP code due to
R. Jonker and A. Volgenant, email: email@example.com) and
H. Gabow's N-cubed weighted perfect matching algorithm, written by
Ed Rothberg, found at:
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.
Computes the permanent of a nonnegative integer matrix.
Notes: Compile in C++, "g++ -o permanent permanent.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
Then "make" the codes (this codes are in C, not C++).
The program is then run by the command "wmatch".