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".